結果 A - Frog 1 B - Frog 2 C - Vacation D - Knapsack 1 E - Knapsack 2 G - Longest Path H - Grid 1 I - Coins K - Stones L - Deque M - Candies P - Independent Set 結果 26 問中 12 問正解（1200 / 2600 点, 216:15），1124 位中 252 位．AC した問…

問題 解法 解答 問題 atcoder.jp 解法 dp(i, f) := 頂点 i を黒で塗れるかどうかが f のとき，頂点 i から到達できる頂点を塗り分ける通り数 と定義する．このとき， dp(i, f) = dp(v_1, true) * dp(v_2, true) * ... (f == false のとき) dp(i, f) = dp(v_1…

問題 解法 解答 問題 atcoder.jp 解法 dp(i, j) := i 人目までで j 個分けるときの通り数 と定義する．このとき， dp(i, j) = dp(i - 1, j) + dp(i - 1, j - 1) + ... + dp(i - 1, j - a_(i - 1)) dp(i, j) = 1 (j == 0 のとき) dp(i, j) = 0 (j < 0, i == 0…

問題 解法 解答 問題 atcoder.jp 解法 dp(i, j, k) := 数列 a_i ~ a_j の中で k が操作するときの (X, Y) の値 と定義する．このとき， dp(i, j, k) = ( dp(i + 1, j, (k + 1) % 2).X + a_i, dp(i + 1, j, (k + 1) % 2).Y ) か ( dp(i, j - 1, (k + 1) % 2).…

問題 解法 解答 問題 atcoder.jp 解法 dp(i, j) := 石が i 個あり操作するのが j のとき，j が勝てるかどうか と定義する．このとき，残りの石の状態のうちどれかが相手を負けにすることが出来るならば，自分を勝ちにできることを踏まえると， dp(i, j) = !d…

問題 解法 解答 問題 atcoder.jp 解法 dp(i, j) := i 枚目まで操作し j 枚表のときの，表が裏より多くなる確率 と定義する．このとき， dp(i, j) = dp(i - 1, j + 1) * p_(i - 1) + dp(i - 1, j) * (1 - p_(i - 1)) と漸化式が立つ．状態数 O(N^2)，遷移 O(1…

問題 解法 解答 問題 atcoder.jp 解法 dp(i, j) := マス (i, j) に到達するまでの経路数 と定義する．このとき， dp(i, j) = 1 (i == 1 かつ j == 1 のとき) dp(i, j) = dp(i - 1, j) + dp(i, j - 1) (それ以外のとき) と漸化式が立つ．状態数 O(HW)，遷移 O…

問題 解法 解答 問題 atcoder.jp 解法 dp(i) := 頂点 i から始まるパスで最長のものの長さ と定義する．このとき， dp(i) = max( dp(v) + 1 ) (v は頂点 i から到達できる任意の頂点) と漸化式が立つ．答えは dp(i) (1 <= i <= N) の最大値．状態数 O(N)，遷…

問題 解法 解答 問題 atcoder.jp 解法 dp(i, j) := i 番目のものまでで価値 j のときの重さの最小値 と定義する．このとき， dp(i, j) = inf (j < 0 のとき) dp(i, j) = 0 (j == 0 のとき) min( dp(i - 1, j) , dp(i - 1, j - v_(i - 1)) + w_(i - 1) ) (そ…

問題 解法 解答 問題 atcoder.jp 解法 dp(i, j) := i 番目のものまでで重さ j のときの価値の最大値 と定義する．このとき， dp(i, j) = max( dp(i - 1, j) , dp(i - 1, j - w_(i - 1)) + v_(i - 1) ) と漸化式が立つ．状態数 O(NW)，遷移 O(1) となり O(NW)…

問題 解法 解答 問題 atcoder.jp 解法 dp(i, j) := i - 1 日目に j を選んだ時の i 日目までの幸福度の和の最大 と定義する．このとき， dp(i, j) = max( dp(i - 1, 0) + a_(i - 1) (j != 0 のとき), dp(i - 1, 1) + b_(i - 1) (j != 1 のとき), dp(i - 1, 2…

問題 解法 解答 問題 atcoder.jp 解法 dp(i) := 足場 i に行くまでにかかるコストの最小値 と定義する．このとき， dp(i) = min( dp(i - j) + | h_i - h_(i - j) | ) (1 <= j <= K) と漸化式が立つ．状態数 O(N)，遷移 O(K) となり O(NK)． 解答 atcoder.jp

問題 解法 解答 問題 atcoder.jp 解法 dp(i) := 足場 i に行くまでにかかるコストの最小値 と定義する．このとき， dp(i) = min( dp(i - 1) + | h_i - h_(i - 1) |, dp(i - 2) + | h_i - h_(i - 2) | ) と漸化式が立つ．状態数 O(N)，遷移 O(1) となり O(N)…

結果 A - Gennady and a Card Game B - Petr and a Combination Lock C - Yuhao and a Parenthesis 結果 ８問中３問正解（2670点），7762 位中 2235 位，新レート 1480 (+61, Highest)．レート最高を更新出来たのでよかった．B ~ C 問題で WA を何回か出して…

問題 解法 解答 問題 codeforces.com 解法 各括弧列について，( と ) のどちらがどれだけ不足しているのかを調べる．もし，両方不足している括弧列は他のどの括弧列ともペアになれないので考えない．それ以外の括弧列の中で ( の不足分と ) の余剰分が一致す…

問題 解法 解答 問題 codeforces.com 解法 n <= 15 と小さいので，回すそれぞれの動作を時計回りか反時計回りのどちらにするかを全通り試す．針が 0 度のところに戻るかどうかは O(n) で判定できるので，O(2^n * n)． 解答 codeforces.com 360 で mod を取る…

問題 解法 解答 問題 codeforces.com 解法 問題文の通りに判定すればよい．O(1)． 解答 codeforces.com