はじめに
趣味と勉強を兼ねて競技プログラミングをしている @kami634 です。この度、AtCoderで目標としていた青コーダーになりました。
青色というのは、一定水準以上のアルゴリズムの知識を持ち、それを問題解決に活かすことができないとなることができません。それゆえに多くの人の目標になっていると思います。
chokudaiさんのブログ記事に青のレベル感が記載されていたのでご参考に↓
黄・橙・赤などの上を見上げると、青色というのは通過点に過ぎず、まだまだ必要なことは多いです。ですが、青色レベルのアルゴリズム力があれば多くの問題を解決することが可能でしょう。
ということで、水色や青色あたりを目指す方のために、自分が必要だと思ったことをまとめたいと思います。
そもそもAtCoderとは
AtCoderとは、競技プログラミングのコンテストを開催する日本最大のサイト(及びそれを運営する会社)です。週末にコンテストが開かれる他、3000問もの過去問をいつでも解く事ができます。
最近では、インターンや就職のためのAtCoderJobsや、アルゴリズム実技検定(PAST)などもあり、サービスの幅も日々広がっています。
日本の競技プログラミングの普及や、アルゴリズム力の向上に大きな役割を果たしている企業と言って良いでしょう。
競技プログラミングは何が嬉しいのか？
競プロによって得られる恩恵は様々なものがあります。
- 純粋に問題を解くのが楽しい
- 様々なアルゴリズムの知識が得られる
- 実装力が上がる
- 複雑な問題の本質を見抜き、プログラムする力が身につく
- 就職やインターンに役立つ
- アルゴリズム力や実装力の証明になる
愚直に実装して計算させると一生かかっても終わらない問題などを、適切なアルゴリズムを利用することで高速化できた時の喜びはかなり大きいです。
単純に楽しいだけではなく、競技プログラミングが認知されるようになったので、スキルの証明としても使用することができます。
興味が出た方は @e869120 さんの
などの記事が詳しいので読んでみると良いと思います。
青色をめざすために
青色になるために知っておくと良さそうと思ったことなどをまとめます。
コンテストについて
とにかくコンテストに出る
大切なのがコンテストに出ることです。時間を確保するのは大変ですが、コンテストに出ないとレートが上がりません（下がりもしませんが）。
問題を見て解けそうになかったら submit せずに撤退する (No Sub) などの戦略もあるようですが、コンテストに出るのも経験です。特にレートが低いうちは、気にせずどんどん出て経験を積んだほうが良いと思います。
また、__バーチャルコンテスト__に参加するのも練習になります。AtCoder上では既に終了したコンテストを本番同様に解くことができますし、AtCoder Problemsでもバーチャルコンテストに参加することができます。
Problems では有志の方が「あさかつ」や「よるかつ」などのバーチャルコンテストを開いてくれています。問題も過去問からバランス良く選ばれているので練習におすすめです。
コンテストが終わったら復習をする
当たり前のことですが、コンテストで出た問題を復習しましょう。終わった後に解法をTwitterなどでつぶやくと、軽い復習とアウトプットになって良いかと思います。
考えても解けなかった問題は、翌日でも良いので解説などを読んで AC できると良いでしょう。
ただし、解説は厳密にかかれていたり、詳細が省かれていたりして逆に分かりにくい場合があります。その場合は、解説記事を検索したり、解説動画を見たりすると良いでしょう。
コンテスト中は本気で問題を解こうと考えるので、終わった後にしっかり復習すれば良く定着します。
海外のコンテストにも挑戦する
AtCoderに慣れてきたら、海外のコンテストサイトに挑戦してみるのも良いと思います。
最近はDeepLなどの優秀な翻訳ツールもあるので、英語に多少苦手意識がある方でもなんとかなると思います。
Codeforces はAtCoderの次に始めるのにオススメです。
なんといっても、コンテストの開催頻度が凄いです。日本時間で夜中に開催されることが多いので毎回参加するのはかなり難しいですが、余裕がある日は参加してみると良いでしょう。
過去問での練習時について
解法を思いつくための道筋（考察の典型）を考える
問題を漫然と解いていくだけではあまり成長しないと思っています。「どうしてその解法に至るのか」を良く考えるようにしましょう。
競技プログラミングでよく出る「アルゴリズムとデータ構造」というのがあり、その典型を学習する必要もありますが、それとは別に「考察の仕方」にも典型があるように思います。
いくつか(ほんの少しだけ)例をあげてみると
- 何かを固定して考える（3つ動かせるものがあれば中心を固定することが多い等）
- 操作をする問題は、不変量は何か・順番を入れ替えても変わらないか・逆順に行うとどうかなど考えてみる
- xor は桁ごとに考えることが多い
- グラフは特徴的なもので実験してみると状況をつかめることがある（スターグラフ・完全グラフ・パスグラフなど）
- ...
などです。「多い・気がする」というものばかりですが、こういう「考察の典型」を知っているかで、解くための取っ掛かりを見つけられるかが大きく変わる気がします。
「どうしてその解法を思いつくのか」を意識することで、考察力が上がり、他の問題にも応用が効くようになると思います。
ただし、様々な種類の「考察の典型」があります。多くの問題を解いて、知らないものを少なくし、使いこなせるようにする必要があるので、一朝一夕で身につくものではありません。
体感ですが、水色と青色で求められるアルゴリズムは、そこまで大きく差がないように感じます。2つの差は「考察力」にあるのではないでしょうか？（もちろん速度も関わってくると思いますが）
私がいくつか大事そうかなと思った「考察の典型」は 競技プログラミングで解法を思いつくための典型的な考え方にまとめてみました。
まだ完全には整理できていませんし、私が知らないものもまだまだあると思います。
たくさん過去問を解く
（アルゴリズム・考察ともに）典型力を鍛えるためにも、沢山問題を解く必要があります。楽しい問題も多いですが、頭も時間も必要です。
単純に問題を解き続けるのは結構しんどいので、AtCoder Problems などのサイトを活用すると、モチベーションを保って続けられると思います。
アルゴリズムとデータ構造
水色や青色で必須になりそうなアルゴリズムとデータ構造を大まかにまとめてみました。
- STL のよく使うデータ構造や関数（set, map, lower_bound など）
- 整数系（素因数分解・最大公約数・約数列挙など）
- 二項係数と mod p の計算
- 累積和
- しゃくとり法
- 二分探索
- 深さ優先探索・幅優先探索
- 単一始点最短経路（ダイクストラ・ベルマンフォード）
- 全点間最短距離（ワーシャルフロイド）
- 動的計画法
- Union-Find Tree
その他のアルゴリズムも出題される可能性があるので、知っておくに越したことはありません。
Twitterのすゝめ
Twitter 上では、競技プログラミングで強い人達がワイワイと活発に議論しています。
そういうのを傍から見ているだけで、色々と勉強になりますし、参考になるサイトの情報なども出回ってきます。
自分では思いつかなかった「楽な実装方法」や「どうしてその解法を思いついたのか」などのツイートを見つけると得した気分です。
ちなみに私のアカウントはこちら(@634kami)です。
便利サイト・ツール
競技プログラミングをする上での便利サイトやツールをいくつかご紹介します。
AtCoder Problems
普段の練習に最も良く使うサイトです。自分がどの問題を解いたか一瞬で分かりますし、問題ごとに推定難易度もあるのでメチャクチャ便利です。
一面緑色にしたいと思えるので、精進のモチベーションが上がります。
AtCoder Scores
AtCoder の（重み付き配点に対応した AGC 001 以降の）問題を点数順に並べるサイトです。点数の小さい方から埋めていきたい方はこちらを使って練習すると良いでしょう。
WolframAlpha
複雑な数式などを解いてくれたり、簡単に式変形してくれたりします。AtCoderで使ったことはまだないですが、コドフォでは何度か使用しました。
The On-Line Encyclopedia of Integer Sequences
数列の一部を与えると、それがどんな数列か教えてくれます。問題を解く時になんか数列っぽいのが見えたら、このサイトに打ち込んでみるとエスパーできたりするかもしれません。
ただ、私はまだコンテスト中に使ったことはないです。
GeeksforGeeks
英語ですが、アルゴリズムやデータ構造に関する記事が多くまとまっています。
有名なアルゴリズムは大抵何らかの記事があり、実装例もあるので非常に参考になるでしょう。
DeepL
精度の高い翻訳ツールです。競技プログラミングの問題文を読む時などにも使えます。
数式はうまく表示できないなど、完璧ではありません。しかし、英語を読むときの補助としては十分です。
Competitive Programming Contests Calendar
AtCoder, Codeforces, Google Code Jam, LeetCode, Topcoder などの有名コンテストサイトの、コンテストの開催予定がカレンダーにまとめてあります。それぞれのサイトのカレンダーを一度に確認できるので便利です。
Chrome拡張
ブラウザがChromeなら、Chrome拡張を利用してAtCoderをさらに使いやすくすることができます。Greasy Forkを利用したスクリプトが多いです。
AtCoderStandingsAnalysis
順位表から分かる情報をかなり分かりやすくまとめて表示してくれるスクリプトです。コンテスト中に、問題ごとの難易度やWAになりやすいかなどがすぐに分かるので重宝しています。
問題の順番と難易度が逆転している場合などは特にありがたみを感じるかもしれません。
ac-predictor
コンテスト中にパフォーマンスを予測してくれます。自身の解く速度がパフォーマンスで表すとどのくらいかすぐに分かるので便利です。
AtCoderPerformanceColorizer
成績表のパフォーマンス値・レート値を色付けしてくれます。視覚的にわかりやすいです。
ビフォー
アフター
自身が青色になるまで
参考として、自己紹介と私がどういう精進をして青色になったのかを記載しておきます。
競技プログラミングを始める前のスペック
- T大学 理学部情報科学科の学部生
- 中学受験経験
- 大学受験の範囲の数学は忘れている部分もあるが分かる
- 大学数学は情報科学科の学生が習う範囲は学んだ
- プログラミングは大学に入ってから
- アルゴリズムとデータ構造、グラフ理論などは授業で基礎的なことを学んだ
- 天才ではない
青になるまでの期間・成績・精進量
前に一度アカウントを作ったのですが、真面目にやらなかったので（灰色か茶色くらいだったと思います）新しく作り直し、2019年の11月23日の 【DISCO presents ディスカバリーチャンネル コードコンテスト2020 予選】 からはじめました。
はじめは緑くらいの実力でしたが、徐々にパフォーマンスが上がっていくのを実感できました。
以下に青になるまでにどんな問題をどれだけ解いたかを載せておきます。
特別にやったこと
青色をめざすために で書いたこと以外にやったことがあるのでまとめておきます。
アウトプットとしてアルゴリズムまとめサイトの作成
自身のアウトプットを兼ねて、アルゴリズムをまとめるサイト(アルゴリズムロジック)を作りました。あるアルゴリズムを記事にしようとすると、それを言語化できるまで理解しなくてはならないので、かなり勉強になります。
ちなみに twitter で少し話題に上がった記事はセグメント木をまとめたものでした。
ネット上や書籍上で、セグメント木に関する情報は多くあったのですが、競技プログラミングで必要となる情報を上手くまとめた記事が少なかったので話題になったのだと思います。
100記事近く書いてようやく少し慣れてきたのですが、
- トップダウン的な説明によってリファレンスとしての機能を提供する（結論や実装を提示してから、詳細な説明をする）
- 関連問題があれば記載することで、アルゴリズムを習熟させる起点とする
という点を今後は意識したいと思います。
自分の説明よりも分かりやすく、正確なものは沢山あると思うのですが、他サイト・書籍との差別化を図りつつ、自分だけではなく閲覧してくださる方にとっても役に立つサイトにしたいと思っています。
ただ、最近は大学の勉強の方もあるので、更新ペースはゆっくりです。
1日1回感謝のAC
AtCoder への感謝を忘れないために、1日1回感謝のAC をしました。
つまり、AtCoder Problems での Streak を絶やさないことを意識しました。
気分が乗らなくても「1問解いたら2問目を解きたくなっている」という状況はよくあります。
青になるまでに学んだアルゴリズム
全てではありませんが、思いついたものをまとめておきます。
- STL のよく使うデータ構造や関数（set, map, lower_bound など）
- 累積和
- しゃくとり法
- 二分探索
- 深さ優先探索・幅優先探索
- 単一始点最短経路（ダイクストラ・ベルマンフォード）
- 全点間最短距離（ワーシャルフロイド）
- 最小全域木
- 動的計画法
- ナップサック系
- 桁DP
- ビットDP
- 区間DP
- 木DP・全方位木DP
- Union-Find Tree
- セグメント木・遅延評価セグメント木
- Binary Indexed Tree (BIT / Fenwick tree)
- ダブリングによる木の最近共通祖先（LCA)
- 最大フロー・二部グラフの最大マッチング・最小カット
- トライ木
とりわけ後半は青でも必要ないものが多いと思います。楽しいので勉強しました。
ここに書いた大抵のアルゴリズムはアウトプットも兼ねてサイトに記事を載せています。