Codeforces Round #344 (Div. 2) E. Product Sum
Convex Hull Trick は蟻本にも書いてあるらしいが知らなかった。
問題概要
サイズ n の配列 a が与えられる。配列の characteristic は $\sum_{i=1}^n a_i \cdot i$ で定められる。
一回だけ配列の要素をひとつ抜き取って好きな場所に挿入する操作を行ったときの characteristic の最大値を求めよ。 なお、選んだ要素を同じ位置に挿入することも許される。
解法
$i$ 番目の要素を $j \, (i<j)$ 番目に移動させたときの characteristic の増分は以下の式で表せる。
$$ (a[l] \cdot r - s[r]) + (-a[l] \cdot l + s[l]) $$
$l$ を固定して $a[l] \cdot r - s[r]$ の最大値を求めればいい。
突然だが、次のようなクエリを考える。
- 直線 $f_i(x)=a_i x+b_i$ をリストに追加する
- $\max f_i(x)$ を計算する
もしこのようなクエリが高速に処理できるなら、$x \cdot r - s[r]$ を追加して $\max f_i(a[l])$ を計算するという処理を配列の後ろから順に行っていくことにより計算できる。
このクエリを高速に行うために最大値の候補になり得ない直線をあらかじめ削除しておく。こうすることにより、ある地点 x で一番上にある直線を二分探索で求めることができる。どのように二分探索をするのだろうか。
上の図において傾きの小さい順に L0, L1, L2 としたとき、
- 左側では L0(x)≧L1(x)≧L2(x)
- 中央では L0(x)≦L1(x)≧L2(x)
- 右側では L0(x)≦L1(x)≦L2(x)
が成り立っていることが分かる。5 つ直線があれば
- L0(x)≧L1(x)≧L2(x)≧L3(x)≧L4(x)
- L0(x)≦L1(x)≧L2(x)≧L3(x)≧L4(x)
- L0(x)≦L1(x)≦L2(x)≧L3(x)≧L4(x)
- L0(x)≦L1(x)≦L2(x)≦L3(x)≧L4(x)
- L0(x)≦L1(x)≦L2(x)≦L3(x)≦L4(x)
になる。増減の変化が高々 1 回なので差分の正負で二分探索ができることが分かる。
今回は追加する直線の傾きに単調性があるため直線の削除処理は比較的簡単である。リストに追加するときに不必要になる末尾を削除していけばいい。
不必要かどうかの判定法は蟻本に書いてある。
3 本の直線を傾きが大きい順に
$f_1(x)=a_1 x + b_1$
$f_2(x)=a_2 x + b_2$
$f_3(x)=a_3 x + b_3$
$a_1 \ge a_2 \ge a_3 $としたとき、
$$ f_2 が最も下側と成り得ない \Leftrightarrow (a2-a1)\times(b3-b2)\ge(b2-b1)\times(a3-a2) $$
要素を右から左にも移動できることを忘れてはならない。
Editorial のコードに影響されてしまった。
Codeforces Round #344 (Div. 2) E. Product Sum
とても教育的だった。
