AtCoderで青になるまでにやったこと
一年一ヶ月ほどの苦心の末、ようやく青コーダーになりました。感慨深いです。
全く独自性のないブログタイトルですが、なるべく他の人が書いてないことを書くようにします。胡散臭い箇所はスキップしてみてください。
- Rustを習得した
- 知っているアルゴリズム増やした
- 問題を解いた
- 苦手問題を克服した
- コーディング時のボトルネックを調査した
- ボトルネックを改善した
- ルーティンを決めた
- 統合開発環境を開発した
- 今、壁にぶつかっていると感じている方へ
Rustを習得した
職場では主にC++を書いているのですが、仕事で書いている言語を家で書きたくないという思いもあり、モダンでC++並の速度が出る、ということでRustを選択しました。
所有権などコンパイルが通る条件は他の言語より厳しいですが、慣れてくるとまあこんなもんかとスラスラ書けるようになってきて、今では仕事で書いているC++よりも速い速度でコーディングできている気がします。
やっぱりタプルとか構造化束縛とかパターンマッチングとかイテレータは便利です。
知っているアルゴリズム増やした
水から青になるまでに、最大流、セグメントツリー、Binary Indexed Tree、平方分割、Grundy数あたりをラーニングしました。
ただ、知識だけでは上がれなくて、アルゴリズム活用力なるものが上がっていないと青に進めません。
というか最大流と平方分割とBITはまだ一度も本番コンテストで使ってないです。
問題を解いた
まあ誰だってやってるんですが必要なことです。
青になった時点での解いた問題数は400問くらいです。
解くだけでなく400点以上の問題は解いた問題でも解説を読むようにしました。たまに自分の解法と違ったりよりエレガントな解法が解説に書かれたりするからです。
(水色からは正直ABCのA-Cはやるだけになってくるので解説は読みません)。
勿論、解けなかった問題を解説ACしたりすることは重要です。
苦手問題を克服した
私の場合、苦手問題はDPとゲーム系問題でした。
特にDPは多くの人が壁にぶつかるのではないでしょうか？
はまやんはまやんはまやん様のところで、いろんなジャンルの問題がまとめられているので、それを解くようにしました。
後半は難しいので、全ては解いていませんが。
『DPとわかっている問題』を解けるようにしないと、『DPかどうかわからない問題』は解けるようにならないです。
まとまった数のDP問題をやることで、制約的にDPっぽいとか、DPでやろうとするとこうなるから無理みたいな感覚がついて、DPと戦えるようになりました。
コーディング時のボトルネックを調査した
これが昇格の決め手になった気がします。
練習問題で問題を解いた時、毎回あっさり解けるわけではないですよね。
むしろコンフォートゾーンより上の問題を解いている時は、どこかで詰まるものです。
高度な問題で考察に時間がかかるとかはある程度仕方がないですが、考えておくべきコーナーケースでWAしたり、配列の境界値を誤るなどのバグが入ったり、
booleanが反転していたり、32bit整数がオーバーフローしてたり、つまらないミスが案外ボトルネックになっているので、ワードファイルにこれらの失敗の記録をするようにしました。
これを敗北ノートと呼んでいます。
ボトルネックを改善した
敗北ノートをまとめた結果、特に頻発するミスについては習慣を決めたりして再発しないようにしました。
- コーディング規約を決めた
例えば、複数あるRustの整数型のうちusizeとi64のみを使い、usizeは添字になりうる数字のみに使うようにしました。
また、グリッド系の問題では配列の添字は問題で与えられている条件に関わらず必ずgrid[y][x]の順とし、原点(0, 0)を左上にするなど、
いつものスタイルを確立することでバグを生まないようにしています。
- ライブラリを整備した
当たり前ですが、ググってライブラリを探すより、使い慣れているライブラリが手元あったほうが何十分もタイムを短縮できることがあります。
また、ライブラリがバグっていると、デバッグで大幅に時間をロスすることになります。
正しいライブラリを揃えるのは勿論、テストコードをつける、使い方をコメントすることにしました。
- ホットスポットで集中するようにした
例えば意外とコピーアンドペースト時に一部置き換え忘れなどのミスをすることが多いことに気づきました。
そういったミスりやすい瞬間をホットスポットと呼ぶことにしました。
こういった場所を半分無意識でやると危険なので、コピーアンドペーストをするときは、『こことここを変える』というチェックリストを脳内に作ってから、意識的にコピペするようにしました。
勿論コピペが大きくなる時は関数化したりループ化してなるべくコピペしないようにしています。
ボトルネックの調査と改善をやると解答時間が安定するようになりました。
ルーティンを決めた
イチロー選手がルーティンを取り入れることで集中力を高めているという話は有名です。
競技プログラミングも競技ということで、ルーティンが取り入れることで、集中力が発揮された状態を作りこむということを試みています。
具体的には、コンテスト前はベートーヴェンのテンペストを聞きながら、ローズマリーとミントをブレンドしたハーブティを飲むようにしています。
ローズマリーは短期集中力と記憶力が上昇すると言われています、効いているかはわかりません。(論文はあるらしい。)
ただまあ、リラックスしていい感じの状態は作れています。
カフェイン飲料を飲むのが手っ取り早いかもしれませんが、競技プログラミングは夜開催されることが多いですし、眠れなくなると健康によくないので、夜カフェインは飲みません。
統合開発環境を開発した
これが回り道だったのか近道だったのかわかりませんが、楽しい道のりではありました。
競技プログラミング専用の統合開発環境（統合競争環境？）というのはあまりなくて、ブルーオーシャンを開拓している感じがあってよいです。
最近はブラウザをくっつけて、問題ページに行った時には自動で入力ケースと出力データがダウンロードされるようにしたりしています。
ツール開発は精進に飽きていた時に気分転換にもなります。
動作が安定していない頃は競プロの問題を説いている最中に、環境の方のダメな動作が気になって、いつのまにかそっちの開発に移行している、、みたいなことも結構ありました。しゃーなし。
とはいえ今では心強い自分の相棒になってくれています。
今、壁にぶつかっていると感じている方へ
各々の素養によって伸び率は違うんですが、間違いなく言えることは『競技プログラミングを続けていれば、どこかでは必ず壁にぶつかる』ということです。
私の場合最初の10回くらいはぐんぐんレートが上がってて(レート補正の効果もあるんですが)、ちょろっとアルゴリズムを覚えたら解ける問題が増えたりして楽しかったです。
しかし、練習をしてても伸びない時期、前日有休を取って準備してまで挑んだのにレートが下がったコンテストなど、水色になってからは苦しい時期がありました。
敗北ノートをつけたりして手探りを続けてるうちに、なんとか解答時間が安定して青パフォが出るようになりました。
ぶつかった壁を乗り越えること、そしてそれまでの過程、それが競技プログラミングを続ける真価なのかな、と思います。
ぜひ焦らず壁を乗り越えてみてください。私もこれからまた次の壁にぶつかると思いますが、もうしばらくはなんとかやっていきます。