初心者・初級者向け：ABCのC問題を自分なりに分類してみた
背景
A問題やB問題はひたすら解くだけですが、C問題以上になると、アルゴリズムや解法を学び始める必要があると思いました。ある程度まとまった時間で、ひとつのジャンルの問題を解き続けたいと思って分類してみました。
対象読者
競技プログラミングの初心者・初級者を想定しています。
AtCoder で言うと、茶色以下の人たちが体系立てて学習したいときの一助になれば幸いです。
対象範囲
配点が300点のABC-C問題をピックアップしています。勉強したい用語を検索してお使いください(ex. 再帰、グラフ、累積和など)。
注意事項
筆者自身のプログラミング知識は大したことありませんので、分類が適当すぎたり誤りがあるかもしれません。その場合はお気軽にご指摘いただけると助かります。
分類表
一問一答十九週目
概要
AtCoder Virtual Contest で、一日一問 ABC-C 問題を解いてます。一週間ごとにさらっと内容をおさらいします。
九十七回目
解説AC。初期はすべて表かつ3x3のエリアスキャンをするので、四隅、周上、内部で場合分けすればよい。
九十八回目
解説写経AC。極力左下にいる赤点を残す方針で貪欲にペアを作る。
九十九回目
解説AC。(コスト総和) - ( を消した時のコスト) + (
と
をつないだ時のコスト)を順に調べる。
百回目
複数問やりました。
百一回目
解説AC。数学的な証明は公式解説参照。思いつける気があまりしない。。。今回の制約なら、BFS でも通せるみたい。
百二回目
解説AC。ソートすれば中央値の候補が2つに絞れる。候補の値と削除する値を比較して中央値を判定する。
百三回目
解説AC。C 円のものを2i枚買うのと、2C円のものをi枚買うのは本質的に同じ。Cを2枚ずつ買って、買い切れなかったらA,Bを個別に買うという調査を繰り返す。
百四回目
時間内AC。単体で黒マスが存在するか調べる。
百五回目
解説AC。部分文字列の特性を考慮して、各頭文字を先頭とした長さがK以下（5以下）の部分文字列を調べればよい。
百六回目
写経。左端から見て、Wを向く必要があるEの個数からスタート（すべてのEをカウントする）。左からi番目とi-1番目の向きを調べる。i-1番目がWならEに向く必要があるのでカウントをひとつ増やす。i番目がEなら重複するのでカウントを一つ減らす。
むすび
ゴールが見えると、早く終わらせたくなるものです。
一問一答十八週目
概要
AtCoder Virtual Contest で、一日一問 ABC-C 問題を解いてます。一週間ごとにさらっと内容をおさらいします。
九十二回目
解説AC。三重ループを二重ループで済ませる典型問題。気づいたけどなぜか解けず。
九十三回目
自力AC。の時間内に
から
へ移動可能か調べる。かつ、それらの偶奇を比較する。
九十四回目
時間切れAC。j回目（j : 1～N）で下に移動する場合でキャンディの個数を全探索。素直にやるだけ。
九十五回目
時間切れ自力AC。素直にやるだけ。多重リストで set 型取ろうとしてミスった。取れないことを学んだ。
九十六回目
時間切れ自力AC。M A R C H で始まる人数を数えて、それら人数のの組み合わせをすべて足し合わせる。
むすび
6月はコンテスト参加おやすみ予定です。
一問一答十七週目
概要
AtCoder Virtual Contest で、一日一問 ABC-C 問題を解いてます。一週間ごとにさらっと内容をおさらいします。
八十七日目
写経AC。10桁のbitを探索すればよいと思ったが、実装できず。
「営業時間が一致する」かつ「ほかの店がその時間に営業している」ことを、「[k]]」で判定している。bit探索使いこなしたい。
八十八日目
自力AC。個数の少ない種類から書き換えるようにすればよい。もしくは。個数が多い種類をできるだけキープすると考えればよい。
Counter メソッドの、.most_common(n) を使うと、出現回数が多い順に要素を取得できて便利。
八十九日目
自力AC。やるだけ。
各数字の個数を調べて紐づける(Counter 使用)。key と valueの大小関係に応じて処理する。key > value ならすべて取り除く、key = value ならそのまま、key < value なら value - key だけ取り除く。
九十日目
寝坊AC。入力例に惑わされず、一番小さい数を2倍していって調べればよい。
九十一日目
あと回し（問題文読み解くのがめんどくなってしまった…）
むすび
問題の題意の理解が遅い。
一問一答十六週目
概要
AtCoder Virtual Contest で、一日一問 ABC-C 問題を解いてます。一週間ごとにさらっと内容をおさらいします。
八十二回目
写経AC。制約が緩いので全探索でよい。Tと等しくなる部分文字列Xを探し、存在していたら"?"部分をすべてaに変えればよい。
八十三回目
写経AC。ABC127回目（？）あたりで同様の問題があったのでその練習。何とか自力でできるようになりたいな。
・貪欲にスコアが高くなるように全探索
・「各種最もおいしいネタ」と「そのほかのネタ」を分けて降順ソート
・累積和を利用して、ネタの種類が1～Kの時のスコアを調べて最大値を求める
八十四回目
写経AC。をキーとして、
と
の個数を調べればよい。二分探索って便利なんだな。PyPyでないとTLEです。
八十五回目
解説AC。一回目で失敗したとしても、それ以降の期待値はずっと変わらない。言われてみたらそりゃそうだ。
八十六回目
むすび
八十六回目
寝坊した…AC。全探索やるだけ。ただし、汎用性を高めるにはbit探索がよさそう。
むすび
YouTube の動画解説が楽しみになっている。
一問一答十四週目
概要
AtCoder Virtual Contest で、一日一問 ABC-C 問題を解いてます。一週間ごとにさらっと内容をおさらいします。
七十回目
時間外AC。丁寧に丁寧に場合分けするだけ。レート3200以上の人は灰～赤以外の色も使えるという条件を認識していなくてかなり悩んだ。。
七十一回目
時間外AC。丁寧に場合分けを考えればよい。階乗した値など、大きな数の余剰を取る場合、計算の毎に余剰を取ると計算量を減らすことができる。
七十二回目
地力AC。各要素の番目に応じて、右から追加するか、左から追加するか場合分けすればよい。O(n) で解ける。
七十三回目
解説AC。for 文の中で迂闊にリスト操作すると、二重ループになりかねないので注意。 かつ
であることを利用して、一回のループで計算可能。
七十四回目
解説AC。①1~i への経路が存在しているか調べる。②i~Nへの経路が存在しているか調べる。③両方存在していれば移動可能。
①、②用に bool 配列を2つ用意して、配列の番目を上記 i として記録する方法がとても勉強になった。
七十五回目
解説AC。丁寧に場合分けする問題。「4の倍数」「4の倍数以外の偶数」「奇数」の並べ方の最適化を考えればよい。「4の倍数以外の偶数」は、一括りにすると奇数一個と等価とみなせるのがポイント。
七十六回目
解説AC。lcm を求めるだけとは気づいたものの、なぜか解けなかった…実装力？
gcd や lcm は累積的に求めることができる、というのはポイント。reduce 関数使わなくても、複数の数に対して計算可能。
七十七回目
解説AC。大きい順に棒を並べて、同じ長さが二本ずつ存在するか調べていき、二つのペアが作れた時点で最大面積が求められる。
もともとやろうとしていた方法で RE が出たのはなぜなのだろうか…
むすび
C問題に対する抵抗感はだいぶなくなってきたと思う。
