JOI2022/2023 春合宿参加記
はじめに
3/18~3/22にあったJOI2022/2023の春合宿に参加しました。貴重な体験だったので参加記を書きました。拙い文章ですが読んで頂けたら幸いです。
本選
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に携わったすべての方々、大変ありがとうございました！すごく楽しい経験をさせてもらいました！
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ヶ月頑張ります。
ここまで読んでいただきありがとうございました！
