辛うじて全完したが、最後の問題の正しい解法がわからなかった。
K - 急ぎ旅
最短経路DAGを作ってからDPした。
ダイクストラと同時にできるらしい。確かに。
L - たくさんの最小値
最小値の列挙は遅延セグメント木上を二分探索すればできる。いつもこの方針でやっていて、想定解のようにノードに持たせる情報を増やすやり方でやったことがない。後者でないと難しい設問ってあるんだろうか。
M - 分割
明らかに最小費用流だと思ったが、グラフの作り方で長時間かけてしまった。
辺の下限流量を決めて変形するイメージで作った。まず、整数$A_i$を表す各位置$i$を$i_{\mathrm{in}}, i_{\mathrm{out}}$に分割する。
- $S$から$i_{\mathrm{out}}$に容量1、コスト0の辺を張る
- $i_{\mathrm{in}}$から$T$に容量1、コスト0の辺を張る
- $i_{\mathrm{out}}$から$T$に容量1、コスト$C$の辺を張る
- $i < j$であるすべての$j$について、$i_{\mathrm{out}}$から$j_{\mathrm{in}}$に容量1、コスト$|A_i-A_j|$の辺を張る
想定解は「通ってほしい辺」のコストを$-\infty$にしてから変形する考え方のようだった。こちらは全然考えたことがなかった。
N - モノクロデザイン
JOI 2012 春合宿 - fortune_telling
O - コンピュータ
$(B_i)$が狭義単調増加の場合が解ければよい。また、世界には$B_1, ..., B_N$円のコンピュータしか存在しないとしてよい。
$\operatorname{dp}[x] = x$日目でちょうどコンピュータを買い替えなければならない場合の最大所持金額
とする。$x$日目に買えるコンピュータは、所持金以下であるような最大価格のコンピュータを$r$として$B_x, B_{x+1},..., B_r$のいずれかであり、$B_y$を買うとすると遷移は$\operatorname{dp}[y+1] := \max(\operatorname{dp}[y+1],\operatorname{dp}[x]+A_{x+1}+A_{x+2}+...+A_{y+1}-B_y)$。$A_{x+1}+A_{x+2}+...+A_{y+1}$の部分を累積和で計算すると、このDPは${O}(N^2)$である。
$o(N^2)$にする方法がわからなかった。試しに、買うコンピュータを$x$か$r$だけにしたものを投げると半分以上は通る。それならと思って両端から2000個程度（$x, x+1, ..., x+2000$と$k-2000, ..., k-1, k$）の遷移に限定してみたらACした。
解説を見た。
$\operatorname{dp}[x] =$ コンピュータ$x$を買った時点での支出の最小値
とする。コンピュータ$p$を買ってから次に買うコンピュータとして$x$を選べる必要十分条件は$A_1+...+A_{p+1}-\operatorname{dp}[p] \ge B_x$であること。これが成り立つような$p$について、$\operatorname{dp}[x] := \min_p\operatorname{dp}[p] + B_x$と更新すればよい。
実装としては、range minを載せた平衡二分木のキー$A_1+...+A_{p+1}-\operatorname{dp}[p]$に値$\operatorname{dp}[p]$を対応させておけば、キーが$B_x$以上のノードについての$\operatorname{dp}[p]$の最小値を高速に求められる。
Oは今までのPASTで一番難しく感じた。
