先日、累計38回目のコンテストでやっと緑色になる事ができました！

折角の節目なので、緑になるまでにどのような勉強をしたかについてまとめておこうと思います。いわゆる色変記事というやつです。

もくじ

灰→茶になるまでにやったこと
茶→緑になるまでにやったこと
これからの目標について

灰→茶になるまでにやったこと

初めてAtCoderのコンテストに出たのは2020/5/31に開催されたAtCoder Beginner Contest 169でした。

2020年の5月といえば新型コロナウイルスがいよいよマズイ段階になってきていて、 45年ぶりに(第一回)緊急事態宣言が発出されていたとかそういう時期です。

そのころ僕は高校1年生だったのですが、このコロナウイルスの影響でまだ1度も高校に行ったことがなく、中学は2月で殆どの日程が終わっていたため実質的に春休みが3ヵ月間続いているような状態でした。

この頃僕はアホみたいに暇で(中学卒業のタイミングだったので課題なども一切なかった)、なにか暇つぶしになることないかな～～～と思っていたところに以前から興味のあったプログラミングを折角ならやってみようかなという気になり、適当に入門書を買ってプログラミングの勉強を始めました。

初めて読んだ本はこれだったと思います。知識0でもめちゃくちゃ分かりやすくてサクサク読み進められました。あ、ステマじゃないです。

その後入門書を追加で何冊か読んだりインターネットで調べたりしている中で、「AtCoder」というものを知りました。

そのためAtCoderをやり始めた頃は競プロどころかプログラミング自体がまだ始めたてだったので、まずコーディングに慣れるというのが最初の目標でした。

最初の頃はコンテストの時は必ずJava(昔はJavaで競プロをしていた)のリファレンスや、読み終わった入門書をチラチラ見ながらコーディングしていました。それでもREやCEをよく出していました。

(最初に参加したコンテストの提出)

その後、コンテストに参加していく中で「C++の方がどうやら競プロに向いているらしい」ということを知り、C++を勉強しました。下図の丸部分が使用言語をC++にしてからのレートの変化です。

使用言語をC++に変えたらレート爆増！！！とまでは行きませんが、C++にしてからは多少レートの伸びが良くなったと思います。

個人的には、当然C++のコーディングに慣れるのにも時間がかかったため、中々すぐにC++に変えたことによる恩恵が出てくる訳ではなかったという事だと思います。(それに加え2完くらいなら計算量はあまり関係ないため)

C++のコーディングになれてきたら、やっと典型アルゴリズムについて勉強を始めました。

茶色になるまでに学んだアルゴリズムはこんな感じです。

• 簡単なDP
• imos法
• 優先度付きキュー
• エラトステネスの篩
• 貪欲法(Greedy)

しかし、学んだアルゴリズムを使う問題がすぐに解けるようになったという訳ではなかったです。むしろ解けない事のほうが遥かに多かったです。

ですが、段々と解答の言っていることが分かるようになり、ただ問題文の通りに愚直に実装すればいい問題だけしか解けなかったのが、少し問題文を言い換えたり、簡単な典型アルゴリズムを用いる問題がちょくちょく解けるようになっていきました。

そんなこんなで2021/3/6のAtcoder Beginner Contest 194、通算23回目のコンテストで茶色になることが出来ました。

というわけで灰→茶になるまでにやったことの概要はこんな感じです。

まずはコーディングに慣れる  →  使用言語をC++にする  →  簡単なアルゴリズムを勉強し始め、解説が読めるようになる

入茶当時のAC数はこんな感じでした。ただこの頃はしっかり理解していないのに解答をほぼ丸写しして提出していたりしたので、解いた問題全てをちゃんと理解できていたかというと全くそんな事はなかったです。

茶→緑になるまでにやったこと

茶→緑になるまでは色々なことを始めました。また、灰→茶の時よりもかなり多くのアルゴリズムを覚えました。

まず最初に、やり始めたことについて書いていきます。

AtCoder Problems

みんな大好きAtCoder Problemsですが、記憶が正しければ入茶するまでその存在を知りませんでした。

このサイトの恩恵は最早言わずもがなですが、中でもdiffの存在を知ったというのが1番大きいです。

このサイトを使う以前は問題の難易度を判別する術が「その問題が何問題であるか(A問題、B問題など)」という事しかなかったので、 「その問題が同じカテゴリの問題群の中でどれくらい難しいのか」という事がわかりませんでした。 そのため、自分のレベルではまだ取り組まなくてもいいdiffの問題にすごく時間をかけて、結局理解できずに終わる、という事が多々ありました。

また、diffを知ったことにより「今の自分のレベルで解くべき問題」が可視化されてとてもよかったです。 Recommendation機能は使った回数はそこまで多くありませんが自分のレートに合ったdiffの問題を列挙してくれるので、とりあえず何でもいいから1問解きたい!という時に活用していました。

また、Achievement欄はモチベーションの維持にとても役立ちました。 今年の夏休みの間は1日1AC以上必ずしていました。
(この「1日1AC方式」には賛否両論ありますが、個人的には「1日1ACに拘り過ぎるあまり私生活に支障が出てしまった」とならない限りは有効な手段だと思っています。)

蟻本

本格的にアルゴリズムを覚えていきたいと思い買いました。

この本は各アルゴリズムが噛み砕いて説明されているため、新しいアルゴリズムを覚えるのに使えるのは勿論のこと、アルゴリズムがどのようなものだったかやどのような実装だったか「確認する」事にも使えるのがとてもよかったです。

まだ全ページの1/3くらいしか読んでいないので、どんどん読み進めていきたいです。

競プロ用開発環境

灰色の頃はターミナルでいちいちコマンドを打ってコンパイルを行っていたのですが、VScodeにWSLの拡張機能を導入した事によりいちいちコンパイル時にコマンドを打たなくてもいいようにしました。

また、必要なライブラリをすぐに持ってこれるようにスニペットも使い始めました。これによりいちいちテンプレをコピー&ペーストする手間が省けました。

「開発環境」ではないですが、atCoder用のweb拡張機能もとても便利です。

中でも便利なのが、提出した問題に色付けするatcoder-tasks-page-colorizer、問題のdiffを表示してくれるAtCoder Difficulty Displayの2つです。

このようにweb拡張機能を導入すると提出状況やdiffが一目で分かるので、いちいち提出状況を見るために提出結果をページを確認したり、diffを確認するためにAtCoder Problemsを見に行く必要がなくなります。

基本的にこれらの便利機能を入れて損はないので、躊躇わずにどんどん導入した方が良いと思います。

学んだアルゴリズム

次に、緑になるまでに学んだアルゴリズムについてです。

• 尺取り法
• 累積和
• ナップサックDP、確率DP、bitDP
• DFS(bit、再帰)
• BFS
• 二分探索
• バケット法
• Union-Find
• ワーシャルフロイド法
• 繰り返し二乗法
• 座標圧縮

アルゴリズムを理解したときに感動が大きかったのは二分探索、尺取り法、繰り返し二乗法あたりだったと思います。計算量を対数時間まで落とせるのはロマンがありますよね。

勉強方法の変化について

最後に、勉強方法の変化についてです。

灰→茶の時と茶→緑の時では勉強方法がかなり変化しました。具体的には、以下の3点が大きな変更点でした。

解説ACを極力しなくなった(理解できるまではなるべくACを通さない)

灰→茶の時は、問題が理解できない時に解説ページをなんとなく読んで分かった気になって、ほぼ解説コードのコピペを提出してACをとって満足する、といった事が多々ありました。

ただこれはほぼ意味がないので、解説を読んでちゃんと理解できるまではACを取らないようになりました。

何故意味がないかというと、僕の場合とりあえずACが取れれば満足してしまいその問題を考えることをやめてしまうからです。そのため中途半端にしか理解していない段階でACをしてしまうと、結局得るものがなかった、みたいなことになりかねないからです。

「とりあえず問題を適当に解く」から「アルゴリズムを理解するために問題を解く」へ

灰→茶の時はABCから適当に1問選んで解くというのが主な取り組み方だったのですが、茶→緑の時は学びたいアルゴリズムを選んで、そのアルゴリズムを使う問題を何問か解く、というような取り組み方に変わりました。

僕の場合折角アルゴリズムを学んでも、いざ実装しようとしてみるとどうやったらいいのか全く分からず手が止まってしまう、という事が結構あるので、実際に手を動かして新しく覚えたアルゴリズムを利用する、というやり方はとても有効でした。

問題を理解するために解説ページ以外に参考にできるものを増やす

AtCoderを始めたての頃は、問題の解説として利用できるツールが公式の解説ページだけでした。

しかし、それを読んだだけではなかなか理解できないことが多々あります。そのためTwitterで分かりやすく解説してくれている人をフォローしたり、Discordの競プロサーバーに入ったり、ブログを読んだり、と問題を理解するために活用できるものを増やしました。

精進記録

こんな感じです。最近は緑diffの問題もすらすら解ける事が多くなってきた気がします。

Heatmap(下の画像)を見ると、今年の夏休みは結構頑張っていたのが分かって良いです。

これからの目標について

入緑することが当面の目標だったので、次は何を目標にするか考えていたのですが、とりあえず決まったので書いておきます。

2022年6月までに入水する

これに向けて今後も頑張っていきたいと思います！

というわけで初めて色変記事を書いてみました。僕は緑になるまでかなり時間がかかったので、今茶色でなかなか緑になれなくて悩んでいる、という人の参考に少しでもなっていれば嬉しいです。

以上です。ここまで読んでくれてありがとうございます。