2025年1月26日,2月2日に開催されたJOI2024/2025 本選に参加しました。結果は100-100-100-46-25 合計371点で総合5,6位くらい(真偽不明)でした。
二次予選
今年はISUCONに参加していたため、二次予選に参加しませんでした。シード権を使用して本選進出です。前回大会の春季トレーニング参加記はこちら:
本選Day1
- 講義が非常に面白くて普通に論文を読んでしまった。
- 双子に代わって他チューターらがチューター企画をやっていた。今年はGartic Phoneみたいな感じで、お絵描きで競プロの問題文を伝えてコンテストフェーズで絵から問題を解くというような競技だった。CMSを使うのは新規性があって面白かった。各チーム2グループに分かれたが、自分のグループは問題を解くパートがあまりうまくいかず、悔しかった。なにはともあれ、楽しく交流できたので良かった。来年以降もチューター企画が開催されるのだろうか🤔
本選Day2
競技当日
時系列でコンテストでのムーブを思い出します。
13:00 競技開始 practiceの時コンパイルコマンドがなんだったか確認し忘れたのでここで確認してデバッグライブラリをこれに合わせる
13:06 だけ無視して累積maxを取って尺取り法をしろと書いてあるのでやる A AC 100点 6:24
13:11 (必要な強さ,増加する強さ)の組がモノイドになって、マージも簡単にできるのでセグ木でできる B AC 100点 11:34
13:11~13:45 Cを読み、 と
は見た瞬間わかる。
(
以上の会社を使える時、
以下の会社のみですべての頂点を行けるような最小の
) を各
について求められればあとは(座標圧縮した上で)
とかを持つセグ木を使ってやればいい。
を求めるパートがどうしても
かかってしまってそこから進展せず30分くらい経ってしまったのでとりあえず実装することにする
14:00 実装して出してみたが0点でちょっと焦る C 0点
14:16 直ったと思って出すが7点 どうやら クエリを答える部分で の場合しかできてないようだ。そこを重点的に見てバグを探した C 7点
14:22 場合分けが足りておらず実装しなおす C 48点
14:28 48点を提出した直後、このグラフがDAGであることを思い出し、すべての頂点についてその頂点に入る辺がありさえすればかならず頂点 1から到達できることに気付いて を求めるパートだけ書き換える。10行くらいの書き換えで済んだ。かなりのアハ体験だった C 100点 88:19
14:46 Dを読んですぐに各長さは高々一つなのでbitで集合を持てばいいことがわかって 46点は取れそうだしもしかしたら72点も行けそうだし実装は楽そうだったので実装する。D 46点 101:08
この時くらいに春は大丈夫そうだなと一安心する。あとはメダル目指してがんばるだけや！
72点取れたらかなりデカそうなのでbitset高速化や定数倍改善をしようと色々試す。しかし、結局何も46点から改善せず 72点取るまであと2ケースくらいにはなったがさすがに厳しかった
ここまでで15:15くらい
一旦Eを読んで取れる点数を取ろうということでDからEにシフトする
Eを読むと愚直で12点取れそうだとわかったとりあえずこれと直線の木だけで50点取れるのでこれはデカいと思い考える。程無くして13点の小課題3はAとBの境目に注目してどんどんそこに到達してくるみたいな感じで考えるとうまくいった。これが実はそのまま小課題4に応用できるものだったが頭が動いておらず...
15:57 そのまま30分くらいEで小課題4すら解けなかったので 小課題1,2を実装することにする E 12点 177:34
16:12 小課題4も解けないか模索したが駄目そうだったので小課題3だけ実装する E (累計) 25点 192:04
このあとはEの小課題4のテキトーな嘘(2ケースしか落ちなかった)やDの定数倍改善/テキトーな嘘を投げたが結局うんともすんとも行かず競技終了
終了後みんなの点数開示ですぐさま3人くらいに負けてることがわかりメダルなし！
Dのhirayuuの嘘は考えなくもなかったので悔しいなあと思った。実際翌日(2/3)起きて実装してみたら100点取れました。マジかよ。
Eはこの記事を書く直前に本質を頭で理解できました。かなしいね。解説の図がHarvestみがあってHarvestだなあとか言っていたが本当にHarvestだなあ。
正直悔いが残る結果でした。Cで少しモタついたのと、D,Eでろくに点数で取れなかったのはかなり悔しい。Eは本質にほぼ近かったんだけどいい感じに整理できずノリで50点獲得まで行けなかった。(Dが頭でちらついて思考が整理できなかったと思う) 自分の特徴として複数の問題を同時に考えるのは苦手なんだろうか
今年はIOI日本代表になる最後のチャンスなのでボリビアへの切符を獲得するために残り40日程度頑張ろうと思います。
