0.はじめに
初めまして、nouka28です。
2024/5/4に行われたABC352でついに黄コーダーになったので、色変記事を書きます。
（入青記事もあるのでそちらもぜひ）
1.自己紹介
高校1年生です。
競プロは中2くらいから始めましたが、中3になってから本格的にやり始めました。競プロ歴は1年半弱です。
2.入黄するまで
入青からすぐはABCで黄perfを取れることが多くなり、その後少し停滞はしましたが、2月下旬には1920くらいまで行くことができました。しかし、3月上旬のABCと2度のARCで緑perf、水、水と3連続大敗してしまい、1800を下回ってしまい、だいぶメンタルがやられていましたがそこからABCでは7連続黄perf、ARC、AGCでも大敗せず、無事入黄することができました！！！！！
3.やったこと
1.新しく覚えたこと
青→黄で新しく覚えたことはそれなりにあったと思いますが、実践的な面で考えると水→青のときと比べて結構少ないと思います。
以下に新しく覚えたものをあげます。
- 新しく覚えた中でコンテスト中考察の道具として使ったもの
- 全方位木DP
- 2D segtree
- FPS
- ゼータ、メビウス変換
- LinkCutTree
全部で5つだけです。ほとんどコンテスト中に必要な知識は水色のときで持っていたらしいです。
- 新しく覚えただけのもの（いつか出てくれ）
- Auxiliary Tree
- 重心分解
- HL分解
- LowLink
- ミラーラビンの素数判定、ポラード・ローの $O(N^{1/4})$ の素因数分解
- BSGS（離散対数問題）
- Merge Sort Tree
- Treap base の SortedList、SortedMultiList など
2.精進
水→青になった時も感じていたのですが、精進がとても大事だと思います。
アルゴリズムを学ぶのももちろん大事ですが、コンテスト（特にABC）では解いた問題数ももちろん、解いたスピード、すなわち如何に早解きできたかが勝負の分かれ目になります（崖があるコンテストではなおさら）。これらを鍛えるためには精進が必須だと思います。
- 問題文の速読（問題の言い換え など）
- 典型力（上界が絶対に達成できるやつかな？、制約的にbitDPでしょ！ など）
- デバッグ力 （サンプルと自分の実装が合わない、意図しないセグフォを直す など）
特に上の3点は精進をすることで身につけることができるものであり、問題文の速読は低難易度埋めで、典型力はABC-D~問題埋めで、デバッグ力は重実装系問題で鍛えることができると思います。
入青時：
入黄時：
青→黄にかけて、特にやったことはABCの 青、黄diff（ABC-F,G問題） を解くことです。これで典型力が身についたと思います。制約、TLからの計算量エスパーも多少できるようになりました。考察力も鍛えることができました。
最初は毎日青diffを、その合間に黄diffを解いていたら、いつの間にか毎日黄diffを解くようになり、最近は橙diffでも解ける問題が出てくるようになりました。
1日1問、Streakを切らさないことを意識することでモチベを保っていました。ちなみに入黄したときにはCurrentStreakが400日を超えていました。これからも切らさないように頑張ります。
3.バチャに出る
バーチャルコンテストに出ることもモチベのキープに繫がります。限られた時間内で問題を解くため、早解き、実装力などが鍛えられます。
- あさかつ（毎日朝7:30~8:30）
- まよこん（毎日夜）
- もV （不定期だからあまり出られない） など
僕は主に上のものに出てました、時間に余裕のある時に参加するのがおすすめです。
4.習得したアルゴリズム
入黄するまでに覚えたアルゴリズムやデータ構造の理解度を5段階に分けます。
この記事を参考にして書きます。
- 5 : 得意
- 4 : まあ使える
- 3 : 調べれば使える or 使えるけど中身がわからない
- 2 : 使えない
- 1 : すみません、よくわかりません...
グラフ
| 名称 | 習得度 |
|---|---|
| ダイクストラ | 5 |
| Yen's algorithm | 1 |
| ワーシャルフロイド | 5 |
| ベルマンフォード | 4 |
| LCA | 5 |
| オイラーツアー | 3 |
| 二部グラフ判定 | 5 |
| クラスカル法 | 5 |
| プリム法 | 3 |
| Brounvka法 | 1 |
| トポソ | 4 |
| SCC | 4 |
| LowLink | 4 |
| 重心分解 | 3 |
| HL分解 | 3 |
| 木の直径 | 4 |
| AuxiliaryTree | 3 |
| LinkCutTree | 3 |
| グラフの彩色数 | 3 |
| 最大流/最小カット | 4 |
| 燃やす埋める問題 | 4 |
探索
| 名称 | 習得度 |
|---|---|
| DFS | 5 |
| BFS | 5 |
| bit全探索 | 5 |
| 半分列挙法 | 5 |
| 順列全探索 | 5 |
| 二部探索 | 5 |
| 三部探索 | 4 |
| 尺取り法 | 5 |
DP
| 名称 | 習得度 |
|---|---|
| 1次元DP | 5 |
| 2次元DP | 5 |
| LCS | 4 |
| LIS | 4 |
| 区間DP | 4 |
| 期待値DP | 4 |
| 確率DP | 5 |
| bitDP | 5 |
| 桁dp | 4 |
| 竹dp | 1 |
| 耳dp | 4 |
| 木dp | 5 |
| 全方位木dp | 3 |
| 2乘の木dp | 4 |
| 挿入dp | 4 |
数学
| 名称 | 習得度 |
|---|---|
| 素数判定($O(\sqrt{N}$) | 5 |
| 素数判定($O(\log N)$) | 4 |
| 素因数分解、約数列挙（$O(\sqrt{N}$） | 5 |
| 素因数分解、約数列挙($O(N^{1/4}$)) | 4 |
| gcd、lcm | 5 |
| 累積和 | 5 |
| 繰り返し2乗法 | 5 |
| 行列累乗 | 5 |
| CRT | 4 |
| 拡張Euclid | 5 |
| 商列挙 | 5 |
| 離散対数問題 | 3 |
| modint | 5 |
| mod Pでの位数 | 2 |
| $_nC_r$が $O(1)$ | 5 |
| floor_sum | 3 |
| ゼータ、メビウス変換 | 3 |
| FPS | 4 |
| Lagrange補完 | 3 |
| 包除原理 | 4 |
| 鳩の巣原理 | 4 |
データ構造
| 名称 | 習得度 |
|---|---|
| UnionFind | 5 |
| WeightedUnionFind | 5 |
| UnionFindに一次方程式載せる | 5 |
| map | 5 |
| set | 5 |
| multiset | 5 |
| BIT | 5 |
| segtree | 5 |
| lazy_segtree | 5 |
| segtree_2D | 5 |
| segtree_beats | 3 |
| dynamic_segtree | 5 |
| dynamic_lazy_segtree | 5 |
| Space Table | 2 |
| MergeSortTree | 4 |
| WM | 3 |
| ダブリング | 4 |
| モノイドが乗るSortedList | 4 |
| モノイドが乗るSortedMultiList | 4 |
| ImplicitTreap | 4 |
文字列
| 名称 | 習得度 |
|---|---|
| ローリングハッシュ | 5 |
| Z_algorithm | 4 |
| suffix_array | 4 |
| lcp_array | 4 |
その他
| 名称 | 習得度 |
|---|---|
| 座圧 | 5 |
| 平方分割 | 5 |
| 平面操作 | 4 |
| Grundy数 | 4 |
| Mo's algorithm | 4 |
| 2 sat | 1 |
5.写真集
-
直近7回Beginnerの成績
-
直近7回Regularの成績
6.これから
あ、あのARC、AGCどっちも黄perf以上を取ったことがないのですが...
ということで、これからは主にARC、AGCの精進を頑張っていきたいと思います。
あと、今年こそJOIの春合宿にいきたいです。