問題 arc009.contest.atcoder.jp 解法 「0 から K-1 がバラバラ, 残りは揃っている」の場合の数が分かれば, 後は答えを comb[N][K] 倍するだけです。comb[N][K] はおよそ O(K log K) で求めることができるので, 問題は「」の中身の場合の数です。これは, 包…

問題 arc027.contest.atcoder.jp 解法 解説を参考にしました。 AtCoder Regular Contest 027 解説 from AtCoder Inc. www.slideshare.neth[i] の値は 10 以下であるので, dp[t] = (t 番目の石までたどり着く方法は何通りあるのか) というのは, t より前の 10…

問題 TopCoder Statistics - Problem Statement 解法 bit ごとに考えます。dp[day][index][bit] = (day 日目に, index 番目の部屋の duck の数について, bit 目の値が 1 になっている確率) とします。 例えば初日に duck の数が 5 だったら 0 bit 目と 2 bit…

問題 TopCoder Statistics - Problem Statement 解法 求める条件は, 「任意の p, q(>= 0) に対して, ある r, s(>= 0) が存在して, p*A + q*B = r*X+s*Y」が成り立つことですが, この条件と 「"ある r, s が存在して, A = r*X+s*Y" かつ "ある r, s が存在し…