前座
二次予選
最終問題だけ見れば易化だが全体的に難しかったと思う。ボーダーは思っていたより高くて、確か 225 くらいを予想していたが 240 もあった。そして体感難易度以上に多くの人が満点を取っていたので危機感を抱いた。この最終問題は 12 人に解かれる問題ではないと思う。。。
一日目
自己紹介動画は 5 秒程度という制限があった。ほとんど何もできないと思う。二次予選の得点 / 50 秒自己紹介できるというのはどうだろうか😀 結局いつものかえるのぬいぐるみを登場させた。秀逸な 5 秒芸がたくさんあってよかった。去年やったずんだもんが今年は二人いたので、使い回さなくてよかったと安堵した。
交流会は、暗号化された問題文を解読して問題を解くというものだった。うちのチームは弊校 3 人と Yukkku さんだったので、あまり新しい人と交流をした感じはしなかったが、内容はとても面白かった。準備ありがとうございます！
チームメイトの暗号解読が強かった上にプログラミングパートは軽かったので、あまり貢献できなかった。直前にチームメイトが最終問題を解読していてお見事だった。なんと 3 人チームが優勝するという結末でびっくりした。
欲を言うと昔みたいな宿泊形式で競技してみたいと思う。昔は JOI も SuperCon も宿泊のオンサイトだったけれど、今は東京住みだと IOI まで行かないとそういうものがないので、その点では上の人が羨ましい。
二日目
昔と違って、午後開始という都合上寝坊のしようがない。
開始直前にコードテストの調子が悪くなっていたようなので、かわいそうだと思った。内心でガッツポーズをした。
戦略
落ちはしないだろう、本当にまずかったらそのとき考えようということで、賞の可能性の最大化の気持ちでやった。D までの (ほぼ) 満点が最低条件だということで、結局順番に解く以上の戦略ではなかった。E の部分点は先に考察し切ってから一気に取るつもりだった。
A 問題
例年より簡単だったと思う。見たら方針がわかったので、少し心配になって正当性を確認しながら実装した。結局 AC だった。
経過時間 : 0:04:17
B 問題
こちらも例年より簡単だと感じた。とりあえず両側から最短経路を求めて、そこからどうしようかと考えたが特に突飛な考察もなく解けた。強いて言えば N(N-1)/2 の計算をうっかり int でやりかけたのでヒヤッとした。実際これで大変なことになった人がいたらしい。
経過時間 : 0:14:22
C 問題
いきなり難しくなった。最初に思ったこととしては、
- $T < 500000$ という制約が怪しい。判定問題を解くというのも珍しい。
- 外側のボールから優先して取るとよさそう。
折返しを 3 回しかしないという嘘の貪欲法を思いついたが、流石に違うと思って反例を考えた。すると、ゴール付近にたくさんボールが集まっている場合などが怪しいことがわかった。$O(N^{2})$ の区間 DP が正当だとわかったので、最後の小課題では結局二乗を落とさないといけないんだよなあと思いつつ実装をした。
実装しながら、座標圧縮したあとも $L$ が十分に大きかったらまずそうだということがわかり、本質的には解法がわかった。
DP をしたあとの結果の集計の高速化をサボったものを提出したが、 62 点しか入らなかった。経過時間 : 1:09:17
本質的な改善をした。最後の小課題で WA が出て 84 点。直して満点。経過時間 : 1:27:05
正直かなり難しくて時間もかかったので焦った。
D 問題
こんな問題がクエリで高速に解けるわけないだろ！というのが初見の感想。$Q \leq 10$ に 50 点の配点がつけられているのでそれを考えた。
マッチングくらいしか考察の道具がなかったので Hall の定理を適用したら、本質的な考察が生まれた。とりあえず実装をして 50 点。経過時間 : 1:45:20
この条件を素直に扱っても難しいと思ったので、いわゆる逆の視点から見るみたいな ? 考察をしたら、これがうまくいきそうだった。log 1 つなのでそのまま満点が取れた。segtree, 平面走査、全て自力実装をしていなくて、春合宿ならあと 20 分はかかっていた。経過時間 : 2:17:04
私は C よりこちらが楽だった。人によるらしい。去年もそうだったのでそういうジンクスを疑う。
E 問題
こんな問題がクエリで高速に解けるわけないだろ！枠の二つ目だった。この時点でとりあえず春合宿落ちはしなさそうだったので、メンタル的にはのびのびと考えられた。
ネチネチ考えていくと、 $T_k = 2, C_i = 1$ かつ愚直が許される前半の 16 点は案外簡単なことがわかった。$T_k = 2$ を取り除いた小課題があったので、そこまで一気に取りたいと思った。解説に書かれている条件はとてもきれいだが、そこまできれいではない条件しか思い浮かばず、ひたすら連結成分の情報を保持するコードを書いた。31 点取れた。経過時間 : 3:06:59
$C_i \neq 1$ は検討がつかなかったが、 431 点は割といそうなのでもう少し点は取りたいと思った。残り 40 分くらいの段階で覚悟を決めて、 $C_i=1$ までの小課題 4, 5 を取る 48 点を目標にした。どちらもダブリングで解けそうなので実装を始めたが、先程の考察が不完全だったので持つべき情報がひどいことになってしまった。
残り 30 分段階くらいで、とりあえず一般の実装を諦めて $T_k=2$ の方、小課題 4 を取ろうということにした。こちらは通って 42 点。経過時間 : 3:53:24
結局一般の場合の実装は終わらなかった。最終結果は 100-100-100-100-42 の 442 点。
コンテスト後
D までどれくらいの人が解いてくるのか分からなかったので不安だったが、結局ここまで満点を取った人はほとんど居なかった。多くの人が誤読と制約の読み落としに引っかかっていたので、そういう幸運も大きいと思う。
公式 discord サーバの得点自己申告では全員に勝っていたのでこれはあるか ? と思っていたが、 Forested 様がなんの言及もしないので嫌な予感がしていた。E の解説スライドの得点分布に 48 点がいたので、全てを察した。Forested orz.
Open Contest では rainboy が満点を取っていてびっくりした。解くの速すぎる。errorgorn が 448 だったのでやはりそこからは茨の道で、 rainboy がおかしいだけだと信じたい。
結局銀賞だった。JOI の本選でメダルを取れたのは初。金銀銅が全員うちの学校だった。快挙というかなんというか...。抜ける人と残る人的に、来年も Paken で金銀銅が十分有り得そう。
感想としては、もちろん反省点がないということはないがコンテストはそういうものなので、全ての問題で大きなミスなくよい結果を取れたことを喜びたいと思う。望外の順位ではあったがその分あと一歩の悔しさもある。来年は金賞を取りたい。
抱負
春合宿も同じ調子でいけることを祈ります。色々忙しいんですが、最善を出せるように精進します。
今年もとても楽しかったです。事務局の方々、チューターの方々、ありがとうございました。
