読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

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 単体の解説ではないけど書いているので良かったら参考に。

pekempey.hatenablog.com

Codeforces Round #351 (Div. 1) C. Levels and Regio ...

BとCの難易度の差がかなりあるように感じた。もっと簡単な考え方があるのかな。