人権なし

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

AtCoder その他の問題

プログラミングバトル 本戦 - BCU30:B - Interval Addition

問題 解法 解答 問題 atcoder.jp 解法 広義単調増加となっている部分列の個数が答えになる.無駄に最初から全体に +min(A) してから・・・などと考えると反例が出てくるので注意する(1 WA した). 解答 atcoder.jp

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)…

Typical DP Contest:D - サイコロ

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

Typical DP Contest:C - トーナメント

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

Typical DP Contest:B - ゲーム

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

Typical DP Contest:A - コンテスト

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

AtCoder Regular Contest 033:D - 見たことのない多項式

問題 解法 解答 問題 D - 見たことのない多項式 N 次多項式 P(x) があり,P(0), P(1), ... , P(N) が分かっているとき,P(T) を求める問題. 解法 さっぱり分からないので解説を読んだところ,ラグランジュ補間というものを使うらしいと分かった.これは,P(…

AtCoder Regular Contest 032 : D - アットコーダーモンスターズ

問題 解法 解答 問題 D - アットコーダーモンスターズ N 匹のモンスターには攻撃値と防御値がそれぞれ決まっていて,この中から K 匹選んでチームを作りたい.このチームの「不安定度」はチーム内のモンスター同士の攻撃値の差と防御値の差の min の max で…

AtCoder Regular Contest 035:C - アットコーダー王国の交通事情

問題 解法 解答 問題 C - アットコーダー王国の交通事情 全ての頂点が連結であるグラフがあり,この全頂点間の最短距離の和を S とする.「頂点 X と Y の間にコスト Z の辺を追加」というクエリが K 回与えられるので,K 回それぞれに対して S を求める問題…

AtCoder Regular Contest 032:C - 仕事計画

問題 解法 解答 問題 C - 仕事計画 a_i と b_i を始点・終点とする区間が N 個あり,それらからいくつか両端以外で重ならないように選ぶとき,最大でいくつ選べるかを求め,辞書順最小の組み合わせを求める問題. 解法 区間をソートし,時間を後ろから見てい…