Educational Codeforces Round 16: E. Generate a String
問題概要
- 現在の文字列の末尾に 'a' を追加(コスト x)
- 現在の文字列の末尾を削除(コスト x)
- 現在の文字列全体をコピーし、末尾に貼り付け(コスト y)
という 3 種類の操作を使って長さ n の文字列を作る最小のコストを求めよ。
- $1 \le n \le 10^7$
- $1 \le x,y \le 10^9$
解法
priority queue を使えば DP できるが制約がきついため間に合わない。
i までの最短経路というのは、
- k<i から +1 し続ける
- k<i から *2 して、-1 し続ける
のどちらかである。一度 i を追い越したら -1 以外の操作をするのは無駄というのが効いている。このことを使うと遷移が DAG になる。ただし k からの遷移先が k+1..2k と広範囲になるため、ループを回すだけの更新では間に合わない。
更新時に知りたいのは以下の値。
$$ \min_{k<i\le 2k}\{dp[k]+y+(2k-i)x\}= \min_{k<i\le 2k}\{dp[k]+y+2kx\}-ix $$
これはスライド最小値の要領で計算できる。スライド最小値は蟻本 p.300 を参照。
i+1,2i,2i-1 の 3 つに遷移させるだけでも通るみたいだけど、そっちは理解していない。