人権なし

競プロで解いた問題や開発の進捗などの記録です

2019-01-07から1日間の記事一覧

Educational DP Contest / DP まとめコンテスト

結果 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 した問…

Educational DP Contest:P - Independent Set

問題 解法 解答 問題 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…

Educational DP Contest:M - Candies

問題 解法 解答 問題 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…

Educational DP Contest:L - Deque

問題 解法 解答 問題 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).…

Educational DP Contest:K - Stones

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

Educational DP Contest:I - Coins

問題 解法 解答 問題 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…

Educational DP Contest:H - Grid 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…

Educational DP Contest:G - Longest Path

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

Educational DP Contest:E - Knapsack 2

問題 解法 解答 問題 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) ) (そ…

Educational DP Contest:D - Knapsack 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)…

Educational DP Contest:C - Vacation

問題 解法 解答 問題 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…

Educational DP Contest:B - Frog 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

Educational DP Contest:A - Frog 1

問題 解法 解答 問題 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)…

Hello 2019

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

Hello 2019:C - Yuhao and a Parenthesis

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

Hello 2019:B - Petr and a Combination Lock

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

Hello 2019:A - Gennady and a Card Game

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