0.はじめに
こんにちは、HIROSHI0635です。緑色になった時も、簡単な記事を書きましたが、緑になってから約9ヶ月でなんとか水色になることができました。正直かかった時間としては長い方だと思います。だからこそ緑や茶色で苦戦してる方に少しでもヒントとなるものが書ければと思って執筆しております。そういう意図もあって、あえておこがましくも「AtCoder水色になるまで」ではなく、「AtCoder水色なるには」というタイトルを付けました(記事書いてる途中で緑落ちしてるのはご愛敬...)。
| 章 | タイトル | 備考 |
|---|---|---|
| 1. | 自己紹介 | |
| 2. | 問題の考え方 | メインパートです |
| 3. | その他精進内容 | |
| 4. | コンテストでの立ち回り | 小技みたいな話が多めです |
| 5. | 便利リンク集 |
1.自己紹介
・金融関係の社会人3年目。
・AtCoderはC++で一度始めたが何もできず1ヶ月ほどで挫折。
・Pythonに言語を変えて再挑戦し1年半で水色到達。
・大学時代は文系。プログラミングは全くの未経験。
・大学受験段階で数学への苦手意識は無し。
ざっとこんな感じです。
AtCoderを始めた詳しい経緯など知りたい方は、過去記事（ AtCoder緑になるまで)
をご覧ください
2. 問題の考え方
2-1.伸び悩みから考えたこと
初めての緑パフォーマンスが11回目のコンテストなのに対し、初めて水色パフォーマンスが取れるのは38回目（38回の日立コンテストは100-200の速解がたまたまハマっただけなので実質は41回目）までかかりました。確かに11回目のころは、DFS,BFS,ダイクストラ法,二分探索etcといったいわゆる「定番アルゴリズム」もわからない状況でしたが、25回目になる頃にはそれらは全て何度かは実装してコピペできるような問題ならACできる状況でした。それでもなかなか緑Difficulty1の問題を解けなかった理由として、計算量2への意識、問題を帰着する意識の2つが弱かったからだと思います。
2-2.計算量に対する意識を高める
突然ですが、AtCoderの問題を解くのをカレー作りに置き換えて考えてみましょう（カレーに特に意味はありません、今思いついただけです）。制限として2000円以内で作ってカレーを作ってくださいと言われたとします。普通の人はスーパーに向かって、2000円より多く具材を買わないと思いますが、競技プログラミングにおいて予期せずTLEになるということはこういうことです。この具材は何円かわからないという意識が働いてるなら幾分マシですが、値段を考えずにレジに向かっていたり、これは100円だと思っている物が実は5000兆円だったりすると最悪です。自分の解答の計算量がよくわからない人はいろんなアルゴリズムに手を出すのではなく、まず自分の解答の計算量を把握する癖をつける方がいいと思います（偉そうなことを言ってますが、自分が計算量を把握して解答を出すことを意識しだしたのは緑になる直前くらいからです）。そもそもアルゴリズムを使う動機が、全探索では間に合わないので計算量を落とすために使うのであって、計算量がわからなければ、宝の持ち腐れになるからです。
じゃあどうやって計算量を把握する能力を高めたらいいのかと言われると、練習段階でこの計算量がいくらかわからないという場面があると、計算量を調べるか、計算量が確定する書き方に変える癖をつけるしかないと思います。Python使いならこの記事（Pythonistaなら知らないと恥ずかしい計算量のはなし）はかなり参考になると思います。
2-3.問題を帰着する意識を高める
突然ですが（またか）、AtCoderはよく数学ゲーと言われますね。確かに、数学のバックグラウンドが強い人が10回前後の参加であっという間に青に到達みたいな事例も見られます。僕の持論ですが、これは半分正解で半分不正解と思っています（筆者は受験数学しかしてないので認識違いであればすみません）。というのが、実際AtCoderで数学の知識がそのまま使える問題はそこまで多くありませんが、数学の問題を解く時に求められる、問題を抽象化して適用できる公式を探すという思考方法はそのまま使えるからです。例えば、中学生の時に「5x=10」→「x=2」という一次方程式の解き方を習ったとします。これをそのまま覚える人は「3a=6」を解いてくださいと聞かれても「習ってないのでわかりません」となってしまいます。最初の問題をxだけの変形と捉えるか、そもそもxは代数で数の入れ物であると捉えられるかで、抽象度合いも違いますし、より抽象的に捉えられる方が、多くの問題に応用できます。あえて簡単な例を出して、抽象化の実例を挙げましたが、実際の問題でも、同じアルゴリズムを使って実装量も大差ないのにDifficultyが大きく変わることがあります。
例えば（以下ネタバレを含みますので先に解きたい方はご注意ください）、
AtCoder Beginner Contest 177 D - Friends
AtCoder Regular Contest 107 C - Shuffle Permutation
この二つの問題は同じアルゴリズムを使いますが、Difficultyは500以上違います。
177-Dの問題は、「グループ」とかいう言葉が出てきて、いかにもUnion-Findっぽいなーという空気が漂っているのでなんとなくACできた人も多いような気がします。上の問題がACできて下の問題がACできない人の違いこそ問題の帰着力の差だと思います。下の問題は、パッと見はとっかかりがないように見えますが、要素の重複がないので縦と横を分けて考えられることがわかります（縦と横が出てきた時に別々に考えられるか？と考えるのも結構典型的な思考パターンです）。また、swapできる行・列に辺を張るとみなすと、連結になってる行・列は自由にswapできることがわかります。ここまでできると、連結かどうかを管理するデータ構造→Union-Findというように帰着し問題を解くことができます。最大のポイントは「swap」を「辺を張る」に言い換えできるかということですがこれこそ問題をどれだけ抽象的に考えられるかということです。次以降で問題を抽象的に帰着する力をどうやって高めるか解説していきます。
2-4. 帰着力を高めるトレーニング
①同じジャンルの問題をまとめて解く
この精進方法を行うことで、各アルゴリズムが様々な問題に適用できることがわかり、問題の帰着力が高まります。また、帰着力を高めるには、各アルゴリズムをより抽象的な次元で理解する必要があります（１次方程式の例で示した通りです）。ただ、いきなり抽象的に考えるのは難しいので（数学的に厳密な定義・定理をいきなり理解しようとするとウッってなりますよね？）、具体例（具体的な問題）を考えながら気づきを得ていくこの方法がやりやすいと思います。茶色・緑で燻ってる人特におすすめしたいのが、レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】に挙げられている100問を解くことです。自分は80問ほど解きましたがかなり力がついた実感があります。かなり難しい問題もあるので、どうしても難しければ飛ばしてもいいと思います。
②同じ問題を別の解き方で解く
①の方法が縦串としたら②の方法は横串です。例えば、BFSで解ける問題は大体DFSでも解けます。また、尺取法で解ける問題も大体二分探索でも解けます。同じ問題を別の方法で解くことで問題を別の角度から捉えることに繋がり、問題の言い換え力、つまり帰着力が高まります。また、どっちでも解けると言いつつも必ずどっちの方が解きやすい（人によって変わるかもしれませんが）という解法があり、こういう問題ならこのアルゴリズムを採用するという指針ができ、スピードアップと確実性の向上に繋がります。僕自身、DFSよりBFSの方が理解しやすく、また尺取法より二分探索の方がバグらせずに速く書けるので、どっちでも適用できそうな問題が来たら、それぞれBFS、二分探索を使うようにしています。最近の発見としては、以下の問題（これもネタバレを含みます）で問題を帰着する方法を一つ学びました。
AtCoder Grand Contest B - Graph Partition
結論から言うとこの問題は「頂点集合に分離できるか」→「二部グラフ判定」の言い換えができるかを問う問題です。僕自身この問題を考えた時、「奇数長の閉路が無ければ分離できる」と考えましたが、コードが書けず解説を見て二部グラフを使う解法でACしました。ここで終わるのではなく、せっかくなので「奇数長の閉路が無ければ分離できる」と言う考えに基づくコードも書いてACが取れることを確認しました。
二部グラフ判定を用いた方法
奇数長の閉路の有無に注目した方法
見比べて貰えばわかると思いますが、二部グラフ判定を用いる方が簡単です。ただ、あえてこの作業を行うことで、次同じように奇数長の閉路に注目する解法を思いついた時、二部グラフ判定に帰着できるようになると思います。全ての問題でこういうことやる必要はないと思いますが、苦労して自力でACできた時などは、解説を見て、違うアプローチをとってるときはそっちも試してみるくらいからやってみるのがいいと思います。
2-5. まとめ
今までの話をまとめるついでに問題の考え方のフローを少し解説しておきます。
僕は、大体上のスライドのようなフローで問題を考えています。見て貰えばわかるように、④、⑥で正しく計算量を把握できること、②と⑤で問題を解ける典型アルゴリズムに帰着できることが鍵となります。①の分岐に入った時、②に書いているように何とか「もがいて」問題をわかる問題に帰着する方法を考えます。ここでは、計算量は度外視してとりあえず解けるアルゴリズムを考えます。考えた解答が計算量が間に合いそうならいいですが、間に合わなさそうなら⑤で書いてあるような方法で削減を試みます。中でも典型的なもがき方がこの記事(競技プログラミングで解法を思いつくための典型的な考え方)によくまとまってます。問題を典型に帰着する意識がなかった人ほど、一度見てみると得られるものがあると思います。
3.その他精進内容
2章で一部精進内容を書きましたが、その他やったことを挙げてみます。
3-1.JOI精進
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】でも結構JOIの問題が出てきますが、JOIの問題は特にDP・最短経路問題あたりの良問が多いです。僕自身DPがあまり得意でなく、Educational DP Contest / DP まとめコンテストもやったのですがいまいち定着できなかったのでかなり役立ちました。AOJ/AtCoder-JOIでは、問題がレベル別に並んでる上に解いた問題を管理できて便利です。茶色コーダーならレベル4かレベル5、緑コーダーならレベル5かレベル6あたりから解くのがいいと思います。
3-2.コドフォ精進
これはやっている人も多いのではないでしょうか。ただ、コドフォのコンテスト開催は深夜が多く、社会人には中々参加が厳しいです。Codeforces Anytimeを使うとバーチャルコンテストでも仮想のレーティングがつくので、緊張感を持って取り組めます。
3-3.チーム戦参加
最近、WUPCやKUPCなど大学の有志が開催しているコンテストに参加しました。3人1組で参加する形式で、他の人の思考パターンを学ぶいい機会になりました。僕のチームメイトは両方青コーダーだったので、あまりチームには貢献できませんでしたが、「次までには1問でも自分が解きたい」、「この人たちに追いつきたい」と思うことで、実力を伸ばせたと思います。
4.コンテストでの立ち回り
4-1.順位表を使おう
みなさんコンテスト中は順位表を見ますか？僕は見ます。ABCの場合は、大体Dまでは順位表を見ずに一生懸命速く解いて、解けたら順位表を見て、EとFを見て同じくらい解かれてたらFを解くようにしています。というのも、一定数は順位表を見ずに前から解く人がいる中で、Fが同じくらい解かれているということは、Fの方が簡単な可能性が高いからです。また、貪欲法で解けそうだけど証明がいまいち自信がないということがあった時は、順位表を見てかなり解かれていたり、WAの率が少ないとわかると思い切って提出します。ただ、この方法は正直力はつかないと思うので、コンテストが終わってからちゃんと解説を見て証明を理解する方がいいと思います。
4-2.問題文にヒントがあることも
これはそこまで汎用性はないですが、たまに使えます。最近だとHHKB プログラミングコンテスト 2020 E - Lampsの問題は、AtCoder Beginner Contest 129 D - Lampの問題を知っていると前処理はコピペで対応できます。最近のABCは正直出題分野が一巡した感があり、過去問をある程度認識していることも重要だったりします。またこの問題、AtCoder Beginner Contest 166 D - I hate Factorizationは、一見数学的な式変形が要るのかな？と思いましたが、問題文を見ると「因数分解は嫌い」とあり、何の保証もありませんが、高度な式変形よりは単純な探索で解けるのではないか？というあたりをつけるきっかけになりました。
4-3.計算量が怪しい時
計算量を把握しても、間に合うか微妙な計算量だと提出するか迷いますよね。そんな時は、自分で計算量が最大なるテストケースを作って、AtCoderページ上のコードテストにコードを提出すると、ペナルティーを犠牲にせずに間に合う保証を獲得することができます。
5.便利リンク集
ここまで、結構な数のWEBサイトを挙げてきましたが、それ以外で自分なりに参考になったものをまとめておきます。気になるものだけ見ていくといいと思います。
Pythonの引数における参照渡しと値渡しについて
・・・体系的にプログラミング言語について学ぶ機会がなかった自分にとっては、こういう言語の構造が中々わからず苦労しました。Python使いならまずマスターすべき内容です。
浮動小数点数オタクが AtCoder Beginner Contest 169 のC問題をガチで解説してみる
・・・オタクは特定分野に詳しいので神。冗談はおいといて最近頻出になった印象がある浮動小数点の扱いですが、これも体系的にプログラミング言語について学ぶ機会がなかった自分にとっては苦手分野でした。まだ得意とは言えませんが、怪しさに気づくことはできるようになってきました。
Python defaultdict の使い方
・・・ループを使いながら一度出てきたか判定する時によく使います。出てくる最大の値が$10^6$程度なら、ゼロで初期化したリストでも問題ないのですが、値が$10^9$までとる時には空間計算量がオーバーしてゼロでリスト初期化する方法は使えないのでdefaultdictが重宝します。慣れたらとても簡単で便利なので是非マスターして欲しいです。
「1000000007 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜
・・・modの処理は頻出ですがずっと苦手分野でした。この記事を読んで、フェルマーの小定理をお気持ちだけ理解できたので、だいぶ苦手意識が少なくなりました。