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

ZOI2と申します。先日のABC343にて入水したので、先人に倣って入水記事を書きます。

---

自己紹介

受験の結果待ちで胃が痛い高3。AtCoder名はZoi2。双子の弟(兄はZOIZOI)。
2022/11開始、2023/04入茶、2023/07入緑(入緑記事)、2024/03入水。
精進量がカス(入水時点でAccepted=263)。考察に強く、実装に弱い。

※この記事の内容のほとんどはAJL2023参加記と重複しています。ごめんね。

入緑時の知識

自力で書ける

• map,set,stack,queue,priority_queueなど
• 二分探索(lower_bound,upper_bound。めぐる式は怪しい)
• DP
• 累積和,imos法

存在は知っている(調べてコピペはできる)

• BFS,DFS
• modint
• UnionFind,scc
• next_permutation
• セグメント木、遅延セグメント木
• ダイクストラ法、ベルマンフォード法

多分このぐらい。グラフが弱いね。

軌跡

ABC311(ABCDE5完、パフォ1339、Rating942(+60))

D、BFSを真面目に書いたの初かも(だいぶ遅いけど)。E、時間の少ない中dpを実装してACをもぎ取れたのが相当大きい。

ABC312(ABCD4完、パフォ1289、Rating984(+42))

C、二分探索すらいらんのに何でdiffが727もあるのかわからん(自分ならBに置いて怒られそう)。Cまではとても速かったがDが遅くて台無し。あとEに黄diffを出すな。

AGC063(A1完、パフォ927、Unrated)

A{R,G}C初参加。A、今考えればそんなに難しい考察は要求されてないな。遅すぎる。まあ慣れてなかったししょうがないけど。(今解いてみたらゴミみたいなWAを吐きまくったが...)

ABC313(ABC3完、パフォ1194、Rating1009(+25))

コンテスト名がいかつい。難易度も100/300/400/550/...とABCとは思えない高さであり、3完早解き回だった。Bで1ズレをやらかして時間が蒸発したが、Cで何とか耐えてRatingが4桁に。この頃はなんだかんだ4ヶ月ぐらいで入水できるやろと楽観視していた。

ABC314(ABCD4完、パフォ890、Rating997(-12))

DとEの難易度差が非常に大きく、4完早解き回だった。BもCもDも遅すぎたためRating3桁に逆戻り。(半年以上前なので覚えていない上に、X(Twitter)を一時引退していたので当時何を考えていたかの情報がなく、何も書けない。)

AGC064(A1完、パフォ1603、Unrated)

Aの構築を爆速で思いつき、初の青パフォを獲得。残念なことに緑CoderなのでUnratedだったが、AJLのスコアが結構伸びてうれしい。この頃からABCとA{R,G}Cの成績の差が明確に表れ始めた。

ABC315(ABC3完、パフォ765、Rating974(-23))

Dに殺された。Eが簡単だったのでDを即飛ばせばEを解けた可能性はあったが、粘ってしまい無念の3完茶パフォ。入緑からここまでABCのパフォが単調に減少しており、よくない。

ABC317(ABCD4完、パフォ969、Rating973(-1))

DでただのナップサックDPに1時間かけてしまい、Eを解ききれず。なんとZoi2、EのグリッドBFSをコピペで持ってきているのである。こいつほんとに緑Coderか...?

ABC318(ABCE4完、パフォ1139、Rating992(+19))

D>EっぽかったのでEから解いた。Eの方針が一瞬で見えてすぐACしたが、DのbitDPを永遠にバグらせて4完。bitDP、(BFS/DFSよりはましだが)苦手。

WTF22-day1(A1完、パフォ1727、Unrated)

金曜日の真っ昼間から世界大会を開くAtCoderくん。AJL対象コンテストだと思っていたので、授業中に脳内でAを考え、休み時間にスマホで実装してAC。参加者が少なくパフォは高かったが、AJL非対象にされてしまい、授業を聞き流しただけの人になってしまった。

WTF22-day2(0完、パフォ2151、Unrated)

黄パフォすげえって思った?これ、0完です。世界大会の2日目(のOpenContest)なだけあって非常に難しい問題が揃っており、Aですら45人しかACできない超難易度コンテストだった。参加登録はしたが、普通に塾だったのでほとんど考えていない。

ABC319(ABDE4完、パフォ1373、Rating1038(+46))

Cみたいな全探索は嫌い。Eの周期性に素早く気づけた。Dが遅かったが、ABDE4完の人数が多くなかったので速度の影響は小さかった。久しぶりのRating大幅増。

ABC320(AB2完、パフォ724、Rating1009(-29))

Cでend()しか返ってこないupper_boundを書いて全てを吹き飛ばした。定期的にこういう事故が起きるのがよくない所。

ARC165(AB2完、パフォ1611、Unrated参加)

Bを嘘解法でACしてしまい、申し訳ない気持ちになった。AJLでは有利を得てしまったが、Unratedなので許してください。

ABC322(ABCE4完、パフォ1248、Rating1036(+27))

実装難死ね定期。Cは後ろからやれば二分探索をしなくて済む。Dを飛ばし、Eを長さpow(P+1,K)の1次元dpにしてAC。AJLで入賞圏内に入った。

ABC323(ABCDE5完、パフォ1281、Rating1064(+28))

C、100人目はボーナス気にしないといけないと勘違いして30分溶かした。Eで確率modを(多分)初AC。Fの難易度が高くなく、Cが早ければFが解けた可能性は十分にあったのでちょっと悲しい。

ARC166(B1完、パフォ1137、Rating1072(+8))

Bで、「3個しかないならrepより手で書いたほうがわかりやすい！」という絶望思考のもと、54個手で書くクソコードを錬成。Aが解けず1完で、遅い上にAとBが両方400点だったためパフォが伸びず。

ABC324(ABDE4完、パフォ1184、Rating1084(+12))

Cが解けないのひどすぎる。D、「0は平方数です」みたいな注意書きかtestcaseはあったほうがいいと思った(無限人死んでたので)。Eをギリギリ通して耐えた。

ARC167(AB2完、パフォ1406、Rating1121(+37))

B、Aの素因数が高々11種類なので多倍長整数でやってみたらうまくいった...が、実装力が0のため早解きに失敗し、青パフォのチャンスを逃した。

ABC325(ABCE4完、パフォ1112、Rating1120(-1))

Bがちょっと面倒。Eで初期化にint型の最大値を用いてしまい時間が爆散。激遅4完では-1もやむなし。Eのdiffが余裕で緑なの、もはやdijkstraは緑なら全人類知ってる前提っぽいな。

ABC326(ABE3完、パフォ1165、Rating1125(+5))

AJLのスコアの関係上、ABDE4完で水上位パフォを狙うのが最適と考えてCを飛ばした。結果Dでiとjを間違えてABE3完。Cを先にやればABCE4完でパフォ1400前後だったので作戦負け。

ABC327(ABCD4完、パフォ1162、Rating1129(+4))

D、二部グラフに気づいて判定方法を調べると頂点倍化UnionFindがあった。ぺたり。Eのdiffが1200ぐらいしかないの未だに納得してない。

ABC328(ABC3完、パフォ623、Rating1086(-43))

定期的な事故。Dでstackが出てこないの絶対なんかのバグだろ。Eは全域木ってなんだ...?から始まったからまあしゃーない。Fで重み付きUnionFindを知ってテンプレに追加した。

ABC329(ABCD4完、パフォ878、Rating1067(-19))

Dまで灰diff、Eから水diffの崖回。F解けないし別に早くもないしで、典型的な崖に負けた人になっていた。終了後にマージテクの計算量を知って驚愕。言われてみれば確かにlogだな...

ARC168(AB2完、パフォ1602、Rating1134(+67))

B、鉄則本で勉強したNimとgrundy数が大活躍し、持ち前の考察力を生かして早めにBをAC、青パフォを獲得。NimとかGrundy数は結構好き。(あとロリハもこのころ知って好きになった。)

ABC330(ABCDE5完、パフォ1403、Rating1164(+30))

かな～り久しぶりのABC成功。こういう感じの、なんというか重くなくて綺麗な感じの問題セットが得意。入水チャンス到来。

ABC331(AB2完、パフォ373、Rating1105(-59))

＿人人人＿
＞　2完　＜
￣Y^Y^Y^￣
CをACしていると思い込んでDに進んだら、CがWAしてたしDも解けず。世界一のカスムーブでRating大幅減。何してんの。

ARC169(A1完、パフォ1368、Rating1134(+29))

B、数学で殴る方向性で考察を進めてしまいdpを思いつけず。ABCが弱すぎるためARCは結構高いパフォが欲しいので、このパフォは悪くないけど微妙な感じ。

ABC332(ABC3完、パフォ1020、Rating1123(-11))

Dみたいな制約の小さい問題、実装難の場合が多いので見た瞬間捨てたりするのだが(実装難が嫌いすぎるため)、この回はE以降が難しかったので捨てられず。制約の小さい問題が全く解けない呪いにかかっている。

ABC333(ABCDE5完、パフォ1216、Rating1133(+10))

Bで2WAしてるのゴミすぎる。Eは後ろから見ればvectorぐらいしか使わずに解ける。F、modintの割り算の計算量をO(log998)と考えて間に合わないよな～と思っていたが、O(1)と考えて良かったらしく、後で出したら普通に間に合ってしまった。

AGC065(A1完、パフォ2018、Unrated)

覚醒回。考察力が爆発し、Aを30分ぐらいでACして黄パフォ。なおUnrated。AGCにRated参加したいというのが入水したい大きな理由の一つだったりする。

ABC334(ABCD4完、パフォ1197、Rating1139(+6))

Aのtestcaseが通らず、よく見たらGloveをGroveと書いていた。英語力。Dまではいい感じだったが、EでUnionFindをバグらせまくって4完どまり。入水は2024年に持ち越しとなった。

(共通テスト)

さすがに年始以降は勉強に専念し、共テに挑んだ。自己採836/900。とてもよい。

ABC336(ABCD4完、パフォ1431、Rating1172(+33))

共テが終わったその日の夜に、二次の勉強を放置してABCに参加。早解きに成功して再び入水チャンス到来。X(Twitter)にて「競プロer共テ合戦」¹なるものに参加し、めでたく優勝...と思いきや、ZOIZOIが共テの自己採をミスっており、ZOIZOIの点数が上がったため2位だった。残念。

(二次試験)

数学も物理も事故ってカスみたいな点数しかなく、相当怪しい。受かっててくれ～～～～。(結果が出てからこの記事を書こうとすると、ABC344の後になり、落緑の可能性があるため先に書いた。)

ABC343(ABCDF5完、パフォ1485、Rating1208(+36))

受験後の復帰戦兼入水戦。Fでセグ木に4つの情報(最大値とその個数、2番目の値とその個数)を乗せられた²のが勝因。入茶時や入緑時のように余裕でとはいかなかったが、無事入水することができた。ちなみにこれがF問題のコンテスト中初ACだったりする。

現在の知識

自力で書ける

• 入緑時の知識(自力で書ける)に書いたもの。めぐる式を含む
• BFS,DFS(さすがに書けるけど苦手意識あり)
• modint
• UnionFind,scc,重み付きUF
• next_permutation
• セグメント木
• ダイクストラ法
• bit全探索
• Nim,Grundy数
• 半分全列挙
• ローリングハッシュ

存在は知っている(調べてコピペはできる)

• 遅延セグメント木
• ベルマンフォード法,クラスカル法,ワーシャルフロイド法
• 畳み込み
• 最大流,最小費用流(大分怪しい)

多分このぐらい。鉄則本が優秀すぎる。ロリハみたいな変な高度典型を学ぶ前に基礎をやったほうが良いのは、それはそう。

展望

今は合格していることを全力で祈るのみ。↓は合格した前提の話。落ちてたら...知らん。
次の目標は年内入青。自律がカスなので留年しないように頑張りつつ、競プロのサークルに入って、化け物を眺めながら仲間と切磋琢磨して成長していきたい。あと兄を倒したい。

---

以上、入水記事でした。入青したらまた書きます。お読みいただきありがとうございました。

1. TwoSquirrelsさん主催の、(共テの点数)*2+(ABC336のパフォ)を競うイベント。 ↩

2. 「セグ木にのせる」、乗せると載せるのどっちが適切なのか、誰か教えてください。 ↩