JOI 本選 2023/2024 参加記


前座

二次予選

最終問題だけ見れば易化だが全体的に難しかったと思う。ボーダーは思っていたより高くて、確か 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 で金銀銅が十分有り得そう。

感想としては、もちろん反省点がないということはないがコンテストはそういうものなので、全ての問題で大きなミスなくよい結果を取れたことを喜びたいと思う。望外の順位ではあったがその分あと一歩の悔しさもある。来年は金賞を取りたい。

抱負

春合宿も同じ調子でいけることを祈ります。色々忙しいんですが、最善を出せるように精進します。

今年もとても楽しかったです。事務局の方々、チューターの方々、ありがとうございました。

Monge / anti-Monge な行列と CHT / Li Chao Tree の関係

導入

N \times M 行列 A が Monge であるとは、以下の条件が成り立つことをいう。

  • 1 \leq i_1 \lt i_2 \leq N 及び 1 \leq j_1 \lt j_2 \leq M を満たす全ての整数の組 (i_1, i_2, j_1, j_2) について、 A_{i_1, j_1} + A_{i_2, j_2} \leq A_{i_1, j_2} + A_{i_2, j_1} が成り立つ。

また、 A_{i_1, j_1} + A_{i_2, j_2} \leq A_{i_1, j_2} + A_{i_2, j_1} \leftrightarrow A_{i_2, j_2} - A_{i_1, j_2} \leq A_{i_2, j_1} - A_{i_1, j_1} なので、 A_{i_2, j_2} \geq A_{i_1, j_2} \rightarrow A_{i_2, j_1} \geq A_{i_1, j_1} である。

N \times M 行列 A が anti-Monge であるとは、以下の条件が成り立つことをいう。

  • 1 \leq i_1 \lt i_2 \leq N 及び 1 \leq j_1 \lt j_2 \leq M を満たす全ての整数の組 (i_1, i_2, j_1, j_2) について、 A_{i_1, j_1} + A_{i_2, j_2} \geq A_{i_1, j_2} + A_{i_2, j_1} が成り立つ。

また同じように、 A_{i_1, j_1} + A_{i_2, j_2} \geq A_{i_1, j_2} + A_{i_2, j_1} \leftrightarrow A_{i_2, j_2} - A_{i_1, j_2} \geq A_{i_2, j_1} - A_{i_1, j_1} なので、 A_{i_2, j_2} \leq A_{i_1, j_2} \rightarrow A_{i_2, j_1} \leq A_{i_1, j_1} である。

アルゴリズム

Monge でも anti-Monge でも本質的には変わらないので、なんとなく後者について説明します。

A_{i_2, j_2} \leq A_{i_1, j_2} \rightarrow A_{i_2, j_1} \leq A_{i_1, j_1} \ (i_1 \lt i_2 \land j_1 \lt j_2) より、全ての整数の組 i_1, i_2 \ (1 \leq i_1 \lt i_2 \leq N) について、 A_{i_2, k + 1} \gt A_{i_1, k + 1} かつ A_{i_2, k} \leq A_{i_1, k} を満たす k \ (1 \leq k \lt M) が高々 1 つ存在します。存在しない場合は k = M とすると、 1 \leq x \leq k について A_{i_2, x} \gt A_{i_1, x} を満たし、 k \lt x \leq M について A_{i_2, x} \leq A_{i_1, x} を満たします。

Li Chao Tree

A_{i, j} = f_i(j) とおくと、先程の式は以下のようになります。

  • 1 \leq x \leq k について f_{i_2}(k) \gt f_{i_1}(k) を満たし、 k \lt x \leq M について f_{i_2}(k) \leq f_{i_1}(k) を満たす

任意のペアについてこのような k が存在するような関数群には Li Chao Tree が使えます。証明を求められるとどう書けばいいのか困るのですが (できると思う) 、ここに書いてあるということで許してください。

codeforces.com

DAG の dp で使う場合

下三角行列なので定義域が怪しい感じになるのですが、結局 (最小値 / 最大値) クエリは定義域の中にしか飛ばさないので、適切な値で埋めれば大丈夫です。

嬉しい場合

  • オンライン dp において Monge の最大値 / anti-Monge の最小値を求めるのには LARSCH が使えなくて、その場合オンライン - オフライン変換 + SMAWK よりも定数倍が速いと思う。
  • SMAWK の書き方を忘れてしまったとき。
  • Monge な行列の列がランダムな順番で追加されるので (!?!?!?!?) min / max を求めたいとき。
  • 変なタイミングで謎の位置での最小値を求めたいとき。これは辺の重み関数が Monge かつ別のいい感じの、例えば極値が高々 1 つみたいな性質を持っている (DAG ではない) 一般の完全グラフの最短経路を求めるときに使える場合があると思っている。

Convex Hull Trick のアイデアの適用

なんだか上で満足してしまったような気分ですが、一応。

No.1867 Partitions and Inversions - yukicoder の解説はこれの特殊ケースです。

Li Chao Tree と同じく、 Monge / anti-Monge の場合ではほとんど Convex Hull Trick のロジックがそのまま使えるのですが、いくつか問題点があります。

連続する 3 つの関数のうち中央がいらない場合の判定

一次関数だとこれは定数時間でできるのですが、一般に Monge / anti-Monge となると困ります。二分探索をすればなんとかなります。なので、いわゆる「追加と質問がどちらも単調な場合」にもならし定数時間にはならない、と思っています。(特に anti-Monge でなったら LARSCH と同じ線形時間が達成できることになって、そんなことはなさそう)

追加クエリが (元の CHT でいう) 単調でない場合

こんな場合ある ??? という気持ちですが......。

CHT の場合、傾きで二分探索をして挿入するべき位置を特定していました。一般に Monge だと困ります。

N \times M 行列 A が Monge であり、その i_1, i_2 行目の任意の要素にアクセスできるので、 i_1, i_2 の大小を比較したい、という問題を考えます。これは、 i_1, i_2 行目かつ 1, M列目である A_{i_1, 1},A_{i_1, M},A_{i_2, 1},A_{i_2, M} にアクセスできればよいです。この 4 要素からなる部分行列が Monge かつ anti-Monge である場合は決定できないのですが、その場合決定しないでも問題ないです。

これで比較ができるようになったので、結局 std::map などで二分探索を用いることができます。

うれしい場合

  • 書きやすい ?
  • 条件によっては定数倍がいい気がする。