第七回 アルゴリズム実技検定

• 問題
• 提出

辛うじて全完したが、最後の問題の正しい解法がわからなかった。

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で一番難しく感じた。