EDPC Z - Frog 3
カエル3
考え方
ABCでいうと、F問題級。
$O(N^2)$ でよければ非常に簡単。
手前の全ての足場から実際に移動するコストを $O(N)$ で求めて、最小値を探す動的計画法でよい。
このコスト最小値を求める部分をどうにか平均 $O(1)$ に高速化できれば、全体が $O(N)$ になる。
足場 $i$ から足場 $j$ に移動するコストは、$(h_j-h_i)^2+C=h_i^2-2h_ih_j+h_j^2+C$ である。
つまり、足場 $j$ に移動する最小コストは、以下である。
$$
DP[j] = \min_{i<j} \{(DP[i]+h_i^2)-2h_ih_j\}+(h_j^2+C)
$$
最後の $h_j^2+C$ 部分は $i$ によらないので、最小値を求めた後で別途足せばよい。
$\{(DP[i]+h_i^2)-2h_ih_j\}$ についてなのだが、これは二次元平面上の話に読み替える。
$xy$ 平面上に点 $(h_i,DP[i]+h_i^2)$ を取り、そこを通る傾き $2h_j$ の直線を引く。
このとき、$y$ 切片の値が、まさに $\{(DP[i]+h_i^2)-2h_ih_j\}$ となる。
ということで、$i<j$ である全ての $i$ について $(h_i,DP[i]+h_i^2)$ という点をプロットした平面を用意する。
これら全ての点から傾き $2h_j$ の直線を引き、最も下に来るものがどれか考える問題が解ければよい。
そして、これはプロットした点の凸包（下側）を用いれば解ける。
凸包上を左から見ていき、次の点との傾きが $2h_j$ より少ない限り右へ進んでいけばよい。
初めて傾きが $2h_j$ 以上になったところ、または凸包の右端が、足場 $j$ の直前に使うべき足場 $i$ である。
足場番号の記録は不要で、座標 $(x,y)$ から $y-2xh_j+h_j^2+C$ を足場 $j$ の最小コストとすればよい。
あとはこれを平均 $O(1)$、延べ $O(N)$ で達成できるか。
凸包の計算は、普通のモノトーンチェーンを動的に行えばよい。
新しい点が $x$ 座標の昇順にしか追加されないため、延べ $O(N)$ で達成できる。
凸包上の走査も、調べる傾きは単調増加するので、走査用インデックスが左へ戻ることは基本的にない。
よって、凸包を作るインデックスと併走させるツーポインタ法で行えば、延べ $O(N)$ で済む。
唯一、凸包生成で今いる点が消された場合だけ、走査用インデックスが例外的に左へ戻ることがある。
その場合も、傾きの構成を考えれば凸包の末尾に移動させればいいだけなので、計算量に影響はない。
以上で高速化を達成できた。
計算量は $O(N)$。
入力例1での動作
入力を受け取る。
n: 5
c: 6
h: {1, 2, 3, 4, 5}足場 $i$ までの最小コストを $D_i$ とする。
既に最小コストが求まった足場 $i$ から、平面上の点 $P_i=(h_i,D_i+h_i^2)$ を作る。
次の足場の高さを $H$ とすると、各点 $(x,y)$ が与える候補値は $y-2Hx$ である。
これが最小になる点を下側凸包から探し、最後に $H^2+C$ を加える。
最初の足場では $D_0=0$ なので、$P_0=(1,1)$ である。
高さ $2$ の足場では、候補点は $P_0$ だけである。
$D_1=1-2\times2\times1+2^2+6=7$ となる。
したがって、新しい点は $P_1=(2,7+2^2)=(2,11)$ となる。
下側凸包は次の2点である。
(1, 1), (2, 11)高さ $3$ の足場を考える。
調べる傾きは $2H=6$ である。
凸包の辺 $(1,1)\to(2,11)$ の傾きは $10$ である。
$10$ は $6$ 以上なので、最小値を与える点は左側の $(1,1)$ のままである。
$D_2=1-2\times3\times1+3^2+6=10$ となる。
新しい点は $P_2=(3,10+3^2)=(3,19)$ である。
ここで3点 $(1,1),(2,11),(3,19)$ を見る。
最初の辺の傾きは $10$、次の辺の傾きは $8$ である。
下側凸包では辺の傾きが増加する必要があるので、中央の $(2,11)$ は凸包から外れる。
(1, 1), (3, 19)高さ $4$ では、調べる傾きは $8$ である。
凸包の辺の傾きは $9$ なので、最小値を与える点は $(1,1)$ である。
$D_3=1-2\times4\times1+4^2+6=15$ となる。
新しい点は $P_3=(4,15+4^2)=(4,31)$ である。
下側凸包は次のようになる。
(1, 1), (3, 19), (4, 31)最後に高さ $5$ を考える。
調べる傾きは $10$ である。
$(1,1)\to(3,19)$ の傾きは $9$ で、調べる傾き $10$ より小さい。
そのため、候補点を右の $(3,19)$ へ移す。
次の辺 $(3,19)\to(4,31)$ の傾きは $12$ である。
これは $10$ 以上なので、ここで止まる。
したがって、$(3,19)$ が最小値を与える。
$D_4=19-2\times5\times3+5^2+6=20$ となる。
答えは $20$。
注意点
答えは、int 型からはみ出る。
long long 型を用いること。
別解
CHT（凸包トリック）で解く方法もある。
というか、おそらく問題を作った人の意図はそちら。
この解説の解法とは、互いにルジャンドル＝フェンシェル変換した関係にある。
（厳密には、大小反転を含む定数倍程度の差異はあるが）