AtCoderで青色になるまでやったこと

長かった水色を抜け、目標の青に到達できたので青変記事を書きます。普段どのようなことを意識して精進してきたかについて記します。

プログラミング歴

プログラミング歴は7年ほど、競技プログラミングを始めたのは2年2ヶ月前です。AtCoder始めてから最初の１年間はPythonで、それ以降はC++を使ってきました。

精進

AtCoderにはたくさんの良質な過去問と解説があるので、これを解くのが一番ですね。Recommendationでは自分にとっておすすめの問題を提案してくれるので、そのSolve timeと競争しながら精進しました。

ただ自分のレベル以上の問題になってくるとなかなか解けなくなってきます。過去問を1,000問埋めるくらいまでは、手が止まって10分経ったらすぐ解説を見ていました。この段階まではアルゴリズム自体を知らないことや解法の引き出しが揃っていないので早めに解説や他の方のコードを見るようにしていました。1,000問埋めたあたりで一通りのアルゴリズムを知ったら、それ以降少しずつ解説見るまでの時間を伸ばしていき今ではできる限り見ないように、時には1日以上考えることもあります。

- 解説見るときは１行ずつ

早めに解説を見ると言っても、一気に全部は読まないようにしていました。自らのレベルを上げるということは、すなわち解ける問題と解けない問題の境界線を上げていく作業です。一気に解説を見て「その方法でやれば解けたのか〜」だと自分の本当の力にはなりません。少しずつヒントを見て、そこから自分の頭で考えてなんとか解く、また解けないにしても次の手がかりを探すことが精進だと思っています。また知らないアルゴリズムでも、ヒントを見ながらなんとか自分で解こうとすることで理解も一層深まるし、アルゴリズムを知れた感動も大きくなります。

- レーティング上げるには自分と同じ色か一つ上の色

水色だった一時期、黄色diff以上の問題を毎日のように解いていたことがありますが、結果的にはレーティングは変わりませんでした。考察力は上がったと思いたいし、難問の解法を知るのは面白いのですが、レーティングを上げようと思えば自分と同じ色か一つ上の色の問題を解くのが効果的だと思います。

- 苦手分野は何度も同じ問題を解く

分野によっては、一度解説ACをしてもなかなか身に付かないことがあります。そのような時は1ヶ月経ってまた同じ問題を解くようにしました。記憶を定着させるのに、忘却曲線から導かれた最適の復習のタイミングがあるように、考察の方法も時期をずらして何度も復習すると必要な時にすっと用いることができるようになります。

- アルゴリズムのイメージを掴む

水、青diffくらいからは、前処理をしてから複数のアルゴリズムを組み合わせて解くようなことが増えてきます。そのため、自分の知っているアルゴリズムをいつでも引き出せるようにしなくてはいけません。

最後の一手で二分探索を使えば計算量が間に合う問題を2,3回落とした時に、なぜ二分探索を知っているのに使いこなせなかったのかと考えました。アルゴリズムに はっきりとしたイメージを持っていなかったため、単体では使えるけど、他のものと組み合わさると思いつきもしなかったのです。それ以降、アルゴリズムに自分なりの命名をしてイメージをはっきり捉えるようにしました。例えば二分探索なら、丸太から薪割りしていくと10回で一枚の薄い紙になるイメージを持ち、それから二分探索が関わる問題を逃さなくなりました。

話は変わりますが、数学の定理やアルゴリズムに発見者（発明者）の名前が付いているのは、その方の功績を讃えるためだと思うのですが、それを使う側にとっては中身をイメージできる名前で覚えた方が良いと思っています。鳩の巣原理なんて名前を聞いただけで理解できますからね。

考察

難しそうな問題では、ノートに簡単な図や数式を書いてそれをブックスタンドに置いて、そのノートを見ながらコーディングしていました。PCのディスプレイと同一平面上にあるのが自分の好みです。

自分と同色の難易度の問題が解けなかった時は、なぜ解けなかったのかを徹底的に考えました。

- グラフで1つの頂点を複数の状態に分ける(ダイクストラ法とのコンボ）
- 何と何を同じデータとしてまとめられるか(dp)
- 答えに対する貢献度
- 余事象と逆順は常に頭に入れておく

アルゴリズムと同じように、はっきりとしたイメージを持つようにしました。

なぜ解けなかったのかを考え、次回以降のコンテストで解けるようになることは、競プロやっていて一番楽しい部分だと思います。

バーチャルコンテスト

1400~1500くらいのレーティングで１年以上停滞していた状態から青までレーティングを上げられた要因は、本番と同じ緊張感で臨めるバーチャルコンテストだったと思います。

8月から朝活、９月から「くじかつ」にそれぞれ毎日のように参加し始めてからパフォーマンスが安定しました。

一人で解くより、他の方と一緒に同じ問題を解くのは大きなモチベーションとなりますね。易しめの問題を確実に早解きする力も毎日のバーチャルコンテストで磨かれました。

プログラミング言語

PythonからC++へは、予想していたよりはスムーズに移行できました。きっかけは青diffのdp問題で何度かTLEが続いたことです。Pythonの上位勢は、JITコンパイラNumbaなどのライブラリを使いこなしていますが、それを習得するよりはC++を学習しようと思いました。

1ヶ月以上思うようにコードが書けない状態でしたが、そんな時もコンテストのパフォーマンスは大きく変わらなかったです。競プロはプログラミング言語の違いより、考察力や実装力で競っているんだと感じました。

２つの言語で競プロに取り組んだことは今考えれば得るものが多かったです。それぞれの言語の上級者のコードを読む機会が増えるし、言語毎のライブラリを習得するのは、アルゴリズムの理解を深めることに繋がるからです。

ただC++を読めるようになると、解説放送も蟻本などの書籍もさらに面白くなるのは間違いないと伝えたいです。

まとめ

今まで色々な方の色変記事を読んで参考にしてきました。この記事も他の方の参考になれば幸いです。

橙や赤以上の方達から見れば、レーティング1,600はまだまだのレベルですし、黄diff以上の問題を解いていると競プロで面白いのはここからなのではないかという気もしています。ここまでは典型を習得しているだけで、ようやく本当の意味での考察をするスタートラインに立てたのかもしれません。10月からはしばらく他の学習で忙しくなりますが、また青以上を目指す道を歩みたいです。