KUPC 2016 H - 壁壁壁壁壁壁壁

• 問題
• AC (slope trick)
• 部分点 (単体法)

位置$i$から$i+1$に補強材を移動する量を$x_i$として制約を書き下す。$n=4$なら

• $A_1-x_1 \ge B_1$
• $A_2 + x_1-x_2 \ge B_2$
• $A_3 + x_2-x_3 \ge B_3$
• $A_4+x_3 \ge B_4$

という制約の下で$|x_1|+|x_2|+|x_3|+|x_4|$を最小化する問題になっている。

$f_i(x)$を$x_1, ..., x_{i-1}, x_i=x$までを決定した際の最小コストとする。slope trick向けに制約を変形すると、

• $x_1 \le A_1-B_1$
• $x_1 \ge x_2-(A_2-B_2)$
• $x_2 \ge x_3-(A_3-B_3)$
• $x_3 \ge B_4-A_4$

となって、一番上の$x_1$に関する制約を無視すると$f_i$の漸化式が得られる:

• $f_1(x) = |x|$
• $f_2(x) = \min_{t \ge x - (A_2-B_2)}f_1(t) + |x|$
• $f_3(x) = \min_{t \ge x - (A_3-B_3)}f_2(t) + |x|$

登場する操作はすべてslope trickで表現できて、答えは凸性により、$B_4-A_4$か$\argmin_xf_3(x)$の大きいほうの位置で$f_3$の値を求めると得られる。

制約$x_1 \le A_1-B_1$については、この範囲を超えると高いコストがかかることにして対処したい。$x_1$が$A_1-B_1$を$1$超過することによる利益が高々$C$であるとき、$f_1(x) = |x| + C\max(0, x-(A_1-B_1))$とすればよい。$C$の具体的な値としては、制約を$1$だけ破っている状態を解消するために1つの補強材を端から端へ移動すると$N-1$のコストがかかるので、$N-1$でよい。

CodeChef - CCDSAP Exam

• 問題
• AC

slope trickの練習問題として解いた。

人$i$の初期位置を$a_i$とし、人$i$を位置$x$に配置した場合の人$1, 2, ..., i$に関するコストの総和の最小値を$f_i(x)$とする。

左右の境界を無視すると$f_{i}(x) = \min_{t \le x-2}f_{i-1}(t) + |x-a_{i}| = \min_{t \le x}f_{i-1}(t-2)+|x-a_i|$と表せる。これだけなら普通のslope trickで解けるが実際には境界を越えられないところが難しい。

境界を越えたら大きなコストがかかるように、$|x-a_i|$の代わりに定数$C$を定めて$C\max(0, 1-x) + |x-a_i| + C\max(0, x-N)$を追加することを考えたが、これは優先度付きキューに一つずつ挿入していく方法では難しそう。平衡二分木で多重集合を管理すればいけそう？ → 平衡二分木slope trickを作ろうとしたが、最小値の更新が自明にはできない。おそらく任意の$x$について$f(x)$の値が取得できる必要があって、実現方法がわからなかった。ただ、$\min$がわからなくても$\argmin$は容易に取得・更新できる。これだけわかれば最適解を貪欲に復元できそう。最適解における人$i$の位置を$y_i$とする。$y_N=\argmin_x f_{N}(x)$は既知であり、$y_{i+1}$が既知であるとき$y_i$は

$$y_i = \min(\argmin_x f_{i}(x), y_{i+1}-2)$$

と決定できる。$\argmin$が複数ある時はどれを取ってもよい。

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

• 問題
• 提出

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

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

CodeChef - Short in Average

• 問題
• AC

$A$から$B$へのウォークが与えられたとする。このウォークが閉路を含んでいて閉路の平均長がウォークの平均長より小さいなら、何回も回ればウォークの平均長を閉路の平均長まで下げられるし、そうでないなら閉路を除いて損しない。また、閉路を含まないウォークは高々$N-1$本の辺しか含まない。従って、以下のようなアルゴリズムが考えられる:

1. $B$に到達できる頂点の集合$W \subseteq V$を求めて、以降は$W$による誘導部分グラフ上で考える。
   • この時点で$A$と$B$がつながっていなければ終わり。
2. Bellman-Ford法のようなDPをして、高々$N-1$辺を通るという条件の下での$A$から$B$までの最短平均長ウォークの長さを求める。
3. $A$から到達できる最短平均長閉路の長さを求める。
4. 2と3の小さいほうを取る。

実装上は3のアルゴリズムが2のDPを含んでいる。2は$N-1$回、3は$N$回回す必要があるので、最初から$N$回回せばよい。

3については、$\operatorname{dp}[k][v] =$ちょうど$k$本の辺を使う場合の$S$から$v$への最短経路、として

$$ L = \min_{v \in N}\max_{k = 0, ..., N-1} \frac{\operatorname{dp}[N][v] - \operatorname{dp}[k][v]}{N-k} $$

が求める長さである。ただし、$S$から到達できない頂点がある時にそのまま扱うと$\infty - \infty$という計算が起きてしまうので、$\operatorname{dp}[N][v] = \infty$の場合は除いて計算する。全部そう（＝$N$回目で到達できる頂点がない）なら閉路がないグラフなので$L = \infty$になるべきで、つじつまがあっている。

解説は「平均長が$L$以下のウォークが存在するか？」という判定問題を解いて二分探索する方針だった。判定問題は、すべての辺の重みから$L$を引いた時に$S$から$T$への長さ$0$以下のウォークが存在するかどうかで判定できて、これはやはりBellman-Fordで調べられる。

CODE FESTIVAL 2016 Grand Final D - Dice Game

• 問題
• AC

Petrの純粋戦略は$2$通り:

• 赤を選ぶ
• 青を選ぶ

touristの純粋戦略は$2^6=64$通り:

• どの目が出ても赤と答える。
• 2, 3, ..., 6が出たら赤と答え、1が出たら青と答える。
  ...
• どの目が出ても青と答える。

これらの混合戦略の中からお互いに最適戦略を取った時にtouristが勝つ確率を知りたい。

$a_{ij} =$ Petrが戦略$i$を取ってtouristが戦略$j$を取った時にtouristが勝つ確率、とすると行列$(a_{ij})$の見た目は

$$ \begin{bmatrix} 1 & 1-p_1 & 1-p_2 & 1-(p_1+p_2) & ... & 0 \\ 0 & q_1 & q_2 & q_1+q_2 & ... &1 \end{bmatrix}$$

となっている。touristの混合戦略を$(x_1, ..., x_{64})$で表すとき、touristは$a_{1, 1}x_1 + ... + a_{1, 64}x_{64}$と$a_{2, 1}x_1 + ... + a_{2, 64}x_{64}$の小さいほうを最大化したい。この問題は以下のLPになっている:

• $\textrm{maximize} \ z$
• $a_{1, 1}x_1 + ... + a_{1, 64}x_{64} \ge z$
• $a_{2, 1}x_1 + ... + a_{2, 64}x_{64} \ge z$
• $x_1+ ... + x_{64} = 1$
• $x_1, ... x_{64} \ge 0$

これは単体法などで解けるが、もう少し簡略化する。touristの戦略は「目$i$が出たら$y_i$の確率で赤を選ぶ」という形で表せる。Petrが赤、青を選んだ時にtouristが勝つ確率はそれぞれ$p_1y_1+...+p_6y_6$、$q_1(1-y_1)+...+q_6(1-y_6)$であり、touristはこれらの小さいほうを最大化したい。この問題は以下のように書ける。

• $\textrm{maximize} \ z$
• $p_1y_1+...+p_6y_6 \ge z$
• $q_1(1-y_1)+...+q_6(1-y_6) \ge z$
• $y_1, ..., y_6 \in [0, 1]$

これもLPだけれど、変数が少ないので非基底変数の組み合わせを総当たりするだけでもよさそう。