Codeforces Round #351 (Div. 1) C. Levels and Regions
3 時間近く掛けてようやく AC。
http://codeforces.com/contest/674/problem/C
問題
数列 t[i] が与えられる。これを K 個の連続する部分列に分割する。各部分列はゲームにおけるレベルに対応しており、プレイヤーはレベル 1 からレベル K の順に攻略していく。
レベル X = a[0],a[1],...,a[m] とする。まずプレイヤーはステージ 0 にいる。確率 a[i]/(a[0]+...+a[i]) でステージ i をクリアし、ステージ i+1 に遷移できる。
クリアに掛かる時間の期待値の最小値を求めよ。
- 1≦n≦200,000
- 1≦k≦min(50,n)
- 1≦t[i]≦100,000
解法
レベルが 1 つだけのときを考えよう。
- E[i] := ステージ i に到達するのに必要な時間の期待値
とする。$p=t[i]/(t[0]+...+t[i])$, $q=1-p$ としたとき、次の式が成り立つ。
$$ \begin{align} E[i+1]&=p(E[i]+1)+pq(E[i]+2)+pq^2(E[i]+3)+\cdots \\ &= E[i] p\left(1 + \frac{1}{q} + \frac{1}{q^2} + \cdots \right) + p\left( 1 + \frac{2}{q} + \frac{3}{q^2} + \cdots \right) \\ &= E[i] \frac{p}{1-q} + \frac{p}{(1-q)^2} \\ &= E[i] \frac{p}{p} + \frac{p}{p^2} \\ &= E[i] + \frac{1}{p} \end{align} $$
次のような DP を考える。
- dp[i][j] := 位置 i がレベルの開始地点、j 個のレベルを既に作った、という状態に至る期待値の最小値
(i,j)→(k+1,j+1) に遷移させた時のコストは、先ほど計算した期待値の式を用いて次のように表せる。
$$ dp[i][j] + \sum_{x=i}^{k} \frac{t[i]+\cdots+t[x]}{t[x]} $$
$sum[i+1]=sum[i]+t[i]$ と定義すると、上式は次のようにできる。
$$ dp[i][j] + \sum_{x=i}^{k} \frac{sum[x+1]-sum[i]}{t[x]} $$
さらに次のように変形を掛ける。
$$ dp[i][j] + \sum_{x=i}^{k} \frac{sum[x+1]}{t[x]} - sum[i]\sum_{x=i}^{k} \frac{1}{t[x]} $$
総和の部分は累積和が使えるので、次のように書ける。
$$ dp[i][j] + S[k+1]-S[i] - sum[i] (T[k+1]-T[i]) $$
これで dp[i][j] が次のように書けることが分かった。
$$ dp[i+1][j+1] = \min_{1\le k \le i} (-sum[k]T[i+1]+dp[k][j]-S[k]+sum[k]T[k]) + S[i+1] $$
ここまで来れば convex hull trick (CHT) が見えるはず。
CHT に直線 $sum[i]x + dp[i][j]-S[i]+sum[i]T[i] $ を入れていくことで無事 O(nk log n) を達成できる。
convex hull trick は蟻本に書いてある。僕も convex hull trick 単体の解説ではないけど書いているので良かったら参考に。
Codeforces Round #351 (Div. 1) C. Levels and Regio ...
BとCの難易度の差がかなりあるように感じた。もっと簡単な考え方があるのかな。
