こんにちは。3/17のABC091で無事水色になる事ができたので、今までにやってきた事と水色になるために必要だと感じた事をまとめようと思います。
この記事に載っている内容はあくまで個人の意見なので、あくまで参考程度にお願いします。
また、私自身が水色最底辺の人間なので知識が浅く、いくつか間違っている点があるかもしれません。ご容赦ください。
自分語り
塚本@shibh308です。執筆時点でのレートは1215で、今までのレート推移はこんな感じ(下画像参照)です。
競技プログラミングを本格的にやり始めたきっかけは去年の12月ごろ、JOI予選で300点爆死をキメたのがきっかけでした。当時はアルゴリズムについての知識が全くなかったので、200点問題ですら解けるか怪しいようなレベルだったと記憶しています。
当時のコードはこんな感じですね。この時はB問題を時間いっぱい使ってやっと解けたみたいな状態でした…
ここから競プロに関する基礎的な考え方を学び、2完〜3完で安定するようになりました。この時点での平均パフォは900程度で、300点問題が解けるか解けないかのラインだったと思います。
1月〜2月にかけて300点問題を埋めたり蟻本の初級編を読んだりして、2月中旬にあったABC088で全完する事ができました。そこからは「10〜30分で3完➔余裕があればDに取り掛かる」みたいな流れを続けてパフォ1350-1550辺りを維持し、無事に水色になる事ができました。
水色になるために必要そうな事
私のこれまでの経験と偏見を元に、「これだけできるようになれば水色になれる！」みたいな目安と知っておくべきアルゴリズム、考察のコツについてまとめました。
コンテスト順位や問題について
順位やパフォの目安
・ABCでrated内110〜70位辺りを維持する
・ABCやAGCでパフォ1300-1500辺りを維持する
・爆死しない
300点問題の早解きさえできれば上二つは楽に達成できると思います。(ABC-Dが極端に簡単な場合を除く)
個人的には爆死しない事が一番重要だと思っています。ABC-Cに80分かけて4WA3完とかAGC-Aで5WA0完とかやるとレートがヤバいぐらい下がって非常にヤバいです。気をつけましょう(自戒)
解けるようにすべき問題の目安
・300点問題のうち8割ぐらいを30分で解けるようにする
・400点問題の半分ぐらいを時間内に解けるようにする
500点以降は時間内に解けなくても全く問題ないです。
ABC-Dで500点以上が出る場合は3完でもパフォ1600が取れる事が多いので、3完早解きを意識した方がいいと思います。
問題を解くために使う知識について
使えるようにしておくべき事や知っておくべき性質
・幅優先探索、深さ優先探索
・順列の全列挙(next_permutationを使うと楽)
・2nや3n通りの全列挙(bit演算でも関数を使った列挙でも)
・木の基本的な性質(辺の数がN-1になる事とか二点間の道が必ず一つな事とか、基本的な事だけ)
・最小公倍数、最大公約数の計算(ライブラリとして持っておくと楽)
・累積和(一次元のみ)
・除算を除く四則演算のMOD計算
・ダイクストラ法を使った最短経路計算
・Union-Find木(なくても解けるけどあると簡単になる問題がかなり多い印象)
・漸化式を使った簡単なDP(確率DPとか桁DPは必須じゃないです)
・約数計算や素因数分解、エラストテネスの篩を使った素数列挙
・メモ化再帰(重複計算を避けて計算量を落とす)
・upper_bound,lower_boundを使った配列の二分探索
あまり高度でないものは省いていますが、おおよそこんな感じだと思います。
もちろん全てが必須な訳ではないですが、これらが身についていると300点〜400点問題を解くのがかなり楽になるはずです。
必須ではないけど使えると便利なアルゴリズムや知識
・任意の二点間の最短経路計算(ワーシャルフロイド法)
・負の経路の検出(ベルマンフォード法)
・除法のMOD計算(MOD=109+7の時だけ知っておけば十分っぽい)
・組合せや重複組合せ(前もってテーブルを作ると楽)
・確率や期待値計算(ぼくはよくわかってません)
・しゃくとり法
・二次元累積和
・最小全域木(クラスカル法でもプリム法でもよい)
・二部マッチング問題(ライブラリを持ってると便利)
・最大フロー、最小カット(同上 ライブラリだけ持ってればいいです 使う機会少なめ)
・bitDPや桁DP(知っておいて損はないって程度)
・木やDAG上での簡単なDP(メモ化して計算量を落とす問題)
・評価する関数を用意するタイプの二分探索
この辺りの知識は基本的にABC-D以降でしか要求されない(はず)なのですが、知っておくと400〜500を解く時に役立つかもしれません。
ただ、水色になるだけならこれらの知識が全くなくても問題ないと思います。
水色になるまでに使わない(要求されない)知識
・トポロジカルソート(使える事もあるけど、想定解では必要ない事が多い気がする)
・セグメント木、遅延セグ木、BIT等のデータ構造(トポロジカルソートと同様 ABCでは基本必要にならない)
・半分全列挙(使えるようになって損はないけど、400点問題では多分出ないよね…)
・ダブリング
・xor演算他ビット演算の性質(ABCでも出る事はあるけど、基本的に500点以上の高難易度問題なので覚えなくていいです)
・幾何問題で使ういろいろ(覚える必要はないです 簡単なものはその都度調べればいいので…)
・橋や関節点の検出(ABCで必要になる事はほとんどないはず)
・三分探索
・その他なんか難しいやつ色々
この辺になるとまずABCでは必要にならないです。
上の方は知っていると楽になる事がありますが、水色になるだけなら正直全く必要ないので…
考察する時のポイント
300点以上の問題になると脳死で全探索する訳にも行かないので、問題を考察する必要が出てきます。
そこでいくつか考察時の(基本的な)ポイントを挙げたいと思います。
(※説明の途中にいくつかの問題のネタバレを含んでいます！このようなリンクを押すと問題ページに飛ぶようになっているので、ネタバレを避けたい方は問題ページへのリンクを踏まないようにするといいかもです。)
とりあえず制約を見る
すごい大事です。見忘れたら一大事です。
N<=105ならN2が間に合わないとかN<=16なら2Nが余裕を持って通るとかN<=8ならN!でも十分通るとか、制約から分かる事はたくさんあるはずです。
この問題なんかが分かりやすい例なのですが、N!が通る事に気づかずに難しい解法を考えて時間を溶かしてしまう事が稀によくあるので注意しましょう。(自戒)
算数っぽい問題(これとかこれとか)にありがちな「O(1)でも解けるけどO(N)やO(N2)で解いた方が楽」みたいな問題は無理してO(1)解法を考える必要はないです。
また、複数ある制約のうちどれかが非常に小さい場合(例:N<=105,M<=10)、小さい方の制約に着目して何かできないかを考えると考察がスムーズに進んだりします。
問題文をちゃんと読む
こう書くと馬鹿にしていると勘違いされそうなのですが、問題文をちゃんと読む事は非常に大切です。いや、本当に。
3完早解きセットで誤読して30分溶かすとかやっちゃうと悲しすぎるので、問題文をちゃんと読みましょう。
「自分の家以外の家を少なくとも1軒訪れる」を「自分以外の家すべてを少なくとも1回訪れる」と勘違いして「ｱｯこれ巡回セールスマン問題じゃんｗｗｗｗｗｗｗ無理やろｗｗｗｗｗｗｗ」とか考えてた馬鹿からのお願いです。誤読は絶対に避けましょう。
手計算できるケースを人力で解いてみる
特にゲーム系の問題だと多いのですが、パターンを全て紙に書き出してみると法則性に気づける事がよくあります。「最適な行動をした場合どうなるか」を求めるこの問題や、(ゲーム問ではないですが)この問題などは手計算できる範囲で書き出してみると考察が非常に楽になります。
問題や操作を簡単にできないか考える
問題文の余計な部分を削ぎ落として考えるのはそれはそうなのですが、問題文を見て「このグラフ実質木じゃんｗｗｗｗ」とか「ｱｯこの入力答えに関係ないじゃんｗｗｗｗｗｗ」とかに気づけると非常に楽になる場合があります。
これなんかは操作の簡略化ができれば後は簡単(ABC-Cぐらいの難易度)ですし、この問題とかこの問題とかは簡略化を考える事が本質なので、できる限り操作を簡単にできないか考えていきましょう。
問題内容やサンプルを見やすくする
これは単純かつ効果も強い方法なのですが、サンプルの例を絵なり図なりに書き起こしてみると非常に分かりやすくなります。
特にグラフ問題は入力例だけだと理解しづらいので迷ったら図を書くべき。すごい大切。
辺情報を入力するとグラフをいい感じに可視化してくれるサイト(generate DOT)もあるので、これらのサイトを活用したりして問題を分かりやすく整理しましょう。
もし計算量が余りそうならなら贅沢に使ってみる
いや、これは本当に場合によるのですが、もし計算量が105以下のコードを書いてるのならもっと贅沢に計算量を使ったコードを書いた方がいいです。
制約N<=103でO(NlogN)のめっちゃヤバい実装とO(N2)の楽な実装が思いついたのなら、O(N2)の楽な実装をした方がいいと(僕は)思います。
…でもN<=2000で想定解O(1)の500点問題もあるし…うん！場合によるな！
水色になるまでの勉強法
自分自身の経験を元に精進する時のコツをいくつか挙げてみたいと思います。
どうしても僕個人の考え(偏見)が強く反映されたものになってしまいますが参考までに…
とりあえず過去問(300~400)を片っ端から埋める
AtCoder ProblemsやAtCoder Scoresを見ながら埋めて行けばよいのでやりやすく、似た傾向の問題が降ってきた時に役立ちます。
とりあえずこれやっておけばいい感ある(小声)
苦手分野の問題を探して解く
これももちろん大切。偶然CもDも苦手分野で2完しかできなかったみたいな事があれば人生終了ですしね…
dijkstra-webやhttps://koki-yamaguchi.github.io/などのサイトを使えばジャンルごとの問題絞り込みが可能なので、これらを使っていい感じに解いていくと対応できる問題が広がって非常によいと思います。
蟻本を中級編辺りまで流し読みする
これ非常に効果あっておすすめです。あまり理解しなくてもいいので流し読みして、コンテスト中に「これ蟻本で見た気がする！」ってなれば後は蟻本写経でACがとれたりとれなかったりします。
バチャをやる
AtCoder Virtual Contestを使うとAtCoderの過去問を使ったバーチャルコンテストを開催できます。
他の人が立てたバチャに参加するなり自分でバチャを立てるなり、普段より集中した環境で問題に取り組めるので非常によいです。
海外コンに出る
てっとり早く水色になりたいならこどふぉかCSAで2完できればすぐ水色になれるので…(殴)
まぁ、海外コンは集中して問題を解きたい時の練習やレートが停滞してきたと感じた時の気分転換に実際よいです。
言語の壁もGoogle翻訳に丸投げすれば解決できるので、皆さん海外コンに出ましょう(出ましょう)。
問題集
このページで例に挙げた問題と、ABC-CまたはABC-Dの問題で(個人的に)やっておくべきだと感じた問題をいくつか貼っておきます。どれも良い問題なのでぜひ解いてみましょう(解きましょう)。
ABC006-C スフィンクスのなぞなぞ
ABC040-C 柱柱柱柱柱
ABC054-C One-Stroke Path
ABC070-C Multiple Clocks
ABC075-C Bridge
ABC085-C Otoshidama
ABC090-D Remainder Reminder
ABC055-D Menagerie
ABC059-D Alice&Brown
ABC067-D Fennec VS. Snuke
ABC073-D joisino's travel
ABC078-D ABS
ABC085-D Katana Thrower
ABC088-D Grid Repainting
