入青したので ABC と色の話を書きたい

入青した～

ABC の話

• Ａ 問題
  大抵は、入出力と if とか for とか使えれば何とかなる。「〇言語の基礎 (or 入門)」みたいなのをある程度理解していれば多分解ける。
• B 問題
  基本、Ａ 問題の難しい版みたいな感じ。全探索とかできれば大体大丈夫そう。あとは、D、E、F 問題の簡易版 (導入部分？) みたいなのが出る場合もある。vector クラスは使えた方が便利かも。sort 関数が、オーダー $O(N \log N)$ だと知っておいた方がいい場合もある。
• C 問題
  オーダーの概念は知っておくべき。set (順序付き集合)、map (連想配列) (、multiset、multimap)、stack、queue、deque などを使うこともある。深さ優先探索 (DFS) や幅優先探索 (BFS) も出るかも。
• D 問題
  深さ優先探索 (DFS) や幅優先探索 (BFS) も出る。基本的には、C 問題の難しい版。
  動的計画法 (DP) や二分探索、貪欲法やしゃくとり法が出たりもする。
• E 問題
  ダイクストラ法やワーシャルフロイド法などの最短経路問題や Union-Find を用いた素集合問題、DP などが出る。また、最小全域木 (Union-Find で求められる) も出ることがある。Union-Find は割と利用頻度高い。
• F 問題
  E 問題の難しい版。セグメント木を使ったり、低頻度で出てくるアルゴリズムをほぼそのまま使って解ける場合もある。
• G 問題
  最大流 (二部マッチングや劣モジュラ関数) が出る。高難度 DP やその他アルゴリズムが出ることもある。
• Ex 問題
  多項式や形式的べき級数を用いた数え上げや分割統治法が出る。その他アルゴリズムや難しい数学の公式が出ることもある。

色の話

• 入茶
  ABC では 3 完くらいで茶パフォっぽい。3 完安定すれば余裕で入茶できる？
  3 完安定させるなら、クラスは、set (順序付き集合)、map (連想配列) (、multiset、multimap)、stack、queue、deque あたりは知っておきたい。pair や tuple なども便利。
  アルゴリズムは、深さ優先探索 (DFS) や幅優先探索 (BFS) を理解しておくと良さそう。DFS や BFS をするなら、隣接リストが便利。
  オーダーも理解しておくとより良い。
• 入緑
  大体 4 完くらい？難しめのときは、速 3 完でも届きそう。
  4 完は、動的計画法 (DP) や二分探索が出ることもあるので理解しておきたい。貪欲法やしゃくとり法などもあるけど、知らなくても自力でなんとなくできそう (？)。
  あとは、3 完までスムーズに解けるように頑張るとか？　時間かかりそうな問題は一旦飛ばすのもアリ (飛ばした先の問題でコケるとつらいけど)。
• 入水
  速 4 完から 5 完くらい。速 4 完のみでも続けていれば入水できるかも。
  5 完なら、グラフや DP に慣れたい。Union-Find はよく出る。最短経路問題系 (ダイクストラ法やワーシャルフロイド法 (やベルマンフォード法)) も出る。 毎回実装するのは大変なアルゴリズムも出てくるので、関数やクラスの作り置き (または、AtCoder Library (ACL) の利用) をしたくなってくる。(最短経路問題系は ACL にない (？) ので作っておきたい。Union-Find はある。)
  また、実行環境も整えたい。atcoder-cli と online-judge-tools とか。β 版 (2023/1/26 現在) で unrated 推奨っぽいけど、Hisui とかもある。
• 入青
  速 5 完から 6 完くらい。
  BIT やセグメント木あたりも理解しておきたい。 F 問題は E 問題のレベルアップ版みたいな感じ (？) なので、入水までに学んだことに慣れてくれば、入青もある程度見えてくる気がする。まあ、知らないアルゴリズム出てくるときもあるけど…それは、その都度学んでもらえると。
  それか、AtCoder の「競プロ典型 90 問」とかで、いろいろなアルゴリズムに触れるのもいいかも。
• 入黄
  速 6 完から 7 完くらい。全完は rated 卒業には基本的に要らない ()。
  6 完安定させるか 600 点問題を取りに行くかは必要。
  G 問題は、最大流とか難 DP とか、その他アルゴリズムとかだろうか？
• 入橙・赤
  ABC には縁のないお話…。ARC で速 3 ~ 4 完、AGC で速 2 ~ 3 完くらいは最低でも欲しそう。

おわりに