JOI 2022/2023 参加記 (春合宿編)
※この記事は JOI 2022/2023 の春合宿の問題のネタバレを含みます。
↑本選までの参加記です。
どちらも拙い文章ですが、見てくださると幸いです。
Day -1 (準備編)
トヨタコン予選を突破してしまったので JOI の表彰式とどっちに行くかでだいぶ迷ったが、 1 回は東大に行きたかったので結局表彰式に行くことにした 。
数日前から腰が痛くなったり血圧が高くなったりと体の調子が悪かった。おまけに本番が近づくにつれてどんどん生活リズムが悪くなって、時々寝付けない日もあった。
Day 0 (出発・表彰式)
5:40 に起床。予定よりちょっと遅めに起きてしまったので急いで準備して出発する。天気は微妙。キャリーケースがちょっと古いのとキャスターが 2 つしかないものだったのでかなりうるさかった。
新大阪に到着して新幹線に乗り込むが、慌てすぎて自由席のチケットを取ったのに指定席の車両に乗ってしまった。 (すぐに車掌さんに注意されて別の車両に移った)
新幹線と言えばこれでしょ、ということで買ったはいいものの、食べてたらお腹を壊してしまった。
途中で 1 つ上の先輩と会った (トヨタコンに行く所だった)。その人も JOI の春合宿に行ったことがある人だったので色々話を聞きたかったが、席が遠かったのでちょっとだけ話して別れた。
東京に着いたら人が関西の数倍の人でごった返していてびっくりした。とりあえず人ごみを進んで丸の内線に乗り込むが、ここで逆方向に行ってしまう。すぐに気づいて引き返した。
なんやかんやあったが集合の 45 分前に東大に着いた。
表彰式
自分は優秀賞だけだったのでほとんど登壇することは無かったが、同校がめっちゃ登壇しててすげぇ～ってなってた。メダリストの副賞が Macbook Air とかで豪華すぎる…。
交流会
昼ご飯はおにぎりやサンドイッチなどの軽食だった。(トヨタコンの方は叙々苑の弁当だったらしい。豪華すぎる…)
最初に Twitter で昔からよく交流していた人と初めてエンカして、そこから 2 人でいろんな人に Twitter をフォローしてもらったりした。下の世代で知らない人が多くて、自分はもう老害になったんだなぁ…。White200 でバズっていた TsumoiYorozu さんや Nafmo さんともエンカ出来て良かった。
もうちょっとエンカしたかったが、プラクティスが控えてたので東大を後にした。
プラクティス
会場に着いたらチューターの皆さんが手配してくれた。時間があまりなかったが、とりあえず問題の入った封筒に手を付け始めた。
足し算 (Addition)
問題概要
クエリが Q 個与えられます。それぞれのクエリで A, B が与えられるので A + B を出力してください。
1 <= Q <= 1000000
|A|, |B| <= 10^18
普通に足し算するだけと思って実装したら TLE した。嘘だろ？どうやら入出力はだいぶ遅いらしい。ios::sync_with_stdio(false) や cin.tie(nullptr) で入出力高速化をしないといけなかった。
航空路線 (Airlines)
問題概要
N 頂点の有向グラフが与えられます。任意の 2 頂点間の最短距離の総和を求めてください。
1 <= N <= 1000
N <= 1000 の O(N^3) は間に合わないだろって後回しにしていたがどうやらこれは間に合うらしい。ジャッジどうなってるんだ…
碁石並べ 2 (Stone Arranging 2)
本戦の 1 問目と同じなので省略。
ラーメンの食べ比べ (Ramen)
これも過去問と同じだったが、解き方を忘れて 50 点しか取れなかった。
伝達 (Transmission)
問題概要
Anna は Bruno に整数 N を伝えたいです。 01 文字列でなるべく文字数が少なくなるように Anna は Bruno に文字列を送り、 Bruno は N を特定してください。 (満点は長さ 16)
1 <= N <= 100000
これは新規の問題 (インタラクティブの練習として置かれていた) 。文字列の長さ自体を情報として持つ、発想に無かった…
サンタクロース (Santa Claus)
問題概要
座標平面上に N 個の点があり、 i 個目の点の座標は (x_i, y_i) です。頂点 1 から出発して全ての頂点を通って頂点 1 に帰ってくるときに通ったマンハッタン距離の総和をなるべく小さくしてください。 (テストケースは N = 10 が 1 個、 N = 50 が 3 個)
これも新規の Output Only。あんまり時間が無かったので詰めなかったが、 2-opt で 99 点まで取れるらしい。
この問題があったということは本番にも Output Only があると思って身構えてみたが、蓋を開けると結局 1 問も出なかった。
プラクティスやっただけでちょっと本番が心配になった…
家が遠かったので、夜は運営が手配してくれたホテルに泊まった。
Day 1
モーニングコールのおかげで 7 時に起きることができた。
会場で飲料とお菓子が置かれてたのでとりあえず水と GABA チョコレートとゼリーを取って本番に臨んだ。
2 つの通貨 (Two Currencies)
小課題 1 は愚直に実装。小課題 2 は C が固定なので LCA を使うと解ける。
小課題 3 に取り組んだが、嘘考察に走ってしまい、結構時間を溶かして結局解けなかった。解説を聞いたが、並列二分探索は聞いたことが無かった…
JOI 国のお祭り事情 2 (Festivals in JOI Kingdom 2)
とりあえず小課題 1 を通したが、小課題 2 で a, b の通り数を見誤って間に合わないな…と思って飛ばしてしまった。
解説の最後の方で NTT とか出てきて「？？？」になってた。おそらく Day 1 の最難関枠だと思う。
パスポート (Passport)
小課題 1 はなるべく大きな R を取っていくとできる。小課題 2 は区間 DP で解けた。ここから小課題 3 を考えたが、結局何もわからず競技が終了してしまった。
後で解説を聞くと、これはもうちょっと小課題取れる問題だったな～ってなってしまった。
結果は 38 + 5 + 22 の 65 点 (19 位 / 28 人)。中 2 の後輩にも負けててかなりまずい。
PCT が単独トップになっててすげぇ～ってなった。
ホテルに戻ってから Day 1 の解説を見返していた。ABC は出なかったけど G に 2 つの通貨で使う HLD を使った問題が出たらしい。
Day 2
朝は大体 Day 1 と同じだったので省略。
ベルトコンベア (Belt Conveyor)
Communication に苦手意識を持っていたので結構後の方に手を付け始めた。結局小課題 2 で実装にてこずってしまってそれ以降の考察が進まなかった。最後の小課題が 75 点 (JOIG だと 60 点) でかなり大きかったのでそこで上位陣が結構差が付いていた。
2 個飛ばしで製品を置く、賢い… ちなみにパスグラフは 1 個飛ばしでも解けるらしい。
議会 (Council)
小課題 2 まではそこまで難しくないので実装する。見た目簡単な感じで解けるかなと思って結構考えたけど、小課題 4 までしか通らなかった。
解説を聞くと、「過半数ギリギリの所だけみる」という考察までは合っていたが、 bit で持ってなかったのもあって取れるはずの小課題 5 が取れてなかったことが分かった。うーん
水ようかん 2 (Mizuyokan2)
Day 2 の最難関枠。とりあえず小課題 1 だけ解いて、小課題 2 は区間 DP をセグメント木を使って高速化しようとしたが結局 TLE してダメだった。結局最高点が 28 点だったので別の問題の小課題を解いた方が良かったかなと終わってから思った。解説の「山は和歌山である」が面白かった。
結果は 15 + 41 +6 の 62 点。合計で 20 位 / 28 人。かなり爆死した感じがある。
ホテルに戻って、後輩が VALORANT やってるのを見ながら同校の人といろいろな話をしていた。
夜にオープンコンテストの順位表を眺めてたけど、中国の IOI 勢が水ようかん 2 で 60 点取ってて結構怖かった。
Day 3
ホテル生活にも慣れてモーニングコールが鳴る直前に起きることができた。
ビーバーの合唱 (Chorus)
小課題 1 は全探索だが、列が条件を満たすかを判定するパートを書くのに結構手間取ってしまった。小課題 2 を考えたが、 DP で持つべき情報がどうしても多くて結局思いつかなかった。
グリッド上の経路に置き換えるという発想が無かったなぁ… あと Monge 性のあたりは全然やったことが無かったのであんまり分からなかった。
クッキー (Cookies)
小課題 1, 2 は頑張るとできる。小課題 3 の実装で手間取ったが、どうやら箱の容量にこだわらずにまず箱に入れるクッキーの個数を全探索すれば実装が簡単になったらしい。
小課題 4 以降は分からなかった。解説の必要条件 (十分条件) が賢かった。
旅行 (Tourism)
小課題 2 で配列を要素に持つセグ木を使って解いた (本解ではなかった)。
小課題 3 は求値が区間 min と区間 max であるようなセグ木を持つとできる。
小課題 4 を考察したが、「クエリ頂点の LCA の部分木から葉の部分木を引けばいい」という嘘に走ってしまい、 LCA などの実装で時間を溶かしてしまった。
木上の最小シュタイナー木を知らなかったので結構厳しかったかもしれない。
結果は 16 + 25 + 17 の 58 点。この時点で 21 位 / 29 人。今日は知識不足が顕著に出た感じだった。少しずつ順位が下がっていってて良くない。
Day 4
最後の日だったのでチェックアウトして荷物をデータセンターまで持っていった。結構しんどい。
最後の戦い (The Last Battle)
思い付いた解法が全部ビ太郎の塗り方によっては成立しなくなるものだったのでとりあえず後回しにした。
この問題に戻ってきて、「4 × 4 の正方形 4 つに分けたら絶対にビ太郎が塗れいないところが出てくるな」ということに気付いて、とりあえず N = 8 の解法を書いた。よく考えたら N = 16 まで行けたかもしれない。
満点まで行くと焼きなましを書かないといけないらしい。大変すぎる。
警備員 (Security Guard)
最初の言い換えが全然できなくて結局 0 点だった。難しい
ビ太郎の旅 (Bitaro's travel)
小課題 2 までは解けた。小課題 3 も「100 回移動したら後はほとんど左右どちらかにしか行かない」ということに気が付いて実装したが、なぜか通らなかった。結局 3 時間かけても原因が分からず 15 点しか取れなかった…
結果は 18 + 0 + 15 の 33 点。最後に思いっきりやらかしてしまった。
Day 4 (表彰式・その後)
Day 1: 38 + 5 + 22 = 65
Day 2: 15 + 41 +6 = 62
Day 3: 16 + 25 + 17 = 58
Day 4: 18 + 0 + 15 = 33
最終結果は合計 218 点で 23 位 / 29 人。ところどころ取れるはずの部分点を取りこぼしてしまってしまい結局かなり順位が低くなってしまった。
同校の人が 3 人も IOI に行ってて凄いなぁ… 日本から応援しています。
総括
今年で最後だったのに、あまり精進できずに春合宿に行ってしまって良くない結果になってしまったのでどうしても後悔が残ってしまったけど、大学に行ってから ICPC とかの大会があるらしいのでそこでリベンジができたらいいなぁ… (まずは PCK かも)
でも、コロナでなかなかオンサイトの機会が無かったので (ちょっと前までは JOI 本選もオンサイトだった) 、学外の競プロ er とたくさん交流ができたのは大きな収穫だったと思っている。同校で同学年の競プロ er は少ないのでなかなか競プロについて話すことが無い…
あと 3, 4 年ぶりに東京に行けたのも大きかった。
最後に、このような場を設けてくださった JCIOI の皆様、チューターの皆様、本当にありがとうございます！！！