0 はじめに
0-1 自己紹介
こんにちは、橘諸兄です。中二です。
競プロ歴は一年強で、AtCoderは水色でRatingは1213(執筆時現在)です。
使用言語は主にPythonで、問題によってはC++を使ったりもしています。
0-2 この記事について
僭越ながら、個人的な振り返りを兼ねて私の入水への道についてこの記事で話したいと思います。
あらそうですか程度でお聴き頂ければ幸いです。(恐らく参考になる場所は多くないです)
まとめると完全な自伝です。
不器用で忘れっぽいので色々欠陥があるかもです。
知らない方の為に説明をしておくと、競技プログラミングのサイトにAtCoderというものがあります。そこでは莫大な量のコンテストが開かれており、その過去問がAtCoder Problemsに載っています。
精進とは競技プログラミングの練習・勉強を意味します。競プロ界隈で使われる言葉です。(多分)
1 競プロへ入門
中学に入学する前、小6の3月くらいにPythonを始めました。
Pythonを触りたくてPCをいじる部活に入りました。中1の5月くらいです。
そこで、競プロをやってみるといいよと先輩に言われたのでAtCoderを始める事にしました。
AtCoderを始めたのは競プロ目的ではなく、Pythonを触りたかったからという感じです。
始めてみましたが、使用言語がPythonだったのでAPG4bにはまず文法説明が載っておらず、部活内でもPythonをメインに使用する人は殆どいませんでした。その上、Pythonを始めてから半年も経っていないような状態でしたので、全く文法が身に付きませんでした。
(そんなこともあり、今はPython版APG4bの執筆を考えています。公開は2ヶ月先くらいでしょうか。)
2 初コンテスト
私の初コンテストは、アカウント作成の3ヶ月弱後の中1の7月末にあったABC211でした。
その頃は、アルゴリズムや計算量はおろか、AtCoder Problemsさえも知らず、ろくな精進を行っていませんでした。
そのコンテストが実装力を必要とせず、貧弱な実装力でも2冠はできました。C問題はDPが出題され、アルゴリズムをやっていなかった為、見事に終了。
約1ヶ月後、同級生からAtCoder Problemsと精進について教わり、本格的に精進を始めました。
3 精進開始
精進を始めてから、まずAB問題を埋め始めました。同級生がやっていたので始めた感じです。A問題はC++の練習の為にC++で書いていました。
並行して、C問題も埋め始めました。
そこで色々なアルゴリズムを学ぶ訳ですが、大槻兼資氏の「問題解決力を鍛える! アルゴリズムとデータ構造」という本を買いました。分かり易い絵で説明されており理解に役立ちました。
全18章より成り、そのうち15章を読み込むだけで、水コーダーに必要なアルゴリズムの殆どをカバーしているらしいです。
最初のうちは、主にA,B問題をそれぞれ一日10問程埋めており、中々C問題を埋められていませんでしたが、精進開始から2ヶ月程経った11月にはやや安定的にC問題を通せるようになりました。
以下は私が入茶までに習得したアルゴリズムなどです。
・全探索
・bit全探索 順列全探索
・簡易的なDP
・簡単な二分探索
・辞書型で $O(N^2)$ を $O(N)$ に短縮
4 茶コーダー
入茶したのは中1の11月です。
C問題とD問題の難易度の差がとても大きかった回で、38分での三冠でも緑Perf上位が取れました。
しかしここからコンテストへの参加を渋るようになりました。
その頃、私は冷えたことがなかったこともあり、冷えることを恐れていました。
入茶した直ぐにひどい冷えを味わいたくなかったので、コンテストには出ませんでした。定期テストなどもあり、精進もあまりしなかった覚えがあります。
明確には覚えていませんが、BFS,DFSなどグラフ理論についての問題は面倒だった為(ヲイ)中々勉強しなかった記憶があります。
そこから1~2ヶ月程競プロから離れました。
翌年の1月、定期テストや課題からも解放され、精進を再開しました。
グラフ問題も緑Diff前半くらいまでなら通せるようになり、前述のアルゴリズムの本に載っているアルゴリズムを大方勉強しました。
以下が私が入茶から入緑までに勉強したアルゴリズムなどです。
・BFS、DFSなどグラフ理論に関する問題
・queueとstack
・やや本格的な二分探索
・累積和
・やや難しいDP(ナップサックなど)
・優先度付きキュー
・UnionFind
・数学系の問題
5 緑コーダー
入緑したのは中1の3月末です。
コンテストの参加を渋っていた中で沢山精進を積んだので、茶前半から緑まで6回で辿り着きました。
精進した甲斐を感じとても嬉しかったです。
そこから熱心に精進を積むようになりました。
少しずつではありますが、レーティングは1000まで到達しました。
以下は入緑からここまでに勉強したアルゴリズムなどです。
・最小全域木問題
・ダイクストラ法
・簡単な確率などの数学問題
・尺取り法
6 スランプ
実はここまで私のレーティングは単調増加、つまり冷えたことがありませんでした。
しかし当然冷えが訪れました。(中2の6月)
その時の精進方法はこのようなものでした。
・RecommendationのModerateのABC問題を埋めていく。
・解けなさそうだったら後回し。
これだと得意な種類の問題が得意になるだけで、苦手な問題の克服ができません。
このような精進をずっと続けていたので、思いつく解法が偏り、1日に通す問題数も少なくなりました。
冷えつつもなんとか運で耐えて1113までは辿り着きましたが、ここからが地獄でした。
3回連続で冷えたり、暖まったと思ったら冷えたりを2ヶ月程繰り返し、病みました。
精進方法だけでなく、精神状態も起因していたのでしょうが。
行っていた精進方法を改め、一度見た問題は基本諦めずに考え、それでも無理なら解説を見る、という精進をしたり、個人用バチャを作って時間をかけて解くなど、精進を積みました。
(これくらい普通だろ、という話かも知れませんが私は不器用なので変な精進をしてしまっていました。)
それでも少し冷えましたが、これでようやくスランプから脱却できました。
7 念願の入水
中2の10月1日、ようやく入水できました。
前述の精進方法で、水Perf中間くらいの、当時の自分には難しすぎるくらいの問題を時間を掛けたり解説を見たりして沢山通しました。
それにより、自分が知らなかったアルゴリズムや実装の工夫も習得できました。
以下はスランプの状態から入水時(ほぼ現在ですが)までに精進で習得したアルゴリズムです。
・bitDP、桁DPなど高難易度DP
・半分全列挙
・01BFS
・二分探索(再履修)
・グラフの高難易度問題
・メモ化再帰
・クエリ処理の工夫
・ゲームの最適化問題
・やや考察を必要とする問題
・セグ木、セグ木を利用したクエリ処理
・その他諸々
8 これから
これからも今までと同じように有益な精進を行っていきたいです。
RollingHashやダブリングなどアルゴリズムやFenwickTreeなどのデータ構造も勉強したいです。
又、数学的考察力を身に付けARCも強くなっていきたいです。
そして...
このStreakを切らさず毎日精進を続けたいです。
このStreakは入緑してすぐに始めたもので、そろそろ半年になりますね。(執筆時現在)
又、あと2週間程で、今続いているStreakに入っている「精進した日」が「これまでに精進した日」の半分を占めるようになります。
9 さいごに
最後までお読み頂きありがとうございました。
私の精進方法は必ず全ての人に有効という訳ではありません。自分なりの精進方法を見つけて下さい。
これからも精進を欠かさず、入青を目指したいです。
―できれば単調増加で。
-1 おまけ
レーティング変動
停滞辛い...
精進グラフ
そろそろ入青しちゃいますねw