リクエストを受けたので、最近流行りの「○○色になるまでにやったこと」記事を書きたいと思います。
自分の現在の位置について少し話すと、AtCoder 青上位・ Codeforces 青中位・CSAcademy 青中位・ TopCoder 青下位くらいです。全身青いです。近いうちに青卒業できるように頑張っているところです。なので「青色になったので書いている」わけではないのですが、青を目指している人々にとって参考になる記事になっていれば幸いです。
水色 → 青
これは Twitter などでもよく言われていることなのですが、 AtCoder の ABC / ARC の D がコンスタントに通せる ようになると青が見えてくると感じています。問題セットにもよるので一概には言えませんが、 C 問題は呼吸、 D 問題は最低でも 20 分以内には片付けたいところです。なので、コンスタントに通すにはどのような力が必要かを知りたい気持ちになってきます。
適当に過去問を眺めた範囲だと、よく使われているアルゴリズムは以下で紹介するものたちかなあと思っています。
- 二分探索、尺取り法
- 最短路アルゴリズム (ダイクストラ、ベルマンフォード、ワーシャルフロイド)
- 全域木アルゴリズム (プリム、クラスカル)
- 動的計画法
- ゲーム系 (2 人で行うゲームであって、メモ化が可能・もしくは小さいケースを試すと定数時間に帰着できるものが多い)
競技プログラミング関連の書籍で、最初の方に扱うトピックが多いなあと感じる方も多いと思います。実際その通りです。個人差は勿論あると思いますが、 基本的なアルゴリズムをいつも適切に適用できる ということは意外にもそれほど簡単ではなく、この力を十分に養うことができればおそらく青になれるでしょう。
また、上の箇条書きでは挙げていませんが、 ad-hoc な考察が必要になることが多々あります。つまり、特別なアルゴリズムを知っているかどうかの知識問題ではなく、考察問題がよく出るということです。ですので、出題された問題に対して適切な考察をできるだけ早くする能力も必要かなあ、と思っています。
トラブルシューティング的な何か
青になりたいけど、なかなか前に進めない・・・という方は多いと思います。そこでちょっとしたトラブル―シューティング的な何かを書くことにしました。もし「当てはまってるなあ」と思うことがあれば、弱点を克服していきましょう。
実装が簡潔でない
「なんか実装がひどいことになったなあ」となる経験は誰しも一度はしたことがあると思います。 ICPC で出るような重実装の問題とかだとどうしてもそのような実装になってしまい仕方ないみたいなパターンもあるにはあるのですが、たいていは「実装方針が悪い」だけで、本来ならばもっと簡潔に書ける場合が多いです。
ではどのように簡潔に書けるようにするかというと、他の人のソースコードを読みましょう。上位陣は無駄がなく簡潔なコードを書く方ばかりですので、順位表の上のほうのソースコードを意識的に見るようにすると良いと思います。まあ当たり前なんですが変数名が意味不明とか spacing がなんか嫌とか出てくるのはもう仕方ありませんが、見ないよりはマシですしたくさん読んでいるといつかは読みやすいものが見つかるのでたいてい大丈夫です。 (個人的な話をすると、 tourist のコードが結構読みやすいのでコンテストが終わったらこっそり見るようにはしています。)
考察・実装に時間がかかる
「自力で解けたが考察に時間がかかった、実装に時間がかかった」、よくあることですね。自分も毎日これをしていて人生が終了しています。
これをどう解決するかですが、おそらく 数をこなすしかありません。数をこなすとそれだけ考察の引き出しが増えるので、無駄な考察を経由する確率は低くなっていくと思います。実装に関しても同じで、「こういう処理をやりたいときはこう書く！」というものが自分の中で確立されると迷うことなく書けるようになると思います。
ちなみに、自分は青になるまでに ABC を C まで、 ARC を B まで全部埋めました。それから青になってから ABC の D も全部埋めました。効率の良い方ならもっと少ない練習量でも青水準の技能が身につくかもしれません。
考察ができない
そもそも解説に書いてあった考察ができていなかった、というケースも結構あると思います。
これについては、どのような思考プロセスを踏むとそのような考察になるのかをよく考えて、自分のものにする 必要があります。解説を見ながらよくわからないまま通した問題は後で見返した時に十中八九解けなくなっているので、取り組むのであれば時間がかかってもちゃんと考えながらやったほうが良いと思います。
また、「この考察って他にどういう問題で使えるかな？」「問題設定をこう変えても・こう作ってもうまくいくかな？」と、脳内で類題を作ってみる のもオススメです。わからなかった問題で得た知見を他で応用する癖があると、解ける問題の幅が広がると思います。
誤読をする
問題文を読みましょう。 (雑すぎるだろ)
まとめ
いろいろ書きましたが、つまり何が言いたいかというと、青になるために特別なアルゴリズムはあまり必要ないということです。もちろん知っているに越したことはないのですが、それよりも考察力を磨いたり、与えられた問題に対して適切に素早くコードを書く、ある種の瞬発力のほうが求められていると思います。
コレ以上書くと、黄色になりました記事のネタが切れるので、このへんにしておきます。何か聞きたいことがありましたら Twitter でいつでもリプライを飛ばしてください。
