【色変記事】AtCoderで入水した話 by ZOI2

ZOI2と申します。先日のABC343にて入水したので、先人に倣って入水記事を書きます。
***
# 自己紹介
受験の結果待ちで胃が痛い高3。AtCoder名は[Zoi2](https://atcoder.jp/users/Zoi2 "Zoi2 - AtCoder")。双子の弟(兄は[ZOIZOI](https://atcoder.jp/users/ZOIZOI "ZOIZOI - AtCoder"))。
2022/11開始、2023/04入茶、2023/07入緑([入緑記事](https://qiita.com/ZOI2/items/6dd677775270eb65aae9 "【色変記事】AtCoderで入緑した話 by ZOI2"))、2024/03入水。
精進量がカス(入水時点でAccepted=263)。考察に強く、実装に弱い。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3513813/a7805005-3daa-03ca-1240-f8a6e867fdf6.png)
※この記事の内容のほとんどは[AJL2023参加記](https://qiita.com/ZOI2/items/59032515eec209c31b75 "AtCoder Junior League 2023 参加記 by ZOI2")と重複しています。ごめんね。

# 入緑時の知識
#### 自力で書ける
* map,set,stack,queue,priority_queueなど
* 二分探索(lower_bound,upper_bound。めぐる式は怪しい)
* DP
* 累積和,imos法
#### 存在は知っている(調べてコピペはできる)
* BFS,DFS
* modint
* UnionFind,scc
* next_permutation
* セグメント木、遅延セグメント木
* ダイクストラ法、ベルマンフォード法

多分このぐらい。グラフが弱いね。
# 軌跡
### ABC311(<font color="#808080">AB</font><font color="#804000">C</font><font color="#008000">D</font><font color="#00C0C0">E</font>5完、パフォ<font color="#00C0C0">1339</font>、Rating<font color="#008000">942</font>(+60))
D、BFSを真面目に書いたの初かも(だいぶ遅いけど)。E、時間の少ない中dpを実装してACをもぎ取れたのが相当大きい。
### ABC312(<font color="#808080">AB</font><font color="#804000">C</font><font color="#008000">D</font>4完、パフォ<font color="#00C0C0">1289</font>、Rating<font color="#008000">984</font>(+42))
C、二分探索すらいらんのに何でdiffが<font color="#804000">727</font>もあるのかわからん(自分ならBに置いて怒られそう)。Cまではとても速かったがDが遅くて台無し。あとEに黄diffを出すな。
### AGC063(<font color="#008000">A</font>1完、パフォ<font color="#008000">927</font>、Unrated)
A{R,G}C初参加。A、今考えればそんなに難しい考察は要求されてないな。遅すぎる。まあ慣れてなかったししょうがないけど。(今解いてみたらゴミみたいなWAを吐きまくったが...)
### ABC313(<font color="#808080">AB</font><font color="#804000">C</font>3完、パフォ<font color="#008000">1194</font>、Rating<font color="#008000">1009</font>(+25))
コンテスト名がいかつい。難易度も100/300/400/550/...とABCとは思えない高さであり、3完早解き回だった。Bで1ズレをやらかして時間が蒸発したが、Cで何とか耐えてRatingが4桁に。この頃はなんだかんだ4ヶ月ぐらいで入水できるやろと楽観視していた。
### ABC314(<font color="#808080">ABC</font><font color="#804000">D</font>4完、パフォ<font color="#008000">890</font>、Rating<font color="#008000">997</font>(-12))
DとEの難易度差が非常に大きく、4完早解き回だった。BもCもDも遅すぎたためRating3桁に逆戻り。(半年以上前なので覚えていない上に、X(Twitter)を一時引退していたので当時何を考えていたかの情報がなく、何も書けない。)
### AGC064(<font color="#008000">A</font>1完、パフォ<font color="#0000FF">1603</font>、Unrated)
Aの構築を爆速で思いつき、初の青パフォを獲得。残念なことに緑CoderなのでUnratedだったが、AJLのスコアが結構伸びてうれしい。この頃からABCとA{R,G}Cの成績の差が明確に表れ始めた。
### ABC315(<font color="#808080">ABC</font>3完、パフォ<font color="#804000">765</font>、Rating<font color="#008000">974</font>(-23))
Dに殺された。Eが簡単だったのでDを即飛ばせばEを解けた可能性はあったが、粘ってしまい無念の3完茶パフォ。入緑からここまでABCのパフォが単調に減少しており、よくない。
### ABC317(<font color="#808080">AB</font><font color="#804000">C</font><font color="#008000">D</font>4完、パフォ<font color="#008000">969</font>、Rating<font color="#008000">973</font>(-1))
DでただのナップサックDPに1時間かけてしまい、Eを解ききれず。なんとZoi2、EのグリッドBFSをコピペで持ってきているのである。こいつほんとに緑Coderか...?
### ABC318(<font color="#808080">AB</font><font color="#804000">C</font><font color="#008000">E</font>4完、パフォ<font color="#008000">1139</font>、Rating<font color="#008000">992</font>(+19))
D>EっぽかったのでEから解いた。Eの方針が一瞬で見えてすぐACしたが、DのbitDPを永遠にバグらせて4完。bitDP、(BFS/DFSよりはましだが)苦手。
### WTF22-day1(<font color="#0000FF">A</font>1完、パフォ<font color="#0000FF">1727</font>、Unrated)
金曜日の真っ昼間から世界大会を開くAtCoderくん。AJL対象コンテストだと思っていたので、授業中に脳内でAを考え、休み時間にスマホで実装してAC。参加者が少なくパフォは高かったが、AJL非対象にされてしまい、授業を聞き流しただけの人になってしまった。
### WTF22-day2(0完、パフォ<font color="#C0C000">2151</font>、Unrated)
黄パフォすげえって思った?これ、0完です。世界大会の2日目(のOpenContest)なだけあって非常に難しい問題が揃っており、Aですら45人しかACできない超難易度コンテストだった。参加登録はしたが、普通に塾だったのでほとんど考えていない。
### ABC319(<font color="#808080">AB</font><font color="#804000">D</font><font color="#00C0C0">E</font>4完、パフォ<font color="#00C0C0">1373</font>、Rating<font color="#008000">1038</font>(+46))
Cみたいな全探索は嫌い。Eの周期性に素早く気づけた。Dが遅かったが、ABDE4完の人数が多くなかったので速度の影響は小さかった。久しぶりのRating大幅増。
### ABC320(<font color="#808080">AB</font>2完、パフォ<font color="#804000">724</font>、Rating<font color="#008000">1009</font>(-29))
Cでend()しか返ってこないupper_boundを書いて全てを吹き飛ばした。定期的にこういう事故が起きるのがよくない所。
### ARC165(<font color="#808080">A</font><font color="#00C0C0">B</font>2完、パフォ<font color="#0000FF">1611</font>、Unrated参加)
Bを嘘解法でACしてしまい、申し訳ない気持ちになった。AJLでは有利を得てしまったが、Unratedなので許してください。
### ABC322(<font color="#808080">ABC</font><font color="#008000">E</font>4完、パフォ<font color="#00C0C0">1248</font>、Rating<font color="#008000">1036</font>(+27))
実装難死ね定期。Cは後ろからやれば二分探索をしなくて済む。Dを飛ばし、Eを長さpow(P+1,K)の1次元dpにしてAC。AJLで入賞圏内に入った。
### ABC323(<font color="#808080">ABC</font><font color="#008000">D</font><font color="#00C0C0">E</font>5完、パフォ<font color="#00C0C0">1281</font>、Rating<font color="#008000">1064</font>(+28))
C、100人目はボーナス気にしないといけないと勘違いして30分溶かした。Eで確率modを(多分)初AC。Fの難易度が高くなく、Cが早ければFが解けた可能性は十分にあったのでちょっと悲しい。
### ARC166(<font color="#008000">B</font>1完、パフォ<font color="#008000">1137</font>、Rating<font color="#008000">1072</font>(+8))
Bで、「3個しかないならrepより手で書いたほうがわかりやすい！」という絶望思考のもと、54個手で書くクソコードを錬成。Aが解けず1完で、遅い上にAとBが両方400点だったためパフォが伸びず。
### ABC324(<font color="#808080">AB</font><font color="#008000">DE</font>4完、パフォ<font color="#008000">1184</font>、Rating<font color="#008000">1084</font>(+12))
Cが解けないのひどすぎる。D、「0は平方数です」みたいな注意書きかtestcaseはあったほうがいいと思った(無限人死んでたので)。Eをギリギリ通して耐えた。
### ARC167(<font color="#808080">A</font><font color="#00C0C0">B</font>2完、パフォ<font color="#00C0C0">1406</font>、Rating<font color="#008000">1121</font>(+37))
B、Aの素因数が高々11種類なので多倍長整数でやってみたらうまくいった...が、実装力が0のため早解きに失敗し、青パフォのチャンスを逃した。
### ABC325(<font color="#808080">AB</font><font color="#804000">C</font><font color="#008000">E</font>4完、パフォ<font color="#008000">1112</font>、Rating<font color="#008000">1120</font>(-1))
Bがちょっと面倒。Eで初期化にint型の最大値を用いてしまい時間が爆散。激遅4完では-1もやむなし。Eのdiffが余裕で緑なの、もはやdijkstraは緑なら全人類知ってる前提っぽいな。
### ABC326(<font color="#808080">AB</font><font color="#00C0C0">E</font>3完、パフォ<font color="#008000">1165</font>、Rating<font color="#008000">1125</font>(+5))
AJLのスコアの関係上、ABDE4完で水上位パフォを狙うのが最適と考えてCを飛ばした。結果Dでiとjを間違えてABE3完。Cを先にやればABCE4完でパフォ<font color="#00C0C0">1400</font>前後だったので作戦負け。
### ABC327(<font color="#808080">ABC</font><font color="#804000">D</font>4完、パフォ<font color="#008000">1162</font>、Rating<font color="#008000">1129</font>(+4))
D、二部グラフに気づいて判定方法を調べると頂点倍化UnionFindがあった。ぺたり。Eのdiffが<font color="#00C0C0">1200</font>ぐらいしかないの未だに納得してない。
### ABC328(<font color="#808080">ABC</font>3完、パフォ<font color="#804000">623</font>、Rating<font color="#008000">1086</font>(-43))
定期的な事故。Dでstackが出てこないの絶対なんかのバグだろ。Eは全域木ってなんだ...?から始まったからまあしゃーない。Fで重み付きUnionFindを知ってテンプレに追加した。
### ABC329(<font color="#808080">ABCD</font>4完、パフォ<font color="#008000">878</font>、Rating<font color="#008000">1067</font>(-19))
Dまで灰diff、Eから水diffの崖回。F解けないし別に早くもないしで、典型的な崖に負けた人になっていた。終了後にマージテクの計算量を知って驚愕。言われてみれば確かにlogだな...
### ARC168(<font color="#808080">A</font><font color="#00C0C0">B</font>2完、パフォ<font color="#0000FF">1602</font>、Rating<font color="#008000">1134</font>(+67))
B、鉄則本で勉強したNimとgrundy数が大活躍し、持ち前の考察力を生かして早めにBをAC、青パフォを獲得。NimとかGrundy数は結構好き。(あとロリハもこのころ知って好きになった。)
### ABC330(<font color="#808080">AB</font><font color="#804000">CD</font><font color="#008000">E</font>5完、パフォ<font color="#00C0C0">1403</font>、Rating<font color="#008000">1164</font>(+30))
かな～り久しぶりのABC成功。こういう感じの、なんというか重くなくて綺麗な感じの問題セットが得意。入水チャンス到来。
### ABC331(<font color="#808080">AB</font>2完、パフォ<font color="#808080">373</font>、Rating<font color="#008000">1105</font>(-59))
＿人人人＿
＞　**2完**　＜
￣Y^Y^Y^￣
CをACしていると思い込んでDに進んだら、CがWAしてたしDも解けず。世界一のカスムーブでRating大幅減。何してんの。
### ARC169(<font color="#008000">A</font>1完、パフォ<font color="#00C0C0">1368</font>、Rating<font color="#008000">1134</font>(+29))
B、数学で殴る方向性で考察を進めてしまいdpを思いつけず。ABCが弱すぎるためARCは結構高いパフォが欲しいので、このパフォは悪くないけど微妙な感じ。
### ABC332(<font color="#808080">ABC</font>3完、パフォ<font color="#008000">1020</font>、Rating<font color="#008000">1123</font>(-11))
Dみたいな制約の小さい問題、実装難の場合が多いので見た瞬間捨てたりするのだが(実装難が嫌いすぎるため)、この回はE以降が難しかったので捨てられず。制約の小さい問題が全く解けない呪いにかかっている。
### ABC333(<font color="#808080">ABC</font><font color="#804000">D</font><font color="#008000">E</font>5完、パフォ<font color="#00C0C0">1216</font>、Rating<font color="#008000">1133</font>(+10))
Bで2WAしてるのゴミすぎる。Eは後ろから見ればvectorぐらいしか使わずに解ける。F、modintの割り算の計算量をO(log998)と考えて間に合わないよな～と思っていたが、O(1)と考えて良かったらしく、後で出したら普通に間に合ってしまった。
### AGC065(<font color="#0000FF">A</font>1完、パフォ<font color="#C0C000">2018</font>、Unrated)
覚醒回。考察力が爆発し、Aを30分ぐらいでACして黄パフォ。なおUnrated。AGCにRated参加したいというのが入水したい大きな理由の一つだったりする。
### ABC334(<font color="#808080">A</font><font color="#804000">B</font><font color="#008000">C</font><font color="#804000">D</font>4完、パフォ<font color="#008000">1197</font>、Rating<font color="#008000">1139</font>(+6))
Aのtestcaseが通らず、よく見たらGloveをGroveと書いていた。英語力。Dまではいい感じだったが、EでUnionFindをバグらせまくって4完どまり。入水は2024年に持ち越しとなった。
### (共通テスト)
さすがに年始以降は勉強に専念し、共テに挑んだ。自己採836/900。とてもよい。
### ABC336(<font color="#808080">ABC</font><font color="#008000">D</font>4完、パフォ<font color="#00C0C0">1431</font>、Rating<font color="#008000">1172</font>(+33))
共テが終わったその日の夜に、二次の勉強を放置してABCに参加。早解きに成功して再び入水チャンス到来。X(Twitter)にて「競プロer共テ合戦」[^1]なるものに参加し、めでたく優勝...と思いきや、ZOIZOIが共テの自己採をミスっており、ZOIZOIの点数が上がったため2位だった。残念。
[^1]:TwoSquirrelsさん主催の、(共テの点数)*2+(ABC336のパフォ)を競うイベント。
### (二次試験)
数学も物理も事故ってカスみたいな点数しかなく、相当怪しい。受かっててくれ～～～～。(結果が出てからこの記事を書こうとすると、ABC344の後になり、落緑の可能性があるため先に書いた。)
### ABC343(<font color="#808080">ABC</font><font color="#804000">D</font><font color="#00C0C0">F</font>5完、パフォ<font color="#00C0C0">1485</font>、Rating<font color="#00C0C0">1208</font>(+36))
受験後の復帰戦兼入水戦。Fでセグ木に4つの情報(最大値とその個数、2番目の値とその個数)を乗せられた[^2]のが勝因。入茶時や入緑時のように余裕でとはいかなかったが、無事入水することができた。ちなみにこれがF問題のコンテスト中初ACだったりする。
[^2]:「セグ木にのせる」、乗せると載せるのどっちが適切なのか、誰か教えてください。
# 現在の知識
#### 自力で書ける
* 入緑時の知識(自力で書ける)に書いたもの。めぐる式を含む
* BFS,DFS(さすがに書けるけど苦手意識あり)
* modint
* UnionFind,scc,重み付きUF
* next_permutation
* セグメント木
* ダイクストラ法
* bit全探索
* Nim,Grundy数
* 半分全列挙
* ローリングハッシュ
#### 存在は知っている(調べてコピペはできる)
* 遅延セグメント木
* ベルマンフォード法,クラスカル法,ワーシャルフロイド法
* 畳み込み
* 最大流,最小費用流(大分怪しい)

多分このぐらい。鉄則本が優秀すぎる。ロリハみたいな変な高度典型を学ぶ前に基礎をやったほうが良いのは、それはそう。
# 展望
今は合格していることを全力で祈るのみ。↓は合格した前提の話。落ちてたら...知らん。
次の目標は年内入青。自律がカスなので留年しないように頑張りつつ、競プロのサークルに入って、化け物を眺めながら仲間と切磋琢磨して成長していきたい。あと**兄を倒したい**。
***
以上、入水記事でした。入青したらまた書きます。お読みいただきありがとうございました。