今日解いた競プロの問題。

いろはちゃんコンテスト Day1-K: 期待値を求めるということはM1×M2×…通りの答え全てを足してM1×M2×…で割るということで、これにM1×M2×…をかけて出力しろということなので、要するに出る答えの総和を出せということになる。

まず円盤1個の場合を考える。この場合は単純に出目の総和をとればいい。

円盤2個の場合を考える。$A_{i,j}$の桁数を$L_{i,j}$とすると、

$\sum_{i=1}^{M_1}\sum_{j=1}^{M_2} (A_{1,i}\times 10^{L_{2,j}}+A_{2,j})=(\sum_{i=1}^{M_1}A_{1,i})(\sum_{j=1}^{M_2} 10^{L_{2,j}}) + M_1 \sum_{j=1}^{M_2} A_{2,j}$

同様に円盤3個、4個…と考えていくと、

$dp[k+1]=\sum_{i=1}^{M_k} (dp[k]\times10^{L_{k,i}}+A_{k,j}\times\prod_{i=1}^{k-1} M_i)$

みたいな遷移でいけることが分かる。

---

XRKaigiとかいうのがやってたらしい。一応明日までやっているっぽいが、さすがに授業もあるので行けなさそう。