ツバサの備忘録

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

Typical DP Contest D - サイコロ

動的計画法(DP)

問題
 提出コード
復習問題だったのですが、見事MLEを吐きました。

解法

$d_2 =D$ を素因数分解したときに登場する2の個数、とします(3,5も同様です)。
基本的な方針としては、
$dp[i][j][k][l] = i$ 回サイコロを振ったときに、2が $j$ 回、3が $k$ 回、5が $l$ 回登場するような確率
とします。4は2が2回分、6は2と3が1回ずつ分として計算します。
初期状態は、 $dp[0][0][0][0] = 1$ です。
$i+1$ 回目に、1~6のどれを出すか、で遷移を行っていきます。
1から順番に、それぞれ以下のようになります。

$dp[i+1][j][k][l] += dp[i][j][k][l]/6$
$dp[i+1][j+1][k][l] += dp[i][j][k][l]/6$
$dp[i+1][j][k+1][l] += dp[i][j][k][l]/6$
$dp[i+1][j+2][k][l] += dp[i][j][k][l]/6$
$dp[i+1][j][k][l+1] += dp[i][j][k][l]/6$
$dp[i+1][j+1][k+1][l] += dp[i][j][k][l]/6$

答えは、 $D$ を素因数分解したときに2,3,5以外の素因数が含まれていたら0、そうでなければ $j \geqq d_2, k \geqq d_3, l \geqq d_5$ となる $j,k,l$ を選んだ時の $dp[N][j][k][l]$ の総和です。ただし、このままだと途中でMLEやらなんやらを吐きACすることができません(少なくとも自分はそうでした)。そこで、 $i$ 回目で $j,k,l$ がそれぞれ $d_2,d_3,d_5$ にたどり着いた時点で、それ以降は1~6のどの目がでても問題の条件を満たす、ということに着目すると、以下のようにDPを組み替えることができます。

$dp[i+1][j][k][l] += dp[i][j][k][l]/6$
$dp[i+1][min(j+1,d_2)][k][l] += dp[i][j][k][l]/6$
$dp[i+1][j][min(k+1,d_3)][l] += dp[i][j][k][l]/6$
$dp[i+1][min(j+2,d_2)][k][l] += dp[i][j][k][l]/6$
$dp[i+1][j][k][min(l+1,d_5)] += dp[i][j][k][l]/6$
$dp[i+1][min(j+1,d_2)][min(k+1,d_3)][l] += dp[i][j][k][l]/6$

このように組み替えることで、メモリを抑えつつ、また、答えは $dp[N][d_2][d_3][d_5]$ を見るだけでわかるようになります。