JOI 2022/2023 参加記
はじめに
第22回情報オリンピック(JOI 2022/2023)の春合宿に参加しました。
春合宿に参加したのは実は3回目なのですが、参加記などのまとまった文章を自分で発信するのは初めてです。
自分も高校3年生になり1年ほど競プロを離れてしまうことになると思うので、最後に高校生時代の貴重な経験を文章にして残したいという衝動に駆られてこの文章を書きました。拙い文章ですが見てくださったら幸いです。
2次予選
2次予選2日前から39度の高熱と倦怠感に襲われました(後にコロナだと判明)。前年のJOI春参加者は本選までの競技を事前に申請すれば免除することが出来るのですが、申請した記憶が全くなくかなり焦りました。問い合わせてみたところ申請していたので、2次予選の時はずっと寝ていました。昔の自分ナイス!
本選
自己紹介の動画を送ることを完全に忘れてしまい、NO DATAになってしまった...最後だし折角ならネタに振りたかった。オンサイトで開催される本選を経験したかった。
本選時のムーブをざっと書きます。
0:00 競技開始。A問題から解き始める。
実装が楽そうな解法がどれか悩んだが、脳死で実装。
0:12 AをAC。B問題へ移動。
問題文を読んですぐになんとなくの解法の方針が思い浮かぶ。少し細部を詰めるの に時間がかかったが、難なく。
0:31 BをAC。C問題へ移動。ここからが本番。
満点解法をしばらく考えていたが思いつかないので、部分点を取る方針へシフト。簡単な部分点もかなり実装に手こづる。
1:20 Cの小課題1,2を回収。 (合計27)
今書いたコードを工夫すれば小課題4,(5)が取れそうなので実装。
1:40 Cの小課題4を回収。(合計46)
この時点で競技時間の半分が過ぎてしまいとても焦る。Cに進捗が無さそうなのでD, Eに移動する。
D問題を読んでみるとパスグラフの時の解法が降ってきたので、実装すると意外とすんなり書けた。
2:04 Dの小課題1,2,3,5を回収。 (合計41)
次にEの自明解を実装するが若干バグる。
2:24 Eの小課題1を回収。 (合計3)
CよりDの方が得点を伸ばせそうなのでDに取り掛かる。N <= 5000の場合の実装を頑張る。
2:46 Dの小課題4を回収。 (合計51)
この時点で得点は300点。このままだと3完+α勢に負ける。
CDEどこの部分点を取りに行くか悩む。Eの小課題2がわかりそうなので、考察すると分かる。
3:08 Eの小課題2を回収。 (合計15)
得点は312点になる。実はCDがかなり簡単な問題で無限人に解かれてるということが起こらない限り、通りそうだと感じて少し落ち着く。
Dの小課題6の制約がつまり完全二分木ということに気づいて考察を進めると、解法が見える。これを取れば23点。これしかないと決心して実装を進める。
3:43 Dの小課題6を回収。(合計74)
達成感が体の中を駆け巡る。しかし、油断はできないのでCの残りの小課題を考える。15分で出来ることもなくそのまま競技終了
4:00 競技終了(100+100+46+74+15 = 335)
競技終了後のツイートや反応から察するに、CDはあまり解かれていなさそうだった。部分点はかなり頑張って集めていたので、2完部分点勢の中ではほぼトップだった。
ボーダーは268点だったのでかなり余裕を持って通過。嬉しい。
Day0
自分だけ制服を着忘れたり、飲食禁止の安田講堂で飲み物を飲んでしまったり、色々やらかしをしてしまった。
交流会ではかなりの方々とお話しすることが出来た。ツイッターを15人くらいと交換した。
K理事長先生となんと念願の2ショットを取ることが出来た。家宝にさせていただきます!♡♡♡
交流会ありがとうございました!!
— checkmate (@C_eckMa__) 2023年3月18日
写真はK理事長との2ショット pic.twitter.com/78y9fniqrP
Day1
0:00 競技開始。全ての問題を一通り見る。
festivalが難しそうだから、とりあえず他の2問を考える。ここでcurrenciesの平方分割解(満点)を思いついたので実装する。が、1時間くらいかけても全く書き終わらず途中で断念する。
1:10 passportへ移動。
少し考えると、今行ける国は必ず区間になってその状態数はO(N^2)しかないということに気付く。辺の数も工夫すればO(N^2)に落ちる。小課題2, 3, 4を一気に実装。
1:46 passportに提出。小課題2だけ通って3, 4はTLE。(16点)
解法的には正しいことをしているはずなので頑張れば通ると思い、重そうな部分を修正→提出を繰り返す。18分と6回の提出の後、AC。
2:04 passport 小課題3, 4を通す。(48点)
無事ACできて少し落ち着いたところで、コード書くだけの小課題1を実装。
2:09 passport 小課題1を通す。(54点)
54点を獲得したところでcurrenciesに帰る。このままcurrenciesの満点解を実装しても書ききれるか怪しいしそもそも計算量的に間に合わなそうだと思ったので、部分点を回収することに。まずは書くだけの小課題1から。
2:38 currencies 小課題1を通す。(10点)
競技序盤に小課題2, 3のちゃんとした解法は考えていたのでそれをそれぞれ実装することに。まずは実装簡単そうな小課題2から。
2:51 currencies 小課題2を通す。(38点)
次に小課題3を実装。かなり手こずってしまい、時間がかかる。
3:26 currencies 小課題3を提出するがWA。
3:46 currencies 小課題3を通す。(68点)
ここで、残り1時間の使い方に悩む。
まずfestivalの自明だけ回収して、passportの方が解けそうな感触を感じたので、passportに特攻することにする。
festivalの多項式時間解法を一瞬考えたが思いつかないので、N <= 8まで解くことに。適当に全探索コードを書き、1から8までの解をすべて求めた。(N = 8の時30秒くらいかかった)
4:07 festival 小課題1, 2を通す。(10点)
さっきの計画通りpassportに特攻。しかし方針すら定まらず1時間が経過。
5:00 競技終了。
結果は68 + 10 + 54 = 132点(12位)。currenciesを通した人数が11人もいたが、passportは1人にしか通されていなかった。結果的にはcurrenciesに特攻すべきだった。
festivalで実質満点の87点を2人が通していてヤバかった。
Day2
0:00 競技開始。全ての問題を一通り見る。
mizuyokanが解けない見た目をしていて、最初の小課題も時間がかかりそうで点数配分も少ないので、conveyorとcouncilに5時間を捧げることをここで決心する。
まず取っ掛かりやすいcouncilを見る。
少し考察するとO(4^M * M)解が生えてくる。小課題1, 3, 4は通せそう。小課題2, 5もワンチャン通りそう。
0:33 council 小課題1, 3, 4を通す。(33点)
小課題5のケースがすべてTLEしているので頑張っても通らなそう。小課題2は通りそうだったので、工夫を施す。
0:41 council 小課題2を通す。(41点)
ここでconveyorに移動する。
部分点を見てみると、なんと、満点回答に75点が与えられているのです。僕はこれを見て感動しました。ここからの4時間は75点に常に思いを馳せることとなります。
75点への想いが強すぎて、気付いたら1時間30分が経っていました。
しかし、通りそうな解法が思いつかず、とりあえず部分点を回収することに。
小課題1, 2と小課題3は全く異なるコードを書くので、小課題3からやることに。かなりバグり散らかして脳が破壊されかけた。
2:38 conveyor 小課題3を通す。(10点)
次に小課題1, 2を実装しますが、ここでもバグり散らかす。頭を完全に破壊されました。
3:11 conveyor 小課題1, 2を通す。(25点)
もうconveyorには懲り懲りだったのでcouncilに移動。
councilの小課題5(15点)を取ることを考える。定数倍が早くなるようにコードを大幅に書き直してみる。が、何度頑張っても通らなそう。悲しくなってしまう。
conveyorに戻り満点解を頑張って考察することに。再び1時間30分考察するが何の成果も得られず。悔しい限り。
5:00 競技終了。
結果は25 + 41 + 0 = 66点(20位)。結果を見てみると、conveyorは5人が通して、なんとcouncilは10人も通していた。ビックリ。立ち回りも結果もダメダメでかなり虚無になってしまった。
後で聞いてみたら、代表の某さんが1時間半でconveyorとcouncilを2完していたらしい。圧倒的な実力差を感じて、言葉を失ってしまった。
Day3
0:00 競技開始。全ての問題を一通り見る。
どの3問も不可能枠ではなさそう。とりあえず取っ掛かりやすそうなchorusから。
chorusの考察をすると、数分でO(N^3)の2次元DPが見える。しかも遷移がめちゃくちゃ単純で計算量の改善も容易にできそうだと思う。
とりあえずO(N^3)で小課題1, 2を回収しに行くことに。特に滞りなく実装完了。
0:30 chorusの小課題1, 2を通す。(40点)
O(N^2)に改善するだけで21点が取れて、あわよくばO(N)解も見えそうな雰囲気がしたので、考えてみる。DPのテーブルを出力させたりして美味しい性質(Monge性と呼ばれるらしい)を見つけるが、活かし方がさっぱり分からない。1時間かけたが収穫を得られず...
ここでcookiesを見てみると、小課題2が実装が簡単そうだったので実装することに。
1:52 cookies 小課題2を通す。(7点)
残りの小課題は時間がかかりそうだったので、chorusに戻って30分程度考え直すが、進展はなし。tourismの部分点を回収することに。
tourismの小課題3はminとmaxを管理するセグ木さえ書くだけだったので頑張って書く(ソラで書くのは本当に1年ぶりくらいだったのでめちゃくちゃ手こずる)。なんとか致命的なバグを埋め込まずに書ききることに成功。
2:41 tourism 小課題3を通す。(7点)
次に面倒な実装をするだけの小課題1を通すことに。
2:48 tourism 小課題1を通す。(12点)
さっき書いたセグ木を少し書き換えて小課題1のコードにぶち込めば、小課題2を取れることに気付く。
3:04 tourism 小課題2を提出するがWA。
2ケースだけREになっていた。どうせすぐ治るバグだと思いデバッグするが提出しても治る気配がない(15回ほど提出しました)。本当に何をしても治らなかった。
諦めてchorusの方を考えるが、案の定何も考えが生えてこない。
気付いたら競技は残り30分ちょいで、その時点での得点は59点。かなり焦る。残り時間でcookiesの自明っぽい小課題を考える。
小課題1はやるだけなのでやる。
4:36 cookies 小課題1を通す。(13点)
小課題3が解けそうなのでこれを頑張ることにする。適当に見積もると、箱のパターン数は高々1e6 - 1e7程度なので、判定問題をO(N)で出来ればよい。思いつく貪欲を数パターン試すが、全部WAが返ってくる。
ここである考えが降ってくる。この嘘貪欲たちを一つのコードにまとめれば流石に落とせるケースはなくなるはずでは?ということで一つにまとめて提出してみる...
4:46 cookies 小課題3を通す。(12点)
残り15分で何もできずに、
5:00 競技終了。
結果は40 + 25 + 12 = 77点(16位)。部分点も集めきれず、満足のいかない結果に終わってしまった。chorusのO(N^2)解はどうやら知らない知識枠だそうで、履修していなかったのが悔やまれた。
Day4
0:00 競技開始。全ての問題を一通り見る。
Day3まででBatch以外の問題が1問しか出ていないので、絶対に1問はcommunicationが出ると思っていた。実際、communication(last battle)が1問出た。
guardの問題文がめちゃくちゃ難解で全然本質を理解できなかった。
last battleの問題内容が面白かったので考えてみる。
まず、残りの49マスを全部赤にしたり青にすると流石に1文字に伝えられるので、communicationのコンパイルの実験もかねて、実装。
0:24 last battle (n = 1) を通す。(5点)
どんなX, Yの選ばれ方をしても高々〇マスしかビ太郎に塗られないようなグリッドの良い分割の仕方を考えると、斜めに8マスをとっていく発想にたどり着く。8文字伝えられそう。
0:38 last battle (n = 8) を通す。(18点)
いい発想がもうないので問題を理解できたtravelを考えることに。
Q = 1の時(小課題1, 2)はやるだけなのでとりあえず実装。
1:23 travel 小課題1, 2を通す。(15点)
ここで小課題3のX_(i + 1) - X_i <= 100から何かの回数がlog nに抑えられそうとエスパー。ちょっと考えてみると折り返しの回数がlog nで抑えられるのでは?と仮説を立てる。昨日書いたminとmaxを管理するセグ木をもう一回書いて、とりあえずO(Q log^2N)解を提出。
2:05 travel 満点を提出するがWA。
WAが数個あるがTLEは1個もないので、折り返しの回数がlog nで抑えられることが証明された。(Q. E. D)(カスの証明) しかしコードを煩雑に書いてしまい200行ほどになってしまったためデバッグに相当時間をかけることを覚悟する。バグが見つかり次第修正→提出をすることに。10分かけてようやくバグが見つかる。今年の春は1完すらも出来ずに終わるのかと悲嘆に暮れながら2回目の提出をすると...
2:19 travel 満点AC!!!!
1完してしまい、ガッツポーズをせずにはいられませんでした。この思いを叫ぼうとしましたが、競技規則により叫ぶことは出来なかった。
guardの読解をすると、小課題1, 2は配点が25点あるが簡単に解けそうでした。適当な貪欲解を提出すると、
2:37 guard 小課題1を通す。(2はWA)(12点)
ここで突然last battleの発想が降ってきたので、last battleに移行します。
X, Yを6ビットかけて送ることを考えると、斜めに5マス取ればビ太郎に邪魔されることなく1ビットの情報を送れるので、30マス使えばX, Yを教えることが出来る。あとは残りのマス1つにつき1ビット送るとN = 21~25程度を達成できる。
3:16 last battle (n = 23) を通す。(42点)
ここで、guardの小課題2の正しい貪欲も思いついたので実装します。
3:25 guard 小課題2を通す。(25点)
小課題1, 2と同じように木、一般グラフの時(小課題3, 4)の解法もわかりそうだったので考えます。が、なかなかわからず時間が経過します。競技時間は残り1時間だったので、last battleに時間をかけることを決意します。
last battleを少し考えるとN = 23からN = 28に伸びる小手先の工夫が思いつきます。
急いで実装します。
4:26 last battle (n = 28) を通す。(50点)
その後はlast battleの進捗が無さそうだったので、guradを考えたが正しい解法を思いつけなかった。
5:00 競技終了。
結果は50 + 25 + 100 = 175点(7位)。未証明だったり、余計なlogがついていたりしたが、何はともあれ、人生最後のJOIで1完することが出来て嬉しかった。
結果
Day1: 68 + 10 + 54 = 132 12位
Day2: 25 + 41 + 0 = 66 20位
Day3: 40 + 25 + 12 = 77 16位
Day4: 50 + 25 + 100 = 175 7位
総合: 450点 11位
交流してくださった皆さん、チューターの皆さん、ありがとうございました!!!本当に貴重で楽しい経験をさせてもらいました。