問題 解法 解答 問題 beta.atcoder.jp 解法 まず，D を素因数分解し，2, 3, 5 以外の素因数があった場合は，答えは 0 と決まる． そうでないとき，「dp(i, tw, th, fi) := i 回サイコロを振り，素因数 2 が tw 回，素因数 3 が th 回，素因数 5 が fi 回出た…

問題 解法 解答 問題 beta.atcoder.jp 解法 「dp(i, j) := 人 i が j 回戦目で勝つ確率」と DP を立てる．人 i と j 回戦目で当たる可能性がある人を人 l, l + 1, l + 2, ... , r とし，人 a が人 b に勝つ確率を p_(a, b) とすると， dp(i, j) = dp(i, j - …

問題 解法 解答 問題 beta.atcoder.jp 解法 「dp(i, j, f) := 左の山から i 個，右の山から j 個取られていて今のターンが f の時のすぬけ君の取るものの価値の合計の最大値」と DP を立てる．DP 内で f に応じて処理を変える．具体的には，f がすぬけ君の場…

問題 解法 解答 問題 beta.atcoder.jp 解法 N <= 100 なので，(i - 1) 番目までの要素でできた点数それぞれに対して i 番目の要素を足し合わせたものを新しく答えに追加すればよい．重複が生じるものがあるので，set を使って処理する．O(N^2 * logN)． 解答…

問題 解法 解答 問題 https://www.ioi-jp.org/camp/2011/2011-sp-tasks/2011-sp-day3.pdf 解法 「dp(i) := i 文字目から L 文字目までで考えられる原文の数の総和」と DP を立てる．このとき，S[i] と同じ文字が出てくる位置を p とすると， dp(i) = dp(i + …