競技プログラミングを AtCoder で始めてからいつの間にか丸3年経っていたので、今後への決意のためにも振り返ることにしました。
ランクは半年で緑色→水色に上がりましたが、その後は停滞しています。一応は伸びているようで今は青色に片手が届いたくらいです。
TL;DR
- レーティングの変化が大きなモチベーションになり続いています。
- 勉強すべきところにきちんと取り組めば伸び、逆にダラダラ続けるだけ（解説を読んで復習する程度）だと伸びにくいという傾向を感じました。
- ランクは現在の実業務に対してはオーバースペック過ぎますが、境界値バグを防いだりなど主に正確性のほうで役に立っています。
取り組みスタイル
参加コンテスト
AtCoder の Beginner Contest (ABC), Regular Contest (ARC), Grand Contest (AGC) に極力毎回参加しています。
レーティングが上がると嬉しく、維持できればそれを実力と見ていいと自信になるため、参加時は常に rated にしています。「やるのに計測しないのは勿体ない」くらいの勢いです。疲れていたりしてパフォーマンスが出そうにないときも、それも実力の一部として受け入れています。（続ければまた上がりますし）
ABC はほぼ毎週開催されている上、最初の2～3問はウォーミングアップにできるので気楽にやれています。一方で ARC や AGC は閃けば1問解けるという状態で、まだ精神的にハードルが高いです。
使用言語
使い慣れていて好きな Ruby でやっています。現状のボトルネック（＆興味）は解法を思いつくことであり、言語の性能面の不利は気になっていません。むしろ Ruby で高速に処理する方法を身に付けたり楽しんでいます。
AtCoder ではスタックサイズが大きいので再帰しやすかったり、 Python の NumPy に似た Numo::NArray を使えたり、環境も良いです。
ただ、 C++ にあって Ruby に無いデータ構造（優先度付きキューなど）を必要とする際がきついです。
勉強方法
纏まった時間をとって基礎を固めるということがあまりできていません。コンテスト後に「解けなくて悔しかった」ものについて、解説を読んで知識を補強するということを繰り返しています。
個々のアルゴリズムはこの流れでも習得していけましたが、根本的に苦手な分野は苦手なままというのが身に染みてきました。
取り組み履歴
競プロ開始前
学生の頃は、情報学科にいたわけではありませんが、プログラミングはしていました。
- もともと高校数学は好きでした。
- 教科書の後ろにあったプログラミングを自習したのが、最初のプログラミング経験です。
- 大学では地球科学科にいました。
- 研究室で Fortran と Ruby を使っていました。
- データ解析や数値シミュレーションの関係で、計算量は感覚的に身に付きました。
- アルゴリズムを考えることはあまり必要でなく、離散フーリエ変換や行列計算などをライブラリでできれば十分でした。
- 就活では
通常の面接が苦手でpaiza のお世話になりました。- 競プロに近いことをしたのはこのときが最初です。
- 基礎的な最短経路問題やナップサック問題を解けるようには勉強しました。
AtCoder 開始
業務のチームメンバーから AtCoder について雰囲気を聞き、やってみようと思い立ちました。
- ABC なら名前的に大丈夫だろうと思ったらボロボロでした。
- paiza より難しい問題がすぐに出てきて、それ以上は手も足も出ませんでした。
- 数学的な表現が割と多い（数式そのものだったり言葉遣いだったり）のにも面食らいました。
- その後、コンテストに取り組むための環境を用意していきました。
- 使い方は知っていてもとっさには書けないコード（モジュラ逆数など）を準備しました。
- 紙のようになぐり書きして考えられるよう、安物の電子メモパッドを手に入れました。
こうして AtCoder に慣れていって、ランクは緑色で安定しました。
ACL などの勉強（1年目後半）
知識が明らかに足りていない部分について勉強を進めました。
- グラフの問題に挑めるよう、グラフの基礎を勉強しました。
- 特に「木」は性質が多く、問題にも頻繁に出るので、周辺の知識をかためていきました。
- C++ で "AtCoder Library" (ACL) を提供するということで、 Ruby でもついていけるよう勉強しました。
- まずは Ruby で使えるよう、とにかく ACL を模写しました。
- ある程度内容を覚えたアルゴリズムについては、 Qiita にアウトプットしてさらに理解が深まりました。（→最初の記事：セグメント木）
グラフの問題文が読めるようになったことで解ける問題が増え、ランクは緑色から水色に上がりました。
一方で ACL については、解ける問題は多少増えたはずなのですがレーティングは上がりませんでした（勉強していなければもっと下がっていたでしょう）。 ACL を想定した問題が増えたのに対し、それを適用できるかどうか見極める力がまだ付いていなかったことが要因だと考えています。
長い停滞期（2年目〜現在）
ACL の代用品を手に入れてからは、毎週 ABC に挑むのが中心になり、まとまった勉強はしていませんでした。
（この期間は1年程度だと思っていたのですが、今回振り返ったら2年以上ありました。）
- 動的計画法（DP）と数え上げの苦手ぶりが顕在化してきました。
- 解法を柔軟に思いつく力が弱くなってきたようにも感じています。
- ACL などのツールを使えないか考えることに囚われて、根本的に方針を間違えることが起きています。
- 始めた頃のコードを今回見返したら、なぜ当時解けたのかわからないものがちらほらありました。
- それでも解説で気になったアルゴリズムを新しく覚えると、次の機会に解けたりしました。
- こちらは逆に ACL のお陰で楽に習得できたものがあります。
総合的には成長しているようで、青色に届いたことも一瞬だけありました。
（他の競プロも挑戦）
途中で Topcoder と Codeforces もやってみました。回数が少ないので不正確なものの、 AtCoder と似た評価になりました。
しかし何かとハードルを感じ、結局 AtCoder 1本に戻ってしまいました。 AtCoder で物足りなくなったらまた挑戦するかもしれません。
今後
勉強面でたくさん伸びしろがあるので、きちんと取り組めばまだ伸びると思っています。
- 基礎から弱い分野
- 動的計画法（DP）
- 数え上げ
- ACL でまだうまく適用できないアルゴリズム
- 最大流・最小費用流
- 文字列に関するもの
- 畳み込み
- 2-SAT
今はランクが水色なので、青色を維持できるようになることが当面の目標です。欲を言えば黄色まで行きたいですが、果たして…。
ところで、実業務で役に立っているか
実業務ではアプリケーションの開発や保守をしていますが、求められることが競プロと異なるので直接は役に立っていません。
- 計算量を意識するほど要件が厳しくありません。 ABC のB問題が解ければ十分です。
- 保守性の高いコードを書く・設計をするには別途勉強が必要です。
- 何かしらのフレームワークを使うため、その勉強も必要です。
とはいえ間接的・副次的には役に立っています。
- 境界値など特殊ケースでバグを起こさないか、よく目が向くようになりました。
- ログなどをもとに問題の原因調査をするのも見当がつきやすくなっています。
- 課題に対して「解決法を考える力がある（はず）」という自信を持てています。具体的な実装はもちろん、設計から考えるようなときも。