AtCoder その他の問題
問題 解法 解答 問題 https://atcoder.jp/contests/ttpc2019/tasks/ttpc2019_d 解法 各 X_i は何回か (0 回かもしれない) 2 個ずつ取ることができる．X_i を最大何回まで 2 ずつ引いていくことができるかをまず調べる．この回数 + 1 だけ各山に石があると問…
問題 解法 解答 問題 https://atcoder.jp/contests/ttpc2019/tasks/ttpc2019_c 解法 -1 でない a_i の xor を t，-1 である a_i の個数を cnt とすると，0 以上 X 以下の数 cnt 個の xor が X^t となればよい．これは X^t が X * 2 以上であるときは構成でき…
問題 解法 解答 問題 https://atcoder.jp/contests/otemae2019/tasks/otemae2019_g 解法 N が大きいので，P, Q, R, S, A_i, B_i, C_i, D_i を x, y 座標に分けて座標圧縮をする．また，上下・左右方向にワープ可能な領域をそれぞれ累積和で求めておく．この…
問題 解法 解答 問題 https://atcoder.jp/contests/otemae2019/tasks/otemae2019_f 解法 以下の DP を考える． dp(i, j) := i 日目で右側に j 枚コインがあるとき，i + 1 日目以降のコストの和の最小値 遷移は，右側にのせるコインは j 枚のまま次の日にいく…
問題 解法 解答 問題 https://atcoder.jp/contests/otemae2019/tasks/otemae2019_e 解法 参加者 i は (D_1 - 1) + (D_2 - 1) + ... + (D_i - 1) 秒後に動き始める．これを t_i とおく．なので，参加者 i が座標 1 に到達するのは t_i + (1 + i) 秒後になる．…
問題 解法 解答 問題 https://atcoder.jp/contests/otemae2019/tasks/otemae2019_d 解法 以下の DP を考える． dp(i, j, k) := 上から i 桁目まで決めて，今まで j 回発言し，上から i 桁目までの整数を 3 で割った余りが k であるときの，i + 1 桁目以降の…
問題 解法 解答 問題 https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_a 解法 まず y 座標は 0 以上で偶数でなければならない．ここが一番引っかかるポイントだと思う． y 方向に + の方向にしか移動できないので，移動回数 t が求まる．この移動回数…
問題 解法 解答 問題 atcoder.jp 解法 広義単調増加となっている部分列の個数が答えになる．無駄に最初から全体に +min(A) してから・・・などと考えると反例が出てくるので注意する（1 WA した）． 解答 atcoder.jp
問題 解法 解答 問題 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)…
問題 解法 解答 問題 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)． 解答…
問題 解法 解答 問題 D - 見たことのない多項式 N 次多項式 P(x) があり，P(0), P(1), ... , P(N) が分かっているとき，P(T) を求める問題． 解法 さっぱり分からないので解説を読んだところ，ラグランジュ補間というものを使うらしいと分かった．これは，P(…
問題 解法 解答 問題 D - アットコーダーモンスターズ N 匹のモンスターには攻撃値と防御値がそれぞれ決まっていて，この中から K 匹選んでチームを作りたい．このチームの「不安定度」はチーム内のモンスター同士の攻撃値の差と防御値の差の min の max で…
問題 解法 解答 問題 C - アットコーダー王国の交通事情 全ての頂点が連結であるグラフがあり，この全頂点間の最短距離の和を S とする．「頂点 X と Y の間にコスト Z の辺を追加」というクエリが K 回与えられるので，K 回それぞれに対して S を求める問題…
問題 解法 解答 問題 C - 仕事計画 a_i と b_i を始点・終点とする区間が N 個あり，それらからいくつか両端以外で重ならないように選ぶとき，最大でいくつ選べるかを求め，辞書順最小の組み合わせを求める問題． 解法 区間をソートし，時間を後ろから見てい…
