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

SRM 656

出ました。

250

N個のパンケーキがあり、i番目のパンケーキの幅はi+1で美味しさはd[i]です。以下のような操作をしてタワーを作ります。

  • 残っているパンケーキをランダムに1つ選びます。(残っていなければ終了)
  • そのパンケーキの幅がタワーの一番上のパンケーキの幅より大きければ終了
  • そうでないなら積んで、最初に戻る

タワーに積まれたパンケーキの美味しさの和の期待値を求めよ。

解法

期待値の線形性を使う。

つまり「Σ d[i] * (i番目のパンケーキが使われる確率)」で答えを求める。

dp[i][j] = i個のパンケーキを既に使っていて、一番上のパンケーキの幅がjである確率

というDPをして、答えは「Σ dp[i][j]*d[j]」で求めるといい。

初期化は、番兵をおいて、dp[0][N]とすると楽。

ちなみに遷移は、

if (k < j) dp[i+1][k] += dp[i][j]*(N-i)

みたいな感じ?

500

長さNのパーミュテーションであって、pos[i]の箇所だけp[i]<p[i+1]でそれ以外はp[i]>p[i+1]であるようなものを数え上げよ。
※ len(pos) = Mとします。

  • N ≦ 10^6
  • M ≦ 2500
解法

包除原理

まず、「posのところの条件を満たす必要がない」という問題を考えます。

単調減少でなければならない区間がM+1個出てきますよね。i個目の区間の長さをa[i]とします。

「posのところの条件を満たす必要がない」という問題の答えは「N!/mul(a[i]!)」です。

では、「posのところの条件を少なくともk個満たさない」という問題を考えます。

これは、

dp[i][j] = i番目の区間までを見て今までで少なくともj個の条件を満たさないものの個数/N!(i=0~M,j=0~M)

みたいなDPを考えるとできます。

「/N!」とかいてありますが、これは計算を簡略化するための工夫で、最後に*N!をするという感じです。

遷移は

dp[i][j] = Σ dp[i-k][j+k]*(Σa[i-k]~a[i])!

みたいな感じです(適当に書いたので細かい±1とかがずれてるかもしれませんが)

で、包除原理を使って答えを求めます。

このままだと3乗ですが、包除原理においては満たす条件の個数はどうでもよくて、その偶奇だけに興味があるので、dp[M][2]のDPにすると2乗になります。

ちなみに、さらにまとめてdp[M](dp[i][0]-dp[i][1]を記録する)にしても良いです。

雑な解説なので、足りないところがあれば考えてみるか、聞いてください。

(本番では階乗の配列を2505で取ってて落ちました。つらい)