こんにちは、nouka28です。
2025年1月25日、2月2日に行われた JOI 2024/2025 本選に参加しました。
結果は 100-100-100-46-3 の 349 点で総合 11~15 位程度（多分）でした。
Day1
- 講演会はすごい面白かったです
- もうJOI本選は3回目で、慣れたこともあり、プラクティスはスムーズに行うことができました
- チューター企画は、競プロの問題を絵で表し、相手がその絵と制約、サンプルケースを見て問題を解くみたいな感じでした。とても難しかった...僕たちのチームは3位（16チーム中）でした
- チューター企画が終わった後すぐに ARC191 (Div.2) に参加しました。久しぶりに橙perfを取れてうれしかったです
Day2
競技当日です。
競技が始まりました。(13:00:00)
Aを見ます。すぐにわからなくて困りますが、よく見ると $A,B$ を昇順に並べて後ろから取っていけばよいことに気づきます。(A AC 100点 13:09:47)
Bを見ます。$B$ の累積和 $S_i=B[0,i)\ の総和$ とすると地点 $i$ に体力 $x$ でいる場合、$x+S_j-S_i\geq A_j$ から $x-S_i\geq A_j-S_j$ を満たす必要があり、あとは $A_j-S_j$ のmaxを取ればよく、セグ木で解けることがわかります。書きますが、サンプルが合いません。よく見ると $j-1,j-2,\dots,1$ で倒すのかと誤読していましたが、そうではなく、$1,2,\dots,j-1$ で倒すと書いてありました、円環なので配列を2倍にすればよいです。(B AC 100点 13:23:23)
Cを見ます。しばらく見ると、条件を1を除くすべての頂点の入次数が正に言い換えられることに気づきます。$T[c]=(c\leq C_j\leq r$ の辺を使ったときすべての頂点の入次数が正となるような最小の $r)$ として、 $T[c]$ は尺取り法みたいなのりで優先キュー、セグ木を使って求まることがわかります。
ここまでの考察があってるか確かめるためにここの部分を実装して提出すると0点が返ってきます (C 0点 13:54:32) が、よく見るとデバッグ時の変数を出力してしまっていることに気づきます。直して提出すると無事30点が返ってきます。(C 30点 13:59:18)
$T$ が求まった後の $\min_i(\max(l-i,0)+\max(T[i]-r,0))$ を求めるパートは $T$ の単調性からセグ木を3本生やせばよいです。デバッグ時の変数を出力して1ペナしますが、無事ACします。(C AC 100点 14:26:07)
Cが去年よりは簡単だと感じ、ボーダーは300を超えると見積もりながらDを見ます。
しばらく考えると最適解においてネクタイの長さが等しいような人は存在しないので $N\leq 500,A_i\leq 15$ のbitdpがわかります。実装すると46点が返ってきます。(D 46点 14:58:58)
ここら辺から多分本選通ったかなあの安心感が出てきて集中力が切れ始めます。Dを1時間程度考察しますが、何もわからなかったため、Eを見て自明の3点を回収します。(E 3点 15:58:47)
Eを見て小課題2の貪欲っぽいものが思いつきますが、細かいところを詰められず実装できず、Dで嘘考察を生やしていたら競技が終了しました。
競技終了
結果は、100-100-100-46-3 の 349点でした。
最初の2時間で346点取った後、残りの2時間で3点しか取っていないのですが...
終了後みんなの点数をみて多分本選通ったかなと思いました。
解説終了後 AHC に出ましたが、集中できずすぐに撤退してしまいました。
今後
去年はCで誤読して233点で落ちたので、今年は行けそうでよかったです。
あと2か月JOIの精進を引き続き頑張っていきたいです。