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$が複数ある時はどれを取ってもよい。