AtCoder ARC128 C - Max Dot の双対解

問題概要

整数 $N, M, S$ と数列 $A_1, A_2, \dots, A_N$ が与えられる．

非負実数列 $x_1, x_2 ,\dots x_N$ が $0 \leq x_1 \leq x_2 \leq \dots \leq x_N \leq M$ と $\sum _ {i=1}^{N} x_i = S$ を満たすとき， $\sum _ {i=1}^{N} A_i x_i$ の最大値を求めよ．

問題へのリンク

解法

$y_i = x_i - x_{i-1}$ とします．(ただし $x_0 = 0$ とします)

$y_i$ を使って問題を言い換えると以下のようになります．

制約

$y_i \geq 0$
$\sum _ {i=1}^{N} y_i \leq M$
$\sum _ {i=1}^{N} (N + 1 - i) \times y_i = S$

最大化

$\underset{y_i}{\max} \sum _ {i=1}^{N} \left( \sum _ {j=i}^{N} A_j \right ) y_i$

これは線形計画問題なので双対を取っても最適値は同じです．

制約

$\lambda _ 1 \geq 0$
${} ^ \forall i, \sum _ {j=i}^{N} A_j \leq \lambda _ 1 + (N + 1 - i) \times \lambda _ 2$

最小化

$\underset{\lambda _ 1, \lambda _ 2} {\min}M \lambda _ 1 + S \lambda _ 2$

うれしいことに最適化すべき変数が 2 つになりました．

$\lambda _ 1$ を固定すると $\lambda _ 2$ の最小値は $O(N)$ で出せるので， $\lambda _ 1$ で三分探索して $M \lambda _ 1 + S \lambda _ 2$ を最小化すれば計算量は $O(N \log (M A_{\max}))$ です．

提出コード

おまけ三分探索で最適解が出ることの証明

$\lambda _ 1 = p$ での制約を満たす $\lambda _ 2$ の最小値を $f(p)$ と書くことにします．

ここで $(\lambda _ 1, \lambda _ 2) = (p_1, f(p_1)), (p_2, f(p_2))$ は制約を満たすので，任意の $0 \leq s \leq 1$ を満たす $s$ について $(s p_1 + (1 - s) p_2, s f(p_1) + (1 - s) f(p_2))$ も制約を満たします．

$\lambda _ 1 = s p_1 + (1 - s) p_2$ での $\lambda _ 2$ の最小値は $f(s p_1 + (1 - s) p_2)$ であるので $f(s p_1 + (1 - s) p_2) \leq s f(p_1) + (1 - s) f(p_2))$ であり， $f(p)$ は凸関数です．