JOI 参加記 (～本選編)
覚えているうちに急いで書いたので誤字脱字があるかもしれません。
一次予選
去年本選に出てたので免除されてた。一応 3 回目だけ出た。
二次予選
とりあえず A と B をすぐに解く。 C もちょっと実装が面倒だが 20 分弱で解いた。
D を見る。
まず dp[i][j] = i 番目までの取る荷物が確定していて、移動した総距離が j の時の価値の総和の最大値 とすると、区間 [i, j] 内での価値の上位 W 個の総和を O(N^3) で前計算すれば O(N^2D) になって小課題 4, 5 が通る。
次に、 W = 1 のときは上と同じ DP をするが、遷移を簡略化できて O(ND) になるので小課題 1 が通る。ここまでで 67 点。
ここで小課題 2 に取り掛かるが、一向に WA が出る。ちょっと焦って E の小課題 1 を取った。
D に戻って小課題 2 を解くが結局最後まで解けないで終わってしまった。
結局ボーダーは 207 点だったので余裕で通った。やっぱり本選の枠が 2 倍になるとボーダーが 100 点ぐらい違ってくるなぁ (今まで通りだったらボーダーが 300 あたりになりそう)。
本選 Day1
開会式で参加者の自己紹介動画が流れた。僕は謎解きを作ったけど、他の人は色々なネタをやっていて面白かった。
開会式の後は例年通りプラクティスがあった。もう 3 年目なので 15 分ぐらいで全完した。今年は質問で大喜利をやるのは少なかったような気がする (去年はやりたい放題だった)
プラクティス後、チューター企画が行われた。 4 人 1 チームでヒューリスティクスの問題を解くものだったけど、僕はヒューリスティクスにそこまで明るくなかったので、チームメイトにでいい感じの解を人力作ってもらって山登り法でその解を改善した。結局 8 位 / 23 チーム だったけど結構いい立ち回りができたと思う。
本選 Day2 前日
ABC に出た。黄 perf が出て調子が良かった。
ABC の後に JOI 本選サーバーのボイスチャットで tatyam さんが ABC のバーチャルコンテストに参加しながら雑談しているのを聞いていた。大学の話など色々なことが聞けて良かった。
本選 Day2 (本番)
※ AC した時間は記録してなかったので書いてません → 提出時間が見れたので追記します (書いてある時間は最初に満点 or 部分点を取ったときのものです)
A - 碁石ならべ 2 (Stone Arranging 2) (20:51)
すぐに満点解法は思いつかなかったのでとりあえず 2 問目と平行して部分点解法を考えた。
よく考えたら一番左端と同じ色の碁石はそれより右にある同じ色の碁石とペアになって、その中にあるものは無視できるし、その碁石のすぐ左の碁石でも同じことが言えるが分かったので、実装をする。 AC。
B - 宣伝 2 (Advertisement 2) (115:4)
グラフを描くとマトリョーシカ人形 (難易度 9) みたいな問題に帰着できるので実装できると踏んだ。2 問目を実装する。マトリョーシカ人形と同じ要領で実装するも WA。ここでかなり焦る。とりあえず 3 問目の考察も行いながらミスの特定を急いだ。結局マトリョーシカ人形とは違う方針で解いて AC した。
C - 迷路 (Maze) (135:04)
小課題 1 はよくある 01BFS 、小課題 2 はhttps://atcoder.jp/contests/abc213/tasks/abc213_eと同じ解法で解けるので実装する。ここで 27 点。小課題 3 以降を考えようとしたが全然思いつかなかったので、4 問目に進んだ。
D - キャットエクササイズ (Cat Exercise) (131:34)
小課題 1 ~ 3 はパスグラフになっていて、区間 DP で解けることがすぐに分かった。
ここからが問題だが、「操作を逆順に見て、高さが低い順から辺を繋げていけばいいのでは？」と思いつく。そうすると連結成分内でどのキャットタワーが一番高いかを調べればよくて、これは高速化をする前の UnionFind 木を用いると分かる。ここまで急に閃いたのですぐに実装した。
木の 2 頂点間の距離は、小課題 4 なら全探索で O(N^2)、小課題 5 は特殊なパスグラフなので O(1) で求められる。小課題 6 を解こうとしたところで、「これ LCA 使えば O(log N) で 2 頂点間の距離を求められるのでは？」とまた思いついた。これのおかげで小課題 6 をすっ飛ばして満点を取ることができた。
E - 現代的な機械 (Modern Machine) (78:28)
4 問を行けるところまで解いて残った時間でとりあえず小課題 1 を取った。小課題 2 以降に手を付けようとしたが、実装がややこしそうになったので C の部分点に着手した。
結局 C の部分点は 27 点から伸びず、結果は 100 + 100 + 27 + 100 + 3 で合計 330 点だった。
終わった後の人々の感想を聞いていると、 3 問目の部分点取っている人が多くて春合宿は厳しいかなと思ってたけど、点数報告を見ると意外といけそう？となった。
終わった後に解説を聞いた。 3 問目の小課題 3 の解法が天才で、自分の解法の引き出しにはないものだった。あと 5 問目が非自明な考察を何個かやらないといけなくて大変そうだった。このセットをオープンコンテストで 2 時間で全完した中国の高校生は本当にどうなってるんだ…
解説の後に Gartic Phone でちょっとだけ遊んでた。自分の絵心のなさと絵を理解する力のなさを実感した。
ここまでの感想
春合宿に行く決め手になったのはやっぱり D で満点を取ることができたことだと思う。難易度投票によると D は難易度 9 相当らしいので、素直に嬉しい。
本選はオンラインでも楽しかったけど、やっぱりオンサイトだともっと楽しいんだろうな…。コロナが落ち着いたらぜひオンサイト復活してほしい (僕はもう出られないけど)。
春合宿は僕よりも強い人がたくさんいて代表になるのはかなり厳しいけど、最後の年なので楽しんでやりたい。
春合宿編に進む…