JOI2022/2023 本選参加記
はじめに
2/12(日)にあったJOI2022/2023の本選に参加して、春合宿に進出することができました。参加記を書かないと今回のことを忘れちゃうので書こうと思います。
今までのJOI
JOI2019/2020 出たけど結果を覚えていない…
JOI2020/2021 2次予選落ち。2問目のパンケーキで、ある程度の考察ができたにも関わらず、テンパって次の問題に進んでしまう。そこでも何もできず、合計100点という結果に。
JOI2021/2022 定員が増えたこともあって、本戦は通過できたけど、本戦で選挙に勝てなかった。春合宿に行くのは難しいなと感じた。
JOI精進はこんな感じ。
本戦3週間前
1/22(日)のARC154でついに黄コーダーになった。レートが初めて1900を超えてから1年半ほどずっと停滞していたから、めちゃくちゃ嬉しかった。本戦落ち黄コーダーにはなりたくないな。
本選前日
本選では持てる実力を全て出し切りたいので、前日は自分のライブラリに入っているアルゴリズムの復習をした。あと、EDPCの問題の解法をさらったりした。
当日の朝
問題を解いて体を慣らそうかと思ったけど、パソコンの前に立つとそわそわして全然落ち着かなかったので、リビングに行って、カービィのYoutubeを見てた。かわいかった。
競技直前は軽く体を動かしたあと、ちゃんとPCの横にプーさんのぬいぐるみをセット。kawaii!
競技
13:00 本選が始まった。いざ！
1問目
問題を見る。
うーん。O(N2)からどうやって落とすんだ...と悩んだけど、左から順に見ていって碁石をひっくり返すパートも、最後にひっくり返して出力するパートもO(N)に落とすことができると分かったので、頭を整理しながら実装。
13:28 AC。実装がバグったので少し時間がかかっちゃった。
2問目
問題を見る。
うーん。最初は何から手を付けていいか分からずに考察用紙にいろいろと書きなぐっていた。そしたら、「誰かに献本されるということがない人」だけに献本すればいいと分かる。てことは横軸Xで縦軸Eのグラフを書いてみて45℃回転か。
14:28 AC。実装のミスに気付かず、バグ取りにだいぶ時間を取られた。
ここまでで約1時間半と結構時間が経ってしまったが、もう過去のことなので忘れて次に行く。
3問目
問題を見る。
制約がRC<=6×106 か...。はんこが押されたマス全てを愚直に考えていたらO(RCN2)で全然だめなので、とりあえずN2の部分を抑えたい。少し考察すると、あるマスでハンコを押すことを考えて領域内を全部見た後、1マス動いてそこでハンコを押す時は、領域の端2N-1個のマスだけ考えればいいので、O(RCN)になるなと思った。とりあえずこれで計46点くらい取ろうと思った。
15:27 提出。
あまり実装がうまくできなかった。どうしたら改善できるか思いつかなかったので、この解法で行くのは諦め、もっと簡潔な実装方法を考えた。考察してるうちに次の解法を思いついた。
解法
この解法を思いついた時にはもう実装することで頭がいっぱいで、計算量の話もこれで何点取れるかも考えていなかった（よくない）けど、実はO(RClogN)解法だったっぽい。
16:16 提出
領域内で斜めの方向に動かすところを一応直してみる。でも直さなくても小課題1はあってるはずなんだけどな。
16:35 提出
うーん。あってるはずなのに、ていうか小課題1も取れないのはなぜ？いろんなテストケースを考えてローカルで試しても、全て正しい答えが返ってくる。
そして気づいたら競技終了まであと20分になっていた。
ところで今の僕の点数は200点。C,D,Eの部分点はひとつも取っていない。D問題は目は通したけど考察はしてないし、E問題はPDFのダウンロードすらしていない。やばい。C問題はあきらめるか？と一瞬考えたけど、ここでD,Eの自明部分点をとっても春合宿に行けるはずはなかった。もうC問題でねばるしかなかった。
実装でバグっているのはBFSの箇所なのかなと思い、コードをより簡潔にするために、斜めの移動を消して横移動だけのコードに書き直す。(これは間違ってました。)
16:47 提出
うぅ。うぅ。
ローカルでN=1のケースを試してもちゃんとあっている。なんで0点？
そして時計を見ると、残りは10分を切っていた。今年も春合宿は無理か...。
ただ、まだ終わってないのでねばる。
この時、BFSのwhile文の箇所を見るのをやめてコードを上にスクロールしてみる。
scanf
いつも使っていない入力形式。とりあえずこれをcinにして提出してみるか。残り9分の時にできるのはこれくらい。
16:52:21 提出
！？
赤じゃない色が見えた。まだいけるぞ。急いで考察を見直す。
小課題1だけあっているということはN>=2の場合が違うのか。どこだろう。あ、さっき実装を簡潔にするために斜めの移動を消して横移動だけに直したところ、よく考えたら間違ってるじゃん。さっきどっかで提出したコードがあってるじゃん。
時計を見る。残りは6分。
震える手を震える手で押さえながらで2つ前の提出をダウンロード。scanfをcinに書き直す。
16:56:32 提出
残り3分…。
結果を見る暇もなく3つ前の提出をダウンロードしてscanfをcinにして保存して、、
Chromeを開く。
うおおおおおおおおおおおああああああああああ
3問目を始めて2時間半が経って、やっと、やっとAC！
4問目
3問目で満点取れるコード書いたっけ？と思いつつ、春合宿のボーダーが301点の可能性もあるから急いで4問目にいく。
小課題1の制約を見て何の考察もせずにとりあえずbit全探索の大枠を書いて、時計を見る。17時0分。
本戦競技終了。
振り返り
最終的な得点は100+100+100+0+0=300でした。解説によると、3問目の満点は8人しかいなかったらしい。わお。
それでなんとか終了ギリギリで300点までは持って行ったけど、結果が出るまでは春合宿行けたのかどうか分からずずっとそわそわしてた。 でも、結果を確認すると、ボーダーは268点。春合宿進出！！
ということで、終了3分28秒前に春合宿の切符をつかみました！うれしい！
本戦の反省点
- 実装するのに夢中になって、残り20分になるまで、CDEの部分点を取っていないことを忘れていたり、解法の計算量を考えるのを忘れていたこと。
- ローカルでサンプルはあってるのにCMSの方では不正解と出ていることに気付かなかったこと。
ios::sync_with_stdio(false); cin.tie(nullptr);
- 上のコードの意味を知らずに使っていたこと。
など、色々と精進不足だなと思いました。せっかく春合宿に行けることになったので、今回の反省を活かして約1ヶ月頑張ります。
ここまで読んでいただきありがとうございました！
