きろく

特筆すべき記録のまとめ

いろはちゃんコンテスト Day1:K - ルーレット

問題

atcoder.jp

解法

答えの E * (M_1 * M_2 * ... * M_N) は読み上げられる数字の総和であるので,確率などを気にする必要はない.ルーレットの番号が小さいものからこの総和を求めていく.

dp(i) := ルーレット i までで構成出来る数字の総和

と DP を立てる.ルーレット i で新たに読み上げられる数字は ~ A_i_j という形をしているので,ルーレット i - 1 までで読み上げられる数字を 10^(A_i_j の桁数) 倍したものに A_i_j を M_1 * M_2 * ... * M_(i - 1) 倍(=ルーレット i - 1 までで読み上げられる数字の通り数)したものを足せばよい.遷移が O(M) となるが,M_1 + M_2 + ... + M_N <= 200000 であるので,全体で O(N + M) となり間に合う.

解答

atcoder.jp

f:id:babcs2035:20190503163522p:plain