JOI2022/2023 春合宿参加記

はじめに

3/18~3/22にあったJOI2022/2023の春合宿に参加しました。貴重な体験だったので参加記を書きました。拙い文章ですが読んで頂けたら幸いです。

本選

tomo222.hatenablog.com

100-100-0-0-0の状態から終了3分28秒前にC問題を通して、100-100-100-0-0の合計300点でなんとか春合宿の切符をつかんだ。うれしかった。人生で春合宿に行けることはないと思ってたので素直にびっくり。それにしても部分点ってどうやって取るんだ…

同校から6人も春合宿に行けていて、KCLCの成長を感じた。

春合宿まで

急遽春合宿に行けることになって準備をする必要があったけど、学校の課題とか期末試験があって3月上旬まではほぼ全く精進ができなかった。

春合宿の1週間くらい前になってから、ライブラリを持っているアルゴリズムを空で書く練習を始めた。ここずっとライブラリをコピペする人生を送っていて空でかけるアルゴリズムが無に等しかったので大変だった。ただ新たな発見とかもあって、いい勉強になったと思う。

交流会

けんちょんさんとお話しした。自分がKCLCの部長としてやっている活動を話したら、頑張ってるじゃん!ってすごい喜んでくれた。うれしかった。

他のみんなとも話したかったけど話すタイミングと内容がなくてなかなか話しかけられなかった。最後の方になってTwitter を見せながら話しかければなんとかなるのかなぁと思って、Twitter のアカウントを作った(@to_omoT222です)。ただ時間がきてあんまり交流できなかった。次はもっと交流します。

競技1日目

現地での競技で緊張した。ぬいぐるみのプーさんを会場に持っていった。かわいい。

競技開始。最初はとりあえず3問すべてに目を通す。

currenciesは、小課題2はEularTourで、小課題3はMoで解けそう?みたいなことを考えた。まず小課題1の10点を取って、次に書き足すのが楽そうなMoを書くも小課題3がTLE。1つの辺に関所が何個もあるから単純にMoは嘘だった。同様の理由で小課題2も通らないと勘違いして飛ばしてしまう。ここまで2時間で10点。

festival2は何も分からなかった。小課題2までは解けそうだけどいったん飛ばす。

passport。区間DPでO(N3)で小課題2を通す。その後、dp[0][N]=0にして逆からdp[K][K+1]を求めていけばいいんだなっていう考察まではいったけど、O(N2)に改善できず22点のまま。

最後にfestival2のバグったコードと格闘するも結局1点も取れず競技終了。

結果

10+0+22=32点。24位。

currenciesの22点と、festival2の10点は取れなかったのは悔しかった。部分点の取り方が下手だなぁと。そしてそこを取れても70点くらいしか取れない自分の精進不足を思い知った。

競技2日目

緊張していた。

1問目のConveyorを見た瞬間に重心分解が頭をよぎる。昨日の失態もあり小課題4が75点なのを見てこれは解かなきゃと焦ってしまったのと直近で重心分解を空で書いてたのがあってすぐに実装に走る。

考察+実装+バグ取りで3時間くらいかけた後に自分の今の解法では解けないことに気付き、憂鬱になりながら別の問題を見に行く。ここまで0点。

councilに手を付ける。O(N×2M)はすぐに分かるがそこからの改善できず、小課題2までの16点を取った。N人いるけど同じタイプの人が高々2M人しかいないことに気づけなかったのは反省。

mizuyoukan2は、愚直なDPを思いつくも実装のコストと取れる点数を考えてConveyorをねばることを選ぶ。最後まで頑張るも結局1点も取れず終了。

結果

0-16-0で16点。合計48点で26位。

Conveyorで沼りすぎたのが完全に失敗だった。2日とも部分点がうまく取れずにさすがに反省。

次はあせらずに自分の実力でとれる部分点はすべて取ろうと決めた。

競技3日目

とりあえず3問に目を通した。

chorusは、O(N2)か!と思ったけど遷移がN回だったからO(N3)のDPで40点を取った。O(N2)に落とそうと遷移を減らせるか考えたが分からず次に行く。

cookiesはdp[i][x]=i種類目の箱まで見てクッキーの総和がxになる時の箱の数の最小値を入れて復元すればいいのでは?という嘘解法を思いつく。実装に入り、まず小課題1を書いて6点を取った。その後嘘解法を実装し終えてサンプル4の答えが合わず、嘘であることに気づく。この時点で2時間くらいが経っていて、解法をお蔵入りにするのはつらかったが、昨日の反省を活かして粘着するのを切り上げた。とりあえず小課題2の7点を取り、次に行く。

その後tourismで17点。セグ木は空で書く練習をしていたのでちゃんと書けた。残り30分くらい余ったのでcookiesの小課題3を書いて12点。

tourismの小課題4がHLDとか使って頑張れば行けるのかなと思いつつ時間切れで競技終了。

結果

40+25+17=82点。合計130点で25位。

前2日に比べて、ちゃんと人に言える程度の点数が取れてホッとした。コンテスト中の得点の取り方は確実に修正で来てるなと感じた。それにしてもこのセットで100点以上取れてる人たち本当にすごいなぁ。

競技4日目

今日は100点超えたい!まず3問全部を考察する。

battleは、端の2行と2列を使って、Brunoに目視でビ太郎の行と列を当ててもらうとL=25まで取れて、ビ太郎の行も列も端じゃないような時は右端1列を潰さなくても頑張ればできるのでそれでL=30までは取れそう。 ただ実装が重たいので後回し。

guardは、問題がとてもややこしかったので、とりあえず小課題のパスグラフを考える。頑張るといけそう。

travelは、今までに行った観光地が区間になるので小課題2まではいける。

ここまでの考察で1時間くらいが経った。最初にtravelを実装して15点。 次にguardのパスグラフを頑張って通す。その拡張で木の場合を考えて実装し、37点。ここまでで3時間くらいだった。

battleのL=30で53点が取れると思い、重実装をとても丁寧に書く。するとほとんどバグらずに通る。その後一番点数が取れてなかったtravelに戻り考察を進める。

すると観光地の区間を超えるジャンプがある時区間の長さは2倍ずつになると気づいたが、それで小課題3に飛びつき30点を取る。ジャンプの回数が高々logN回であるから普通に満点も取れるのか...。

結果

53+37+45=135点。合計265点でなんとか20位に。

終わって

32+16+82+135=265点

最初の2日間はただただ憂鬱だったけど最後はちゃんと点数が取れて楽しかった。最終日に合計が100点を超えたのは合宿内での自分の成長を感じた。

一方で、自分の点数と他の参加者の点数との差を考えると、自分の考察力や知識量、タイピング速度など、あらゆる面において実力が不足していることを痛感した。これからが本当の精進だなぁと思った。そして僕の2倍も3倍もの点数を取っている方々は本当に尊敬です。

幸い、僕は来年もJOIに出れるので、1年かけてしっかりと精進を重ねて、悔いのない形で終われるよう頑張ります。

最後に、今回のJOIに携わったすべての方々、大変ありがとうございました!すごく楽しい経験をさせてもらいました!