はじめに
Javaで競プロをやっている dvoraker です。
AtCoder Beginner Contest 295 で入緑しました！！！！！
精進量に対して結果があまり報われないコンテストもありましたが、無事緑色になれてまずは素直に嬉しいです。
勉強方針
勉強方法は人それぞれとは思いますが、自分は基本的に「解説を即見る」方針で精進していました。
その理由は……「自力で考えている時間があまり有意義とは思えない」からです。
1時間自力で考えるよりも、15分で解説読み込み+15分で他の人のコード見ながら実装+30分で復習の方が、実際問題、理解も深まりますし、問題数もこなせると思います。
青や黄色など、非常に高いレベルになればまた違い、考察力も必要になってくるのかもしれませんが、今のところはこの方針でやってみようかと思っています。
あとは、積極的に高難易度のアルゴリズム・データ構造のライブラリを作成しました。
性格上「習うより慣れろ」なので、武器の仕組みではなく、武器の使い方をまず覚えて、ひたすら問題を解くなかでそれらについての理解を深めました。
勉強したこと
せっかくの機会なのでジャンル別にまとめてみました。
理解度→アルゴリズムそのものの理解度。何も見ずに書けるか、等が基準。
実践度→どれだけ問題数解いたか、が基準。
探索系
| 理解度 | 実践度 | コメント | |
|---|---|---|---|
| Bit全探索 | S | S | おなじみのやつ |
| 順列全列挙 | S | S | nextPermutationを使うやつ全般 |
| 二分探索 | S | S | いわゆる「めぐる式」を履修。これに何度助けられたか。一番好きなアルゴリズムです |
| 再帰 | S | S | 再帰は慣れ……その通りでした |
| BFS | S | S | グラフ、グリッド共に相当数解きました |
| DFS | S | S | 同上 |
| 尺取法 | A | A | Dequeで動かすやつが分かりやすかったです |
| 三分探索 | B | B | 2問くらい解いた |
| 半分全列挙 | B | C | 1問だけ解いた |
色々書きましたが、入緑するならば「工夫した全探索」の問題が非常に重要だと思います。
A, B, C があって、愚直にやると N^3 だけど、A, B を固定すると C が固定されるから、計算量を N^2 に減らせる、みたいなやつですね。
グラフ系
| 理解度 | 実践度 | コメント | |
|---|---|---|---|
| Union-Find | A | S | もはや必須級。ABC-EFまで、解けるものはほぼ解きました |
| ダイクストラ法 | A | A | |
| ワーシャルフロイド法 | B | A | ↑←↓ここの3点セットに関しては、ABC-D以下はほぼ全部解きました |
| ベルマンフォード法 | B | A | |
| 非グラフをグラフに変換する問題 | A | A | かなり大事と思います。ARC011-Cとか |
| トポロジカルソート | A | A | やるだけ、の問題が結構ありました |
| 最小全域木 | A | A | ABC-DEに数問だけあった（解いた） |
| 01-BFS | S | B | 同上 |
| 強連結成分分解 | B | B | ライブラリ用意して数問解いた程度 |
| 最小共通祖先（LCA） | C | C | ライブラリは用意して1問だけ解いた |
| 最大フロー | C | C | 同上 |
グラフに関しては、とりあえず各種ライブラリを用意して、ひたすら問題を解きまくりました。
なので、アルゴリズムの中身の理解については浅いです（UnionFind、ダイクストラとかそらで書けませんし）。
データ構造系
| 理解度 | 実践度 | コメント | |
|---|---|---|---|
| Set（Java） | S | S | 特にTreeSetを使う問題は多いです |
| Map（Java） | S | S | 個数カウントなど、色々と有用（問題数も多い） |
| Deque（Java） | S | S | 個人的には、BFSするときに使うやつというイメージ |
| BigInteger（Java） | A | B | 多倍長整数クラス。便利ではありますが、計算量の関係で出番はほぼ無いです |
| 優先度付きキュー | A | A | ABC-Dでも何問か出題されてます。結構重要そうです |
| セグメント木 | B | B | セグ木自体の理解度は浅いですが、問題自体は5~6問くらい解きました |
| BIT | B | C | とりあえずライブラリだけ用意 |
データ構造系に関しては、比較的早期にセグ木に手を出しました。
セグ木でごり押しで解ける問題も多そうなので、ライブラリは作り得だと思います。
DP系
| 理解度 | 実践度 | コメント | |
|---|---|---|---|
| 累積和 | S | S | マジで本当に頻出 |
| 二次元累積和 | B | B | シッカリとライブラリ作りました（そらでは書けない） |
| 累積（和以外） | A | A | いわゆる累積max, 累積xorとか言われるものです |
| いもす法 | S | S | 過去問だとそれなりにあります |
| 基本DP | S | S | 階段とかジャンプ等の非常に基本的なDPです |
| ナップサックDP | S | S | そらで書けるまで精進 |
| むずめのDP | B | A | 三次元DP等。数はこなしましたが、解けるかと言われると微妙 |
| DP復元 | B | B | 簡単なものだけ |
| 最長共通部分列（LCS） | B | B | ライブラリ用意+数問程度 |
| 最長増加部分列（LIS） | B | B | 同上 |
DPは苦手なのですが、アルゴ式から初めて、ABC-Dにあるやや高難易度なDPも（うんうんと唸りながら）解きました。
問題数自体はかなりこなしたと思います。
数学系
| 理解度 | 実践度 | コメント | |
|---|---|---|---|
| 素数列挙、エラトステネスの篩 | S | S | 問題数も多く頻出。重要だと思います |
| 約数列挙 | S | S | 同上 |
| gcd, lcm | S | S | 同上 |
| N進法 | A | A | それなりに出題されてるみたいです |
| 組み合わせ（逆元、フェルマーの小定理） | B | S | 理解度は非常に浅いですが、ライブラリを使って青色difまで相当数解きました |
| 幾何 | B | A | 三角関数や座標平面など。ライブラリはいっぱい作りました |
| 確率・期待値 | B | B | 最低限だけ履修、解いた感じです |
数学に関しては中学数学以降ほぼ未履修と言っていい状態なので、難しい問題はあきらめるしかないです。
一から勉強するとなれば、競プロ以上に大変そう。
その他
| 理解度 | 実践度 | コメント | |
|---|---|---|---|
| 貪欲法 | A | A | ソートが絡むものが多かったです（区間スケジューリング等） |
| イベントソート | B | B | 最初見たときは「こんなやり方あるのか～！」と思いました |
| ビット演算 | B | B | どれも非常に難しく、ほぼ写経になった問題も多いです |
| 主客転倒 | B | A | 数え上げ問題を解く際に有用なテクらしいです。問題数的にもかなり多かったので今後も重要そう |
| ランレングス圧縮 | S | A | 使いどころは限られますが有用テクニックです |
ここに書いたもの以外にも「差分だけ考える」「包除原理」「周期性を考える」「条件・操作を言い換えて単純化する」など、ここには書ききれないほどの細かい典型考察も学ぶことができました。
それらについては、常設コンテストである「典型90問」を解くのがオススメです。
まとめ
精進は裏切りません。頑張りましょう。僕も頑張ります。
とりあえず水色までは到達したいと思って始めたので、それまでは。