AtCoder 記憶に残っている問題集（～ABC314）

:::note info
2023年9月18日現在、A/B 問題全踏破完了。引き続き C 問題でネタ集め＆順次更新中。
このレート帯での本命は C/D 問題です。
:::

# AtCoder 記憶に残っている問題集

自分と同じ緑コーダーくらいの人向けのイメージ。自分自身も過去 ABC マラソンしながらネタ増やしていきます。
「しばらく間を空けてからでも忘れないよう復習しときたいと思えたかどうか」「記憶を消してもう一回チャレンジしたいと思ったか（解いてて楽しかったか）」を判断基準にしています。ただ面倒くさいだけといったものは載せません。

★マークはその難易度帯における学びの大きさ（主観）

+ [AtCoder](https://atcoder.jp/)（本家）
+ [AtCoder Problems](https://kenkoooo.com/atcoder/)（これとにらめっこしながらお楽しみください）
+ [AtCoder のテストケース](https://www.dropbox.com/sh/nx3tnilzqz7df8a/AAAYlTq2tiEHl5hsESw6-yfLa?dl=0)（どうして WA なのか分からない時に）
+ https://qiita.com/drken/items/fd4e5e3630d0f5859067

# ABC-A

## 論理的思考とパターン整理

### [ABC383-A](https://atcoder.jp/contests/abc383/tasks/abc383_a)（★）
事象や課題も分かりやすく、プログラミング入門者にとっての良い問題だと思う。

### [ABC313-A](https://atcoder.jp/contests/abc313/tasks/abc313_a)（★）
ヌケモレないかきちんと考えよう。

### [ABC263-A](https://atcoder.jp/contests/abc263/tasks/abc263_a)（★★）
ソートした時の法則性を見つける問題はけっこうあります。

### [ABC261-A](https://atcoder.jp/contests/abc261/tasks/abc261_a)（★★）
いきなり図形的な考察を求められるので手が止まる。答えが 0（離れている）でない場合は、包含されている場合・交差している場合を問わず、 **右端の小さいほう－左端の大きい方** ``min(r1, r2) - max(l1, l2)`` が答えになることを頭の中でイメージできるか。

### [ABC249-A](https://atcoder.jp/contests/abc249/tasks/abc249_a)（★★★）
設問はシンプルなくせに A 問題にしては鬼難易度。実装量もボリューム大き目。丁寧に考えないとハマるし、A 問題においておくとトラウマになる。

### [ABC227-A](https://atcoder.jp/contests/abc227/tasks/abc227_a)（★★★）
シンプルですが添字の扱いを間違えるととんでもなくドツボに。地味に良問だと思う。

## アルゴリズムとデータ構造

### [ABC273-A](https://atcoder.jp/contests/abc273/tasks/abc273_a)（★★★★）
いきなり数式が出てくるので、面食らう人は面食らう。今後鬼門になるであろう DP への布石として、 $f(k)=f(k-1)...$ といった関数表記の実装に慣れておきましょう。

### [ABC159-A](https://atcoder.jp/contests/abc159/tasks/abc159_a)（★★）
```math
\displaystyle {}_n C_k = { n \choose k } = \frac{n!}{k! (n-k)!} = \frac{{}_n P_k}{k!}
```
こんな公式覚えていなくても $\displaystyle {}_n C_2$ なら直観的にわかるように。

## 知らないと手が止まる

### [ABC274-A](https://atcoder.jp/contests/abc274/tasks/abc274_a)（★）
``round()`` じゃダメっぽいのは知ってるだけど、四捨五入ってどうやるんだっけ…と。f-string したいけどゼロ埋めの表記方法忘れてしまったよ。

### [ABC213-A](https://atcoder.jp/contests/abc213/tasks/abc213_a)（★）
xor のビット演算子なんて普段使わないから覚えてるわけない。※Python には ``& \| ^ ~ << >>`` の5つのビット演算子があります。

# ABC-B

## 発想力

### [ABC313-B](https://atcoder.jp/contests/abc313/tasks/abc313_b)（★★★）
最初、``itertools`` の ``permutations`` で全順列をリストアップして可能性のないものをツブしていくという力業で提出したら、全 26 テストケース中 ACx7 TLEx19 という笑える結果に。$2 \leq N \leq 50$ 見てなかったよー。
どうしてもわからずに公式解説行き。なんでこれで完全に説明できるのかいまいち分からないままモヤモヤして終了。「全ての情報が正しくなるように、全ての相異なる 2 人組にどちらが強いかを割り当てる方法が少なくとも 1 通り存在する」という制約が大切なんですよね、きっと。

### [ABC302-B](https://atcoder.jp/contests/abc302/tasks/abc302_b)（★★★）
愚直に全サーチすれば良いのだけれど、あらかじめ 8 方向の ``(dx, dy)`` を用意しておいて、全地点で 8 方向走査かけていく…と。盤面系でよく出てくるイディオムですね。

### [ABC264-B](https://atcoder.jp/contests/abc264/tasks/abc264_b)（★★）
[チェビシェフ距離](https://ja.wikipedia.org/wiki/%E3%83%81%E3%82%A7%E3%83%93%E3%82%B7%E3%82%A7%E3%83%95%E8%B7%9D%E9%9B%A2)・・・ごめんなさい、思いつきませんでした。$\max(\lvert dx \rvert, \lvert dy \rvert)$ ってよく考えればその通りなんだけど。[ABC180-B](https://atcoder.jp/contests/abc180/tasks/abc180_b)がまとめです。

### [ABC255-B](https://atcoder.jp/contests/abc255/tasks/abc255_b)（★★）
これはつまり何を求めればよいのか気付かないと手が止まったままに。

### [ABC195-B](https://atcoder.jp/contests/abc195/tasks/abc195_b)（★）
難しい。どうしてそうなるのか最後まで分からなかった…。

### [ABC060-B](https://atcoder.jp/contests/abc060/tasks/abc060_b)（★）
整数のお話、こういうの苦手です。


## 論理的思考とパターン整理

### [ABC334-B](https://atcoder.jp/contests/abc334/tasks/abc334_b)（★）
周辺の B 問題と比べて頭一つ抜けて正解率が低い。深く考えようとすると余計ハマるのかもしれない。

### [ABC310-B](https://atcoder.jp/contests/abc310/tasks/abc310_b)（★★）
同じ機能でもっと安いのないかな？値段同じならせめてちょっとでもいいものを！って現実的にも業務の実務的にもありそう、なんか楽しい。``set`` の使い方に慣れるためにいい。

### [ABC295-B](https://atcoder.jp/contests/abc295/tasks/abc295_b)（★★★）
盤面読み込み系の問題は今後再頻出になるので必修です。この手の問題は、ゲームをクリアした感が強くて大好き。[Rogue](https://ja.wikipedia.org/wiki/%E3%83%AD%E3%83%BC%E3%82%B0)好きとしてもたまらん。
盤面をリストとして読み込むイディオムはよそ見しててもかけるようになっておきましょう。

### [ABC272-B](https://atcoder.jp/contests/abc272/tasks/abc272_b)（★★★★）
難しいアルゴリズムは何も要らないのに、色々詰まっていて良問だと思う。B 問題ってこういうのがいい。設問の設定もそれっぽいし。

### [ABC265-B](https://atcoder.jp/contests/abc265/tasks/abc265_b)（★）
あくまで素直でまっすぐな問題がいいですね。

### [ABC262-B](https://atcoder.jp/contests/abc262/tasks/abc262_b)（★★★）
色々応用問題。隣接リスト作ったのはいいけど、ここからどうしよう・・・と一時停止してしまった。トレビアンな解法があるのかと、ドキドキしながら解説を見たらそんなこと全くない。まっすぐ全検索だ。B 問題にしては難易度ちょい高め？

### [ABC258-B](https://atcoder.jp/contests/abc258/tasks/abc258_b)（★★★★）
最初、途中でも自由に動けるものと勘違いして $O(8^n)$ をどうしようか小一時間ばかり悩んでしまった。よくよく考えると自由に動けてしまったら最大値は、最大数とと周辺最大数のジグザグ往復であることが自明だったりしてヘコんだりと色々ありました。結論：問題はきちんと読みましょう。
いずれにせよ、B 問題の中では相当難しめ。どころか歴代 B 問題の中で最高難易度に近いと思う、実戦でこれが 2 問目にやってきたら涙目必至だわ。

### [ABC197-B](https://atcoder.jp/contests/abc197/tasks/abc197_b)（★★）
突如重いのが来てびっくりする。この周辺の B 問題と比較すると格が違うような。

### [ABC194-B](https://atcoder.jp/contests/abc194/tasks/abc194_b)（★★★）
頭の中でパターン整理するのが気持ちいい。``min()`` と ``max()`` でキレイに書きたい。

### [ABC107-B](https://atcoder.jp/contests/abc107/tasks/abc107_b)（★★）
[ABC197-B](https://atcoder.jp/contests/abc197/tasks/abc197_b)といい、B 問題でやってくる盤面読み込み系は単純に面倒なのが多いような…。イラっとせずに愚直にいこう。

### [ABC087-B](https://atcoder.jp/contests/abc087/tasks/abc087_b)（★★★★）
ループ最適化の分かりやすい練習問題だと思う。制約も緩いので全探索だけど、二重ループでいこう。


### [ABC075-B](https://atcoder.jp/contests/abc075/tasks/abc075_b)（★★★）
盤面読み込みマインスイーパー。

### [ABC070-B](https://atcoder.jp/contests/abc070/tasks/abc070_b)（★）
線分の重なっている部分を求める問題は今後頻出。[ABC261-A](https://atcoder.jp/contests/abc261/tasks/abc261_a)と同じ問題。``min(右端)-max(左端)``、重なってないと負の値。

### [ABC054-B](https://atcoder.jp/contests/abc054/tasks/abc054_b)（★★）
盤面読み込み系、クソ面倒・・・。


## アルゴリズムとデータ構造

### [ABC280-B](https://atcoder.jp/contests/abc280/tasks/abc280_b)（★★★）
メモ化（DP）の練習。この程度の制約であれば、何も考えずに書いても ``AC`` できる。

### [ABC276-B](https://atcoder.jp/contests/abc276/tasks/abc276_b)（★★★★）
グラフ問題で隣接リストを作る練習。これ知らないとここから先には進めないので必修。私は ``g = {i: [] for i in range(1, n + 1)}`` な感じで ``dict`` の入れ物を作ってしまいます。``list`` にするのか、0 オーダーにするのか・・・などいつも迷うのですが、結局これが一番応用が利く気がする。

### [ABC006-B](https://atcoder.jp/contests/abc006/tasks/abc006_2)（★★★★）
漸化式とデカすぎる数字に慣れる練習。

## 全探索（計算量）

### [ABC331-B](https://atcoder.jp/contests/abc331/tasks/abc331_b)（★）
小難しいアルゴリズムを駆使しないと…と一瞬構えるが$1 \leq N \leq 100$なので 3 種類の全買い物パターン数え上げでも大丈夫。

### [ABC299-B](https://atcoder.jp/contests/abc299/tasks/abc299_b)（★★★）
問題は簡単なんですが、何も考えずに ``enumerate`` でリスト内包表記をズラズラ並べていたらまさかの TLE。$2 \leq N <= 2 \times 10^5$ を 2 sec. 以内っていうのは意外と意識しなきゃいけないレベルなんだと知った。``zip`` って素敵です。いぶし銀的良問か。

### [ABC293-B](https://atcoder.jp/contests/abc293/tasks/abc293_b)（★★★★）
呼ばれたことある人リストを作ってループの中で毎回 ``in`` 走査してしまい初回 ``TLE``。``in`` って便利だし脊髄反射で書いてしまうけれどもこれだけで $O(n)$ のコストがかかることを意識しなければ。
$N \leq 2 \times 10^5$ を二重にするとそりゃ ``TLE`` しますわな・・・って計算量を意識しはじめるための良問だと思う。``buf = [False] * n`` って書きにくいんだよなあ。スマートじゃないというか、メモリケチケチ病が身に染みてるというか。

### [ABC251-B](https://atcoder.jp/contests/abc251/tasks/abc251_b)（★★★）
自由すぎて、あちこちに工夫の余地がある。何も考えないと当然 ``TLE``。こういうの苦手。

### [ABC228-B](https://atcoder.jp/contests/abc228/tasks/abc228_b)（★★）
また制約をよく読まずに $10^5$ ループの中で ``in`` 使ってしまった…。[ABC293-B](https://atcoder.jp/contests/abc293/tasks/abc293_b) と同じ轍。

## 知らないと手が止まる

### [ABC273-B](https://atcoder.jp/contests/abc273/tasks/abc273_b)（★）
毎度おなじみ四捨五入。``Decimal.quantize`` の使い方を調べなくてもよいように、「対象のケタを小数点第一位に配置し、2倍して1足して2で割る」です。逆にこれじゃダメなパターンが分からない、丸め誤差が発生するケースがあるのかな。

### [ABC259-B](https://atcoder.jp/contests/abc259/tasks/abc259_b)（★）
いきなり無茶を言わないでくださいという感じ。[回転行列](https://ja.wikipedia.org/wiki/%E5%9B%9E%E8%BB%A2%E8%A1%8C%E5%88%97)調べるしかなかったわな。
```math
\begin{bmatrix}
x' \\
y'
\end{bmatrix}
=
\begin{bmatrix}
\cos(\theta) & -\sin(\theta) \\
\sin(\theta) & \cos(\theta)
\end{bmatrix}
\begin{bmatrix}
x \\
y
\end{bmatrix}
```
```math
x'=x\cos(\theta)-y\sin(\theta) \
```
```math
y'=x\sin(\theta)+y\cos(\theta)
```

### [ABC189-B](https://atcoder.jp/contests/abc189/tasks/abc189_b)（★）
割り算に注意。

# ABC-C

## bit全探索

### [ABC190-C](https://atcoder.jp/contests/abc190/tasks/abc190_c)（★★）
問題文がとっても読みにくいけど、普通にbit全探索して全通り計算してみるだけ。$2^{16}=65536\fallingdotseq10^6$ なので、その内側で $10^2$ を回してもギリ OK かな…とか妄想して実装。
bit全探索っていうのは文字通り全探索なので、計算量はあくまでも $O(2^n)$ ベースってことを忘れずに。

### [ABC167-C](https://atcoder.jp/contests/abc167/tasks/abc167_c)（★★★★）
問題設定も分かりやすいし、bit全探索基本おさえのお手本問題のような感じ。最終出力が最小金額だったりするので、理解度集計のたびに使った金額の小計も取っとかなきゃならなくてちょい面倒。
だけど実務プログラミングではこういうケースの方が多かったりするし学びは多い。

### [ABC045-C](https://atcoder.jp/contests/abc045/tasks/arc061_a) ([ARC061-C](https://atcoder.jp/contests/abc045/tasks/arc061_a))（★★★★）
bit全探索の基本練習。[ABC079-C](https://atcoder.jp/contests/abc079/tasks/abc079_c) も全く同じ。詳細は [こちら](https://qiita.com/gogotealove/items/11f9e83218926211083a) をどうぞ。

## 全探索（計算量）

### [ABC112-C](https://atcoder.jp/contests/abc112/tasks/abc112_c)（★）
シンプルな全探索なんだけど、細かいひっかけポイントがいくつかあるので注意。問題文のテストケースはすんなり通り、意気揚々と提出したら 1 つだけ ``WA`` して頭を悩ませるパターン（俺だ）

### [ABC095-C](https://atcoder.jp/contests/abc095/tasks/arc096_a)（★★）
ループ回す対象を工夫すれば全探索の計算量を最適化できるシンプルな例。何かが決まると、残りの要素はおのずと確定するので検証不要という考え方に気付く練習。$O(n /2)$ でいけそうです。