Educational Codeforces Round 16: E. Generate a String

問題ページ

問題概要

  1. 現在の文字列の末尾に 'a' を追加(コスト x)
  2. 現在の文字列の末尾を削除(コスト x)
  3. 現在の文字列全体をコピーし、末尾に貼り付け(コスト 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 つに遷移させるだけでも通るみたいだけど、そっちは理解していない。