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