初めまして．中二で競技プログラミングをしているhighlighter_mathです．
先日のABC340で三回目の黄パフォを出し，入青しました！
0 初めに
0-0 自己紹介
とある国立中学に通っている中二です．
中一の終わりに同級生のMagentorに勧誘されて競プロをはじめて，そこから約1年間競プロをしています．
プログラミングの経験は競プロを始めるまでほとんどありませんでしたが，数学は好きで，算オリや広中杯に出るなどをしていました．
0-1 この記事について
主に僕が入青するまでに学んだことや精進について軽く触れたいと思います．
競プロに関係ないことも多々あるので競プロについて読みたい人は適宜読み飛ばしてくださいm(__)m
また，一部コンテストのネタバレも含まれます．
1 競プロを始める前
1-0 中学入学前
当時は競プロどころかパソコンにすらあまり触っていなかったため，「この黒い箱何？」状態でした
1-1 中一
僕の学校では中一のはじめに新入生オリエンテーションというものがあり，各部活の紹介をその部活の部長や主将さんから伺います．当時の僕は圧倒的にパソコン弱者だったので，正直パ研の紹介はほぼ聞いていませんでした
結局数研にはいって，他の部活には入りませんでした．
また，このもう少し後にMagentorと出会います．
Magentorに中学数研の部長を押し付けるなどをしていました．
2 ～入茶
2-0 中一終わり
MagentorからAtCoderの存在を教わります．とりあえずアカウントを作り，教えてもらったAPG4bを進めます．
パ研の部室が技術室奥にあることも聞きますが，行ってみたら薄暗くて気味悪いうえに外から見たら先輩が踊っていたりしていたので行っては引き返すを繰り返していました．
また，APG4bがある程度進んだあたりからコンテストにも出始めます．
2-1 中二はじめ
中二はじまってすぐあたりに入茶しました． このころはあまり精進をしておらずダラダラやっていました．
ARC151でAが解け，緑パフォが出せたところあたりで一気に入茶に近づきました．
ここはアルゴリズムを学ぶというより，コーディングになれるということがメインだったと思います．
3 ～入緑
3-0 ARC160
入茶したころ，ABCではパフォが停滞してしまっていました．
そのときARC160で大成功をおさめます．
+170，一気に入緑へ近づきます．
入茶，入緑前のABCで停滞していた時期をARCで何とかしてしまっていたせいで後々苦労することになるとはこの時知る由もありません...
3-1 それ以降
惰性で緑まで届かせます．(適当)
4 ～入水
4-0 停滞
ARCで緑diffまでを回収するだけだと，僕の早解き力ではよくて水下位パフォしか出ませんでした．
案の定水下位で停滞します．
このころ，まずはABCで勝てる，少なくとも水パフォは安定できるようにしなくてはならないと思いました．
そこでE869120さんの典型90問の★5を埋めます．
学校の授業の合間を縫って，約10日間かけてじっくり(ほぼほぼ)埋めました．
4-1 初のABCでの大成功
そんな中，精進が実を結んだのか，ABC330で大成功をおさめます．
しかし，ABCで初めて黄パフォを出したことで調子に乗り，精進をピタリとやめてしまいました．良くないですね．(反省)
4-2 入水後二度目の停滞
1400前後でほぼ動かなくなりました．これはまずいです．前の停滞も精進したら抜け出せたので，今回も精進しようと考えました．
そこで，AtCoder ProblemsのRecommendationのdifficultを，一日一問解くということをやっていました．
ABCかARCかAGCかはあまり気にせず，適当に選んだ問題を考察して，半日考えて分からなかったら未来の自分に託して別の問題を考察するということをしました．
4-3 二度目の黄パフォ
ARC171で黄上位パフォを出します．これに関しては4-2に書いたような，考察を重視した精進が実を結んだと思います．ある問題に帰着で来たあとはライブラリ窃盗しましたが
何はともあれ，レートが1554まで伸びます．
4-4 入青
4-4-0 開始前
ABC340では，青上位パフォ以上を出せば入青という状況でした．
今までABCで青パフォ以上は出したことがなく，ABC330で一回だけ黄パフォを出したのみだったので，正直冷えなければいいかなくらいにしか思っていませんでした．
4-4-1 A,B
特に変わった点もないので，普通に通します．
4-4-2 C
制約を見て一瞬ビビりますが，セグ木のような構造の二分木を考えたとき，各階層で足される和は毎回 $N$ で，最後の段はすべて $1$ 以上 $2$ 以下であることが容易に示せるので，やるだけになります．
想定のメモ化再帰は思いつきませんでしたがなんとかなりました，良かった～(メモ化再帰にも慣れないと)
4-4-3 D
有向辺を貼っていけば $1$ から $N$ までの最短距離を求めればいいだけなので，dijkstraでできます．
Dでdijkstraが出るの！？となっていました．
4-4-4 E
imos+BITで行けることはわかりますが，面倒だったので遅延セグ木で殴ります．(まさか想定解とは思いませんでした)
4-4-5 F
数学っぽい見た目をしていたので心の中でガッツポーズをしながら良く読むと，ただ二変数の一次不定方程式を解けば良いだけと分かります．
少し考察したら再帰でいけそうなことがわかりますが，実装に自信がなかったので検索すると，拡張gcdなるものが出てきます．けんちょんさんに感謝しながらコピペして実装したら通りました．(けんちょんさん，ありがとうございます...！)
4-4-6 G
ここで順位表を見ると予測パフォが黄色になっていました．入青来たのでは！？と思いつつも油断せずに考察します．
↓
解けません...
4-4-7 結果
ギリギリ黄パフォでとどまり入青できました！
5 履修したアルゴリズム
履修したアルゴリズムを5段階の理解度でまとめます．
| 名称 | 理解度 |
|---|---|
| 全探索 | 4 |
| 二分探索 | 4 |
| 並列二分探索 | 1 |
| 順列全探索 | 3 |
| bit全探索 | 3 |
| 累積和 | 4 |
| imos法 | 4 |
| 尺取り法 | 4 |
| ナップサックdp | 3 |
| 区間dp | 2 |
| bitdp | 2 |
| 桁dp | 3 |
| インラインdp | 2 |
| 二分累乗法 | 5 |
| 行列累乗 | 3 |
| Bostan Mori | 3 |
| 逆元を求める | 5 |
| 二項係数を求める | 5 |
| セグメント木 | 4 |
| 遅延セグメント木 | 3 |
| 素数判定 | 4 |
| UnionFind | 5 |
| DFS | 4 |
| BFS | 4 |
| ベルマンフォード法 | 3 |
| ダイクストラ法 | 3 |
| ワーシャルフロイド法 | 3 |
| クラスカル法 | 4 |
| プリム法 | 3 |
| 平方分割 | 2 |
| フロー | 1 |
| 平面走査 | 2 |
| Grundy数 | 4 |
| Rolling Hash | 3 |
| 平方分割 | 2 |
6 次の目標
もちろん，入黄をしたいですが，数オリがあったということもあって，しばらく数学をやりたいので，競プロはのんびり，細く長く続けていきたいと思います．
また，来年はJOIで春合宿に行きたいです！
それでは，このあたりで記事を締めたいと思います．
僕が入黄したときにまたお会いしましょう！
(書きたいことがあったら入黄前に記事を書くかもしれませんが)