ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

Educational DP Contest / DP まとめコンテスト J - Sushi

動的計画法(DP) 条件の作成

問題
提出コード
Sushi問題は難しいことで有名です（要出典）

解法

ループする系の期待値は、こんな感じで立式すると見えてきます。
今回は、お皿にのっているお寿司の数を利用します。
3個のっている寿司がi皿、2個がj皿、1個がk皿だとして、そこから全ての寿司を食べるまでにサイコロを振る回数の期待値をdp[i][j][k]とします。
すると、3個のっているお皿の寿司を食べるとそのお皿にのっている寿司の個数が2に、2個のっているお皿は1個に、1個は0個になることを考えると、次のような式がなりたちます。

dp[i][j][k] = 1 + \frac{i\times dp[i-1][j+1][k]}{N} + \frac{j\times dp[i][j-1][k+1]}{N} + \frac{k\times dp[i][j][k-1]}{N} + \frac{(N-i-j-k)\times dp[i][j][k]}{N}

さて、この式にはdp[i][j][k]が2箇所出てきているので、このままでは解くことができません。ので、両辺を整理すると、次のような式が出来上がります。
dp[i][j][k] = \frac{N\times (1 + \frac{i\times dp[i-1][j+1][k]}{N} + \frac{j\times dp[i][j-1][k+1]}{N} + \frac{k\times dp[i][j][k-1]}{N}) }{i+j+k}

あとは、この式をコードに落とし込めば、この問題を解くことができます。
dp[0][0][0]を上の遷移に当てはめてしまうと、0で割ることになってしまうので、別枠で0と初期化しておくことに気を付けます。答えは、入力されたa_iの3~1の個数をそれぞれx,y,zとしたとき、dp[x][y][z]となります。