先日のABC192でAtCoder水色になることができました。 入水は１つの目標だったので水色になるまでにやったことをまとめたいと思います。 誰かの役に立てば幸いです。

Rating

（だいぶ前に「俺のプログラミング力を見せてやる！(プログラミング初心者)」と意気込んで挑戦し撃沈し離れた頃からアカウントが変わってないので横長。変動がわかりにくいです。表示区間を変えれるようにして欲しいな）

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

緑まで

競プロをやりだしたきっかけは、就職活動のコーディングテストでアルゴリズムの問題が出るとのことで、データ構造とアルゴリズムの勉強が必要だと感じたからです（2020年3月末）。学部は文系だったのでプログラミングはまぁ独学でした。バイトでもデータ構造やアルゴリズムの知識は要求されませんでした。（計算量を無視した）一通りの処理の記述はできるつもりでした。メイン言語はPythonでした。

緑になるまでは以下のことに取り組んだと記憶しています。

  1. AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～
  2. LeetCode の Learn
    • Arrays 101
    • Linked List
    • Binary Search (30%)
    • Recursion Ⅰ/Ⅱ
    • Queue & Stack
  3. AtCoder のコンテストへの参加

過去問精選１０問

計算量を落とす、アルゴリズムやデータ構造を使う、そういったことの意味を理解しました。

LeetCode の Learn

データ構造とアルゴリズムについて具体的に学ぶことができました。 アルゴリズムは実装を通して使い方を学ぶことができました。 Queue & Stack や Linked List ではデータ構造を実装するという課題がありました。実装力がついたと感じます。また計算量の評価という点でも勉強になりました。

ただLeetCodeは面接のコーディング問題を勝手に載せているという話なども耳にします。その点についてよろしくないと思う、あるいは日本語がいい場合はAOJ(Aizu Online Judge)のALDSに取り組むのが良いと思います。というかJOIの問題などもあるのでAOJの方がいいと思います。

コンテストへの参加

過去問はたいして解かずに普通に参加してました。 これは就職活動が終了した後も続けて、緑になったあたりで伸びが止まり、レートが上がる気がしなくなりました。

まとめ

今になって思うと、この時は累積和もグラフアルゴリズムもbit全探索も何も知らない状態だったので、我ながらよく緑になれたなぁと不思議に思います。

考察のできる/できない、知識のある/ないは問題ごとに振れ幅がありますが、実装力は練習した分だけ着実に伸びるのではないかと思います。LeetCodeの実装問題を通して実装力をつけ、解ける問題を高確率で解いた結果、緑になれたのではないかと思います。

ちなみにコーディングテストでは競プロで言われるようなアルゴリズムというものは全く必要ありませんでした。

水まで

  1. けんちょん本
  2. レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】
  3. 精進
  4. AOJ ALDS
  5. AtCoder のコンテストへの参加/復習
  6. +αのデータ構造の習得

けんちょん本

競プロを始めてデータ構造やアルゴリズムのことを検索すれば大抵はけんちょんさんのqiita記事がヒットします（いつもありがとうございます）。こちらの書籍で再帰、二分探索、動的計画法、貪欲法、グラフアルゴリズムといった基本的なアルゴリズム・データ構造の知識を勉強していきました。図が多くてわかりやすいです。途中からデータ構造とアルゴリズムが面白いと感じてのめり込んでいきました。個人的には二分探索が好きです。

サンプルコードがC++だったこともあり、この頃からC++を使うようになりました。C++に慣れてからはACLも使うようになりました。また、コンテストごとにディレクトリを作成したりサンプルをコピペするのが面倒なのでatcoder-cliとonline-judge-toolsを導入し、テンプレートも用意しました。導入はこちらの記事を参考にしました。非常に快適になりました。

レッドコーダーが教える〜中級編

けんちょん本を一通り読み終えたものの定着度/応用力はまだまだでどうしたらいいかなということでこちらに取り組みました。 解けない問題も多くありましたが、けんちょん本で得た知識、累積和やimos法、逆元の数え上げなど一通りの武器が手に馴染み始めて、水色を目指す闘いの土俵に上がれたと思います。

精進

AtCoder Problemsという神サイトのRecommendationのModerateを中心に解いていきました。試験管なしdifficultyで800から1500手前まで埋めました。Trainingも埋めました。

途中から、コンテストでレートを上げてModerateに少し上のdifficultyの問題が出てきてそれを１週間でこなしてまたコンテストでレートを上げて(微増)〜というサイクルができました。とにかく解いて消化していくのではなく理解することを心がけていました。

AOJ ALDS

LeetCodeと似たような感じです。ヒープとか二分木の実装は為になりました。難しくて解けないものもありました。

コンテストへの参加/復習

  • 瞬殺とはいかない問題は解説放送を見るようにしました。
    • 解説pdfよりも説明が丁寧でわかりやすいです。
    • 複数の解法を紹介してくれることがあります。
    • コーディングの様子を見れるので実装の勉強になります。
  • 特に戦略などはありませんでした。
    • 順位表でそれぞれの問題で何人が通しているかを見て難易度が逆転してそうな場合は、簡単そうな方に手をつけて「あらABCのF解けちゃった〜」ってこともありました。
    • オーバーフローが怖い時、文字列処理が面倒、といった場合はPythonを使うこともあります。

+αのデータ構造の習得

ACLにあるsegment tree、fenwick tree、modintを使うくらいです。

まとめ

けんちょん本で一通りの知識を得た後はレートが落ちて茶色になりました。これは刃牙で「ナイフを持った相手はナイフしか使ってこないから怖くない」みたいなことが言われてた気がするのですが、これと似たような感じでアルゴリズムとデータ構造の知識を得た私はその中の「どれを使ったらいいかな？」という考え方をしてしまっていた気がします。

レッドコーダーが教える〜中級編 2-2-4. 過去問を解きまくる という節では、「競プロの実力=アルゴリズムの理解度×競プロの演習量」という式がありますが結果的に私の場合は750問ほど解きました。

継続的な努力の賜物と見ることもできますが運も良かったと思います。

これから

抱負で掲げたレート1400を目指します。

青になるには当然ながら青パフォを出さないといけないのですが、今だに青パフォを出したことがないので青になるのは何かしらのブレイクスルーがないと厳しい気がしています。