JOI 春合宿 2021 / AtCoder 橙
要約
"Hello, World!" から広義1年で AtCoder 橙 / IOI 日本代表 になるまでの記録
橙コーダーと、申します
— yuto (@yuto1115_cp) 2021年3月14日
yuto1115さんのAtCoder Regular Contest 114での成績：18位
パフォーマンス：3133相当
レーティング：2387→2488 (+101) :)
Highestを更新し、三段になりました！#AtCoder #ARC114 pic.twitter.com/DyU8WQDXdL
日本代表になりました
— yuto (@yuto1115_cp) 2021年3月23日
JOI 春合宿の問題に関する言及があります。ネタバレが始まる前にネタバレ部分を飛ばすリンクがあるので、飛ばしたい人は踏んでください。
2019/12
同じクラスだった友人の勧めで競プロを始めた。初めに使う言語として Golang を推されたので、本を借りて Golang の勉強をした。ンコソパのンの字も知らなかったので、色々と教えてもらいながら習得した。
2020/01-02
適当に ABC-A, B, C あたりを埋めたりコンテストに出たりしていた。2月中旬に茶色になった。
C++ は危険だからやめとけと言っていた友人を裏切って、APG4B を使って C++ に乗り換えた。
古いパソコンを使っていたのでかなり重く、動かなかった時にスマホコーディングで ABC に出たら冷えた。
2020/03-04
学校が休校になり、一日中競プロをしていた。今までで一番精進をしていた時期。
蟻本を買い、けんちょんさんの記事（AtCoder 版！蟻本 (初級編) - Qiita）の練習問題や参考記事を見ながら初級編を進めた。
3月上旬に緑になった。
4月上旬に水色になった。
新しいパソコンを買ってもらった。
2020/05-06
友達が家に来ていた日に ABC が重なってしまい、みんなが休憩モードになったのでこっそり部屋に戻って ABC に出ていたが、途中で呼ばれてしまったためリビングで UNO をしながら部屋で ABC に出ていた。すると、初 2400 perf. をとって青になった。
その後は ARC, AGC が続いたこともあってレートが伸びず、初めての停滞を経験した。
精進としては、蟻本の初級編と中級編をやっていた。
2020/07-08
7月くらいからコンテスト成績が上がり始め、停滞から抜け出した。
青 diff を埋めたり、EDPC を解いたりしていた。
8月末に情報オリンピックの夏季セミナーに参加した。JOI のイベントに参加するのは初めてだったので、twitter でしか知らなかった中高生競プロer達と交流できてとても楽しかった。暖色だらけでかなりビビっていた。
最終日の発表の自己紹介で、翌日に黄色になることを宣言した。黄色になった。
2020/09-11
暖色の人たちが rated 不足を嘆いているのをずっと聞いていたのでそれなりに覚悟はしていたが、いざ自分が黄色になるとすぐに ARC が増え始め、結局 rated 過疎を経験しなかった。ゆとり世代とお呼びください。
とはいってもすぐにレートが上がるわけではなく、3~4ヶ月くらい黄溜まりから抜け出せずにいた。
黄 diff に手を出したり、JOI の難易度 7~8 を埋めたりしていた。
2020/12
JOI の2次予選に参加した。本選には絶対に行く、春合宿まで行ければ大満足、というのが当初の目標だった。
結果は全完で、理事長賞を頂いた。嬉しい。
本選に向けて、JOI の難易度 9 を埋め始めた。
AGC にかなりの苦手意識があったので Good Bye rng_58 コンに出るのは怖かったが、実際に出てみると2日連続でいい結果が出せ、一気にレートが +119 した。これは1月中か2月中に橙になれるのでは？とか思っていた。
2021/01-02
ところがそううまくはいかず、橙手前までは行ったが微妙に届かなかった。
1月初めにパ研合宿に外部枠として参加した。オンサイトイベントは初だったのでとても楽しかった。2日目と始業式が被って参加できず、残念だった。
JOI 本選に参加した。メダルとはいかなかったが、春合宿への参加権を獲得した。
春合宿に向けて難易度 10 を解き始めた。難しかったが、思っていたよりは解けた。
2021/03
テスト勉強をしていたので、しばらく精進ができていなかった。その状態で AGC に出てみたところ、全く思考が回らず1問も解けなかったので撤退した。
テストが終わったので、思考能力を回復させるために精進をした。SSRS さんのバチャに参加するなどして去年の春合宿の問題を解いた。代表ボーダーには遠く及ばなかったので、今年は春合宿を経験して、来年本気で代表を目指そうと思っていた。
Day 0
科学の甲子園全国大会に参加した。情報の筆記を担当した。（筆記は優勝していたらしい。やったね！！！）
筆記が終わり、つくばからホテルのある渋谷に移動した。
渋谷駅を出てホテルまで歩いていたが、携帯の充電が1桁だったので「渋谷の路頭に迷うところだったwww」みたいなツイートを後でしようと考えていたところ、残り5％から急に電源が落ちて真顔になった。幸い iPad を持っていたので、コンビニの free Wi-Fi があるところでは地図が見れた。隣のコンビニに行く→間違っていたので戻る→他の隣のコンビニに行く→合っていたので次のステップ みたいな DFS でなんとか到着できた。事務局の方、めっちゃ遅れてすいません。
夕飯は焼肉弁当だった。美味しかった。
ここから JOI 春合宿の問題に関する言及があります。飛ばしたい方はこちら。
Day 1
絶起しなかった。さすが。起床界のt（略）。
人々と会った。すごく非日常空間だった。
持参していたキーボードを繋ごうと思ったところ、USB-C がついておらず、絶望した。去年はこの PC でしたよ〜って言ってた PC には付いてたのに...... 慣れない日本語配列での競技が確定した。
競技が始まった。1問目が Output only だったのでかなりビビったが、他の人よりはできる自信があったので取り組んだ。とりあえず 2-opt と 2点 swap で焼きなましをするのが最初に思いついたので、実装した。細かいパラメータ調節を繰り返して、50点くらいを得た。
2問目を見た。自明な5点をまず取った。シミュレーションには解説とはちょっと違うダイクストラ的なものをやった。（衝突時刻をコストとして持つ辺を張ると、ある人が感染する条件は、コストが単調増加なその人までのパスが存在すること。dp[i] = i までの単調増加パスのうち、最後の辺のコストの最小値 と定義すると、ダイクストラ風に更新できる。最短経路問題では無いが。）それ以降も考えたがわからなかったので捨てた。こういう明らかに全探索が無理そうなやつは、「実は探索する必要があるパターンは少しだけ」を疑うべきだった。反省。
3問目を見た。自明部分点とパラレルバイナリサーチによる小課題6をとった。小課題4が取れれば89点が取れたので必死に考えたが、chmax / add を合成できるという発想に至らなかった。その日の ABC-E で本質が出てかなりびっくりした。精進不足です。
1問目に戻ってきて、現在最小値をとる角のまわりが優先的に選ばれるようにしたらちょっと改善して、65点を得た。
下の方だろうな〜と思いながら結果を見ると4位だったので、かなり驚いた。
水3本と蒟蒻ゼリー1本を飲んだ。
夕飯は油淋鶏弁当だった。美味しかった。
Day 2
絶起しなかった。さすが。起床界のt（略）。
1問目を見た。一度日を跨げばそれ以降は前計算でまとめられるのは分かったが、日を跨がない移動の計算がわからず一旦飛ばした。
2問目を見た。いつもの45°回転をすると、平面走査 and 二分探索の解法がすぐに生えた。K 回二分探索をする解法で K=10 行けるかな〜と思って提出すると、K=1 しか通らない。もう少し考えると、一回だけ二分探索して上界を見つければ、あとは全列挙できることに気づく。これで K=10 解けたぜ〜と思って提出すると、まさかの100点。よく考えたら別に K=10 の必要はなかった。ただし log は二つつけているので犯罪でした。通した人全員犯罪だったけど。
3問目を見た。設定がめっちゃシンプルなので自明枠か？と思ったが、すぐに激ヤバであることに気づく。バケット法を使って10点を獲得し、それ以降は諦めた。正しい判断だった。
1問目に戻ってくると、最短経路が高々 M 回しか変化しないことに気づき、これ間に合うのか〜？とかいいながら NM 回ダイクストラする解法を書くと、最後の小課題を除いて通った。密なグラフだと prique 使った方が遅くなるの、それはそうなんだけど非自明。
この日の成績は同率1位で、合計で3位に浮上した。あまり狙っていなかった代表だったが、狙える位置にあるとなって、急に今年に代表になりたいという思いが出てきた。
水4本と蒟蒻ゼリー2本を飲んだ。
帰りに暴風雨に遭遇し、使っていた骨の1本折れた傘が、骨の2本折れた傘に進化した。
夕飯は串焼き弁当だった。美味しかった。
こっちに全競争心が向いた結果、夜に出た ARC では今までに出た AtCoder rated で一番やる気が湧かなかった。結果も酷かった。それなのにレートが上がったので、これもう冷えるビジョン見えなくない？とか言ってた。フラグにならないことを祈る。
Day 3
1問目を見た。ビット数的にどうせ貪欲だろという気持ちで眺めると、貪欲解が生える。1時間程度で70点を獲得し、次の問題に移った。
2問目を見た。最初の部分点を取るが、それ以降はわからず一旦飛ばす。
3問目を見た。木DPで20点を取るが、それ以降が全然わからない。
どれも解ける気がしなかったので迷ったが、一番チャンスがありそうな2問目に脳の資源を費やしたところ、残り1時間を切ってから45°回転を思いつき、座圧DPで28点を獲得した。時間が足りず、これで終わってしまった。48点は全探索なので解けるべきだったが、CHTはほえ〜〜〜〜って感じだった。CHT 未履修です（おい）
この日の結果は4位で、合計3位もキープしていたが、昨日までは100点以上あった5位との差が60点になっていて、かなり焦った。
水5本と蒟蒻ゼリー2本を飲んだ。
夕飯は生姜焼き弁当だった。美味しかった。
この日の夜はかなり緊張していて、足が震えたりもしていた。
かなり暇だったので Youtube を見始めたら、気づくと1時になっていた。よくない。大事なコンテストの前は早く寝ようね。
Day 4
毎日飲んでいた蒟蒻ゼリーが無かったので動揺した。かなしい。
1問目を見た。2乗解ならすぐ生やせるだろうという勘があったので考えると、生えた。何度かバグらせたが、焦らずにバグ取りをして無事部分点を獲得。トイレに行くとダブリングが思いついたので、戻ってきて実装。満点を獲得した。これでかなり緊張がほぐれた。後にわかるが、この時点で代表が確定していた。
2問目を見た。37 解は自明なので 27 解を考えた。手元で色々なお絵かきをすると、1 x 1 の市松と 2 x 2 の市松を組み合わせた模様で行けることがわかった。頑張って実装とバグ取りをして、39点を獲得。
3問目を見た。まず簡単な木DPで最初の部分点を取る。JOI の木の問題の N <= 105 はどうせマージテク（要出典）なので、なにか部分木の要素数以下であるものがないか探すと、DPの差分が該当することがわかった。頑張って実装して2番目の部分点を取った時はかなり安心した。functional graph の場合も考えると、ループ上の頂点だけ別処理を加えてうまくやるとできることに気づき、満点を獲得した。解説の木に帰着する方法、なるほどなあ。
昼食時に近くに maroon さんがいて思わず二度見してしまった。
流石にこれで代表になれなかったらキツイな、と思っていたが無事代表になっていた。この日の成績は単独1位で、合計としては2位になっていた。めっちゃ嬉しかった。
水6本とよく分からないゼリー1本を飲んだ。日に日に増えた水の量だが、最終日は2L飲んだ。
写真撮影が長かった。
（日本代表写真撮影にて）
事務局の人A「それじゃあメダルもつけて写真撮りましょうか〜〜」
事務局の人B「一人メダルないですね」
事務局の人A「あ、じゃあやっぱメダル外しましょう〜〜」
メダルを取っていない代表がいてごめんなさい。
帰りの電車で、代表になったことを twitter で報告した。1晩でフォロワーが70人増えてかなりびっくりした。橙になった時の比じゃない。
他3人は想定していたが自分は非想定だった的なコメントがちらほら見えた。その気持ちよく分かります。自分が一番驚いているので。
感想（ポエム）
一年前、自分がまだ競プロを始めたばかりの頃、twitter で本選、春合宿、そして代表と活躍する中高生の存在を知り、心から尊敬するとともに、いつか自分もその場所に立ちたいと思っていました。まさか1年後にそれを達成できるとは自分でも驚きですが、代表になった以上は、自分も他の競プロerの目標となれるような実力をつけていきたいと思います。よろしくお願いします。
今後の目標
IOI の問題とかを一問も解いていないので、IOI、APIO、JOI オープンコンテストとかのバチャをたくさんやりたい。
あと、他の代表に比べてレートがかなり貧弱なので上げないとやばい。IOI までに最低限 AtCoder 2600 には乗せたい。
来年の春合宿には赤コーダーとして参加したいです。
色変記事恒例の精進量とかを載せるやつ
こうして見ると、全然精進していなくて、涙......
