AtCoder に辿り着いたのは僥倖でしたが、まだ私には使える言語がありません。そこで友人に尋ねてみると、Python をお勧めしてくれました。入門者用の本も、もう自分には必要ないからと譲ってくれました。これで準備は整ったので、基本的な文法や入出力の仕方を調べながら、積極的にコンテストへ参加していきました。当時の ABC はまだ 4 問で、個人の感触としては、アルゴリズムやデータ構造のちょっとした知識がないと難しい問題が C で出ると 2 問しか解けないけど、D に難しい問題が置かれたときに C までの速解きに成功すると一気に伸びるというようなものだったと思います。この時期はひたすら ABC の AB 時々 C を埋めていました。
水色になるまで
大学が春休みに入ったこともあり、アルゴリズムやデータ構造についてもう少し体系立った学習がしたいという思いから、『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』(通称:螺旋本)に手を出しました。また、この本のソースコードが C や C++ で書かれていたことや、参考にしようとした他の方のコードが C++ で書かれていることもあって、C++ をしようということになり、その前段階として結城浩先生の『C言語プログラミングレッスン』も一緒に読み進めていきました。
この螺旋本には好きなところが 2 つあって、1 つはコンテストでは直接出題はされないけれど、アルゴリズムを理解する上で基本で大切な題材を取り扱っていることです。初等的整列の章では普段自分が何気なくしているトランプや UNO の手札の整列がアルゴリズムとして与えられたことに感動しましたし、木の章では探索順序について理解を深めることで、多くの問題について解答を容易にしてくれたように思います。もう 1 つはコンテストで直接役立つ典型アルゴリズムを幅広く学べることです。グラフ上の様々な最短距離問題や動的計画法の理解についての取っ掛かりを得たのは有意義だったと感じています。
もう 1 つしていた練習として、~ ABC125 の水 Difficulty くらいまでの問題を周回するというものがありました。特に点数がついていないABC041 から前のセットは典型問題が多く、dp、尺取り法、いもす法、二分探索、累積和、木上の探索などの今でも即戦力で役に立つ武器があまり捻りのない形で置いてあるので、これらの問題を定期的に解き直して他の場面でも応用できるように練習しました。
そんな練習が功を奏したのかどうかは定かではありませんが、平成最後の ABC で水色になることができました。
与えられた数列のうち、色1で塗るものを a0,a1,...,alast とし、色2で塗るものをb0,b1,...,br としてみると、(色1の要素)(色2の要素)のように並べ替えた数列が非減少数列であるとは以下の条件を満たすことと同値である。i の普遍集合は整数とする。
・∀i ∈[0,last), ai ≦ ai+1
・∀i ∈[0,r), bi ≦ bi+1
・alast ≦ b0
数列に出てくる数がいずれも一桁であることと、三つ目の条件に注目すると、alast ≦ d ≦ b0 なる d が[0, 10)の範囲にしかないことがわかるので、あとはこの d に対して条件を満たす数列を構築できるか判定できればよいということになる。その判定方法のイメージは下の画像のように、与えられた数列を、[0, d]の範囲の数だけを含むようなaiと[d, 10)の範囲の数だけを含むようなbiに分離することである。