【AtCoder】プログラミング未経験からのんびり続けて青コーダーになった話

はじめまして、chimakiです。先日のARC167にて念願の青コーダーになれたので、今までやってきたことなどをまとめて書いてみました。

簡単な自己紹介

• Twitter: chimaki_yama821
• 数学系の学科に所属している学部4年生
• 競プロ以外はプログラミングをほぼしない
• 使用言語：C++

競プロの存在は高校生の時にTwitterで知りました。「なんかめっちゃすごそうな人たちが難しそうなことツイートしててかっこいい！！」みたいなことを思いながら、大学受験終了後にAtCoderに登録して競プロの世界に飛び込みました。

水色になるまでにやったこと

あまり正確ではないかもしれませんが、各種色変のタイミングまででやっていたこと・できるようになったこと・できなかったこと　などを簡単にまとめました。

〜茶

競プロやるぞ！と意気込んでいたはいいものの、高校の授業でBasicに触れた程度で何も知らなかったので基本的なところから勉強する必要がありました。やってよかったのはこの辺のはず：

• APG4bの1, 2章と3章の一部
• AtCoder Beginners Selection
• けんちょんさんの記事

特に、APG4bについてはとてもわかりやすくてしばらくはこのページを辞書がわりに使いながらコードを書いていました。

できるようになったこと

• if, for文の記述
  FizzBuzzがさらっと書ける程度には。APG4bの演習問題もやったのが良かったです。
• 配列の扱い
  APG4bに載っていた関係でずっとvectorを使ってました。
• 計算量の考え方
  APG4b-2.06を参考に、製薬に対してどのような計算量での解法が求められているのか考えられるようになりました。TLEになった時に原因がわかるようになりました。
• sort
  APG4b-1.14では標準ライブラリの関数紹介があるのですが、このうちsortが非常に便利でした。sortがどのような実装になっているのかは今も知りません。

個人的な感触としては、sortと計算量の話のおかげで頑張って考えればABCのCくらいまで解けるようになりました。

できなかったこと

競プロに限らず、「難しい本を読めば効率よく勉強できる」「難しい問題を解けば色々吸収できる」「難しいことやってる自分かっこいい」 と思いながら背伸びをし過ぎて何も得られず...ということをよくやってしまいます。ここでは、

• 蟻本を買って読んでみる
• EDPCに挑戦してみる

ということをしていたのですが、あまり身につきませんでした。

---

〜緑

茶色になるまでのコンテストで緑中盤くらいのパフォーマンスが出ていたので、あっさり緑までいけるかな〜と思っていたらなかなか苦戦しました。やったこととしては、

• AtCoder Problemsで茶・緑の問題を解く
• DPの問題を色々解く
• ABCの過去問を解いて解説放送をみる

という感じでした。

できるようになったこと

• 簡単目なDFS, BFS
  DFS（というか再帰関数）が苦手だったので集中的に特訓しました。
• bit全探索（APG4b-3.05）
• set, map
  これかなり大きくて、ABC-C,Dあたりの問題の勝率がset覚えてからとても上がりました。
• UnionFind
  蟻本で学んで、使いやすいデータ構造だなぁと感じていました。
• 超基本的なdp
  コンテスト中に自力でdpが書けた時はめちゃくちゃ嬉しかったです。
• combination
  解説放送でsnukeさんが書いていたのをコピペして使ってました。高校数学が行かせて嬉しい。

できなかったこと

茶色までの欄に書いたことと基本的には同じです。あとは、グラフ問題に対して全くアプローチできませんでした。Dijkstra法とか、何もわからず。

---

〜水

緑に入ってからしばらくして、少しモチベが下がってしまったのであまり競プロに時間をかけなくなりました（レートのグラフを見ると明らか）。途中で少し復帰したのを除くと約1年ほどは休んでいたと思います。復帰したきっかけは、

• 応用情報の試験勉強からの逃避
• 大学の友人がやっていた蟻本の勉強会への参加

です。やらなきゃいけないことから逃げてやることが一番楽しいのだ。

で、水色になるまでには色々なことをやったのですが、

• グラフアルゴリズム（ダイクストラ、最小全域木　など）の勉強
• bitDPなどの少し難し目のDPの勉強
• 典型90問の一部
• 水diff問題にチャレンジしてじっくり考える
• E8さんの記事：特に精選100問

というのがメインかな、と。特に、水diffの問題をじっくり考えて解くのが楽しくて、ためになったと思っています。Highestが黄色の友人に問題を出してもらって解いたりしました。典型90問に関しては、難しい問題が多くて挫折......

できるようになったこと

• 再帰関数などでバグらせずパパッと書ける
  何度も苦しんだ結果、スムーズに書けることが多くなってきました。まだ伸び代はあるけれど。
• priority_queue, multisetなどが使えるように
  この辺の便利なコンテナを少し使えるようになってきました。
• 半分全列挙、しゃくとり法、二分探索
  問題に応じて適切な解法を考えることと、その実装をスムーズに行うことができるようになってきました。

この頃にようやく蟻本初級編と中級編の一部を理解できるようになってきました。

できなかったこと

• バグらせずにダイクストラを書く
  なんとなくのノリで書いていたので、無限ループにしてしまったり、正しい解が出てこなくなってしまったりすることが多々ありました。（というか毎回やらかしていた）
• セグ木の理解とACLの使用
  ACLは環境構築が全くわからずに使えませんでした。自分でセグ木を（蟻本を写して）実装したりもしたのですが、問題を解くのに使えるほどには理解できていませんでした。
• 大量の問題演習
  これはどの時期でも言えることなのですが、適正難易度の問題を解く量が少な過ぎて典型的なテクニックを知らないので苦戦することが多かったです。

青になるまで

水〜青までにやったこと

1. 水・青Diffの問題を解く

この期間は今までに比べてたくさんの問題を解きました。水色になった2022/8/27と青色になった2023/10/15での解いた問題数がこの画像のとおりです。


青・水Diffの問題をたくさん解くことを意識していました。約1年で500問ほど解いていて、その中でも特に黄16問・青52問・水97問で力がついた気がします。黄Diffの問題はほとんどが解説AC、青Diffの問題は7割ほど解説AC、水Diffの問題は約半分が解説ACでした。解説ACした問題の解き直しなどは基本的にしていません。

また、この頃は緑Diffの問題は安定して解けるようになってきたのですが、速度が足りないと感じていたため青・水の問題で詰まった時などに取り組むようにしていました。

2. AtCoder Library(ACL) を使えるようになる

全ての機能ではなく、modint, segtree, dsu, fenwicktreeを使いました。modintとdsu(UnionFind)は元から自分で用意していたのであまり変わらなかったのですが、segtreeとfenwicktreeには非常に助けられました。内部の仕組みについては全く理解せず、使い方だけを覚えました。

個人的に、fenwicktreeは「setを使ってst.find(key) - st.begin()みたいなことをしたい（これはsetだとできない）」時に使えるという印象があります。

3. 勉強会・バチャ

「蟻本の輪読をする」ということで始まった自主ゼミで、過去のABCのバチャをやったり典型90問やその類題を互いに解説し合うなどしました。これをやって一番良かったのはモチベーションを保ち続けることができたことで、毎週大学に集まって競プロ関連のことをやることによってその時間だけでなく1人でも問題を解こうという気持ちになりました。

---

できるようになったこと・まだできないこと

現時点でそこそこ使えるようになったアルゴリズム・データ構造は次の通りです：

全探索, 二分探索, 動的計画法, ダイクストラ法, ワーシャルフロイド法, クラスカル法, 累積和・imos法, 座標圧縮, 半分全列挙, 行列累乗, modint, combination, UnionFind, SegmentTree, FenwickTree

ダイクストラへの苦手意識があったり、二分探索の問題がうまく思いつけなかったり、bitDPが思いつかなかったり、桁dpでバグらせたり......と課題はまだありますがそれは今後頑張ります。

一方で、現時点で少し勉強したけど実際に使えるほど理解していないことは次のとおりです：

フロー, Grundy数, ダブリング, 強連結成分分解

蟻本の解説を読んだり、問題の解説で知ったりしたのですが、まだ初見の問題に対してこれらを使って解くということができていません。

また、全くわからないけど今後勉強していきたいというのは次のとおりです：

LazySegmentTree, Mo's Algorithm, 文字列アルゴリズム（Z-algorithmなど）, Rolling-Hash, 形式的冪級数, 幾何

これらはコンテスト終了後のTwitterなどでよく見るので早めに勉強していきたいです。

総括

とにかく問題を解くのが大事！

振り返ってみて、大量の問題を解くことの大切さを再認識しました。正直、始めた頃は「あまり問題を解かずに高いレートに到達できると地頭良さそうでかっこいいだろ」みたいなことを考えていたりもしましたが、今思うとほんとバカだな〜って感じです。

一番しんどかったのはDP・グラフアルゴリズムなどを新しく勉強した時。まともに使えるようになるまでは余計なことを考えてしまうようになって、勉強する前よりむしろ問題が解けなくなってしまいました。 「インプットとアウトプットの割合は3:7がいい」 とかよく聞きますが、競プロに関してはそれ以上にアウトプットの割合を高くしていった方がいいように思います。

競プロをやって良かった！

競プロのおかげで世界が広がりました。特に良かったのは次の3つです。

1. プログラミングが好きになった
   　C++の難しい機能や他の言語のことは全然わかりませんが、競プロで「問題から考察して実装できる形で整理して考える」ということを繰り返し行い、たくさんコードを書いたことでプログラミングが好きになり、少しだけ得意になりました。おかげで今年の夏休みは2ヶ月間のインターンにも参加することができました。

2. 専門の数学のモチベーションに繋がった
   　自分は（競プロの影響を大きく受けて）組合せ論を専門にしているのですが、一見何のために考えているのか分からないようなことでも競プロで活かせるようなものもあったりして楽しいです。まだあまり多くのことは学べていませんが、修士課程も含めて残り2年半続けることで研究も競プロもいい感じにできたらいいな。

3. 人間関係が広がった
   　競プロがきっかけで出会えた人がたくさんいます。その人たちとは、競プロのことはもちろん、それ以外にも例えば各々の専門の話・インターンの話・Kaggleやってみようという話など、ができて楽しいです。今後はTwitterやオンサイトコンテストで大学外の人とも交流を増やしていきたいなぁ。

今後に向けて

次は、黄色コーダーを目指して頑張ります。

現在のDifficulty Piesはこの画像のとおりで、AC数は 947 です。青diff200問・黄dif100問くらい、AC数2000を目指して精進していこうと考えています。また、AtCoder以外にもCodeforcesやyukicoderに取り組み、とにかく大量の問題に挑戦していくつもりです。

最後に

モチベ維持のためにCodeforcesでバチャも積極的にやろうと思ってるので、一緒にやってくれる人が嬉しいです。その時はまたツイートするなどします。

黄色になった報告記事が書けるように頑張ります！！