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

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

---

自己紹介

とある競プロが強い高校に通う高3。AtCoder名はZoi2。双子の弟で、兄はZOIZOI(Qiitaはこれ)。使用言語はC++、エディタはVSCode。去年の11月にAtCoderを始め、約4.5ヶ月で入茶、約8ヶ月で入緑した。

契機

元々兄が競プロをやっているのを見たり話を聞いたりしていたので、競プロというものの存在は知っていた。兄の競プロ再開のタイミングで、暇だったのでちょっとやってみるか～ぐらいの気持ちで始めた。
↓兄の入緑記事より引用。間接的にはこれが僕が競プロを始めるきっかけということになる。

なぜ競プロを知ったのか、始めたのかはあまり覚えていないのですが、再開したきっかけは結構明確にあります。
2022/11/5~6に行われた、「パソコン甲子園」です。もちろんこの時点では競技プログラミングなどできないので、スマホアプリを作る部門での参加でしたが、なんか色々あってプログラミング部門の1位の方々と話す機会がありました。
僕は基本的にポジティブ、というか都合の悪いことは気にならないタイプなので、彼らが天才であることは忘れて「僕でもやってみたら伸びるんじゃね?!」と考えました。改めて見るとひどいですね...

帰宅後、とりあえずコンテストに出てみることにしました。もちろんテンプレもなく、Web開発などで使っていたVSCodeを引っ張り出してきました。11/12、ABC277です。

軌跡

開始～入茶

開始時の知識

• int,string
• cin,cout
• if
• for
• 高校範囲の数学的知識

多分このぐらい。何も知らないわけではないが、コンテストでは戦えない程度。

ABC277 (A1完、パフォ79、Rating4(+4))

初のコンテスト参加。当時、ifやforをかろうじて知っている程度の知識で参加したため、vectorがわからず検索しに行く有様だった。=と==を混同したりしながらなんとか1完。

ABC281 (A1完、パフォ101、Rating14(+10))

A問題で、for文の中にもi--を書いてしまい、ループ1回でiが2減る事故が発生して1WA。B問題で、stringのi文字目がchar型であることを知らず、'0'ではなく"0"と比較してCEしたり、0と比較してWAしたりしていた。

ABC283 (ABC3完、パフォ230、Rating34(+20))

^がpowでないことを知った。ABC281の反省を活かし、ちゃんと'0'と比較してC問題を通した。この辺で競プロ楽しい!ってなった。

ABC287 (ABC3完、パフォ496、Rating72(+38))

C問題にてグラフ初邂逅。当然BFSなどのグラフアルゴリズムは知らないので、端点からN-1回移動できるかを判定した。この回で初の茶パフォ&兄に勝利。

ABC288 (AB2完、パフォ223、Rating90(+18))

この回からテンプレを使い始めた。C問題を見て、前回のC問題より難しそうだな～ということはD<Cのパターンだな!と判断してD問題へ。全然そんなことなかった(C問題のdiffは436、D問題は1757(高すぎ))。これを受けて、コンテスト中に各問題の予想diffが見れる拡張機能を導入した。とても便利。

ABC289 (AB2完、パフォ359、Rating117(+27))

B問題がグラフで驚いた。グラフは分からないのでaに書いていない数字から戻っていった。C問題にてbit全探索初邂逅。色々調べてやり方は分かったが、B問題に時間を使いすぎて時間切れ。

ABC290 (ABC3完、パフォ779、Rating184(+67))

C問題でsetのありがたみを認識。D問題、ll P=(int型)*(int型)がオーバーフローすることを知らず大勝利を逃すが、十分勝利。このあたりから3完&茶パフォが安定してきた。

ABC293 (ABC3完、パフォ535、Rating221(+37))

C問題、bit全探索にリベンジ成功。D問題、ACLにこんなんあった気がするな～と思って探しに行ったらdsuがあったので、色々やったがTLE。cacheしてればACだった。

ABC294 (ABCD4完、パフォ680、Rating273(+52))

B問題みたいなcharを数字として扱う問題、'A'==65、'a'==97を覚えていた。ほぼ利益はないけど。この回で初の4完。この時はABC300までには入茶したいな～などと思っていた。

ABC296 (ABCDE5完、パフォ1403、Rating485(+212))

突然の覚醒。 初の緑パフォどころか水パフォをとってまさかの余裕で入茶。
D問題のような数学問は得意。E問題、時々ACLを眺めていたのが幸いし、sccで強連結成分分解することを思いついた。Rating更新後、茶色になった自分の名前とRatingグラフを眺めてしばらくニコニコしていた。

入茶～入緑

※Unratedの回は省略。

入茶時の知識

自力で書ける

• 開始時の知識に書いたもの
• ll,double,vector,pair,map,set,stack,queue,priority_queue
• charの計算('A'==65など)
• min,max,pow,sqrt,floor,ceil
• sort,reverse
• 累積和
• 貪欲法

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

• 二分探索
• BFS,DFS
• bitset
• dsu,scc

多分このぐらい。こいつなんでscc知ってるんだ...?

ABC297 (ABCD4完、パフォ504、Rating486(+1))

D問題、ansをllではなくintで作ってしまっているのに気付かずかなり時間とペナを消費。4完したにも関わらずRatingが+1止まりだったので、茶色こわいな～と思った。

ABC300 (AB2完、パフォ421、Rating476(-10))

B問題、vector<string>をvector<vector<string>>に入れる事故が発生。4重ループでcout << "Yes" << endlのネスト位置を間違えたりと色々ミスり、B問題までで88分(2WA)も消費してしまった。結果としてC問題は間に合わず、初めてRatingを下げてしまった。

ABC301 (ABC3完、パフォ861、Rating530(+54))

AtCoder Junior League(AJL)開始後初のコンテスト。D問題、powがdouble型であることを知らず、有効桁数不足でWA(後でテンプレにll型のpowを追加した)。ただC問題までが早かったのでパフォは良かった。この回から突然パフォが安定しだした。

ABC302 (ABCD4完、パフォ866、Rating575(+45))

B問題、何の工夫もせずに、if(S[i][j-1]=='n' && S[i][j-2]=='u' && S[i][j-3]=='k' && S[i][j-4]=='e')みたいなifを8個書いた。C問題、検索でdo~whileとnext_permutationを知った。D問題、vector<pair<価値,人>>を降順sortし、条件をみたす隣接2要素を見つけて戻っていった。

ABC303 (ABCD4完、パフォ1010、Rating634(+59))

D問題、連立漸化式だな～と思いながらDPを書いていた。僕は"DPは漸化式"派。

ABC305 (ABCD4完、パフォ941、Rating674(+40))

D問題、累積和を書きながら、B問題がいい練習問題になってるな～と思った。F問題、自力ではDFS書けなかった。ちなみに当時自力では二分探索も書けない。まじで...?

ABC307 (ABDE4完、パフォ1304、Rating765(+91))

C 問 題 、 許 さ ん(diff1307)
E問題、†最強の数学力†で隣接3項間漸化式を求めて解いたが、隣接2項間漸化式があったし、何なら一般項も導出可能だった。†最強†とは。入茶時以来の水パフォでAJL貢献&入緑リーチ。

ABC308 (ABCD4完、パフォ867、Rating776(+11))

C問題、long doubleを知らなかったので、__int128で分子に10^26ぐらい掛ければ精度足りるやろ!で無理やり通した(精度不足で2WA)。D問題、相変わらずDFSが書けないのでコピペで持ってきた。流石に書けないとやばい。

ABC310 (ABCE4完、パフォ1499、Rating882(+106))

D問題(E問題を解いてから戻ってきた)、二項係数の全探索の書き方がわからず死亡。E問題で、dp[i].{first,second}にS[i]=={'0','1'}としたときのそれ以降の和を入れるDPを思いついたのが勝因。3度目の水パフォ&最高パフォ(入茶時)を更新し、これまた余裕で入緑した。

現在

現在の知識

自力で書ける

• 入茶時の知識(自力で書ける)に書いたもの
• 二分探索(lower_bound,upper_bound。めぐる式は怪しい)
• DP
• imos法

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

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

自力で書けるものは入茶時からそんなに増えていない。調べれば通せるので今のところは何とかなっている。

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

記事作成をさぼりすぎたせいで入緑後のコンテストが記事になってしまった。
D問題、やっとBFSがまともに書けるようになった(ただし覚えていない)。E問題、無理では?と思いながらTLE解法を書いていたら突然DPが生えて残り2分で通した。天才。vs兄の勝率も上がってきた。

展望

大学受験のためいつまでAtCoderができるかは不明だが、AJL高3でいい感じの順位(あわよくば20位以内)をとって、受験後でもいいのでいつかは入水したい。あと兄を倒したい。

---

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

(2023/08/17追記)兄が入水しました。めでたい。入水記事見てあげてね。
(2024/03/09追記)入水しました。いえーい。入水記事見てね。