問題 解法 解答 問題 https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_g 解法 「平均値の最大化」における一般的なテクとして二分探索がある．具体的には，求める最大の平均値を二分探索し，平均値 m が実現可能かどうかの判定は (各要素の値 - m) を…

問題 解法 解答 問題 https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_f 解法 前から要素を見ていく．a_i > 0 となっている要素があれば a_i, a_(i + 1), ... から 1, 4, ... を a_i 倍したものを引いていき，最終的に全ての要素が 0 になっているかど…

問題 解法 解答 問題 https://atcoder.jp/contests/agc035/tasks/agc035_c 解法 N = 2^k であるときは No．なぜならば，N - (2 * N) のパス間で k bit 目が 1 であるものはないため，xor を N にすることは不可能だから．そうでないときは全て Yes となる．…

問題 解法 解答 問題 https://atcoder.jp/contests/agc035/tasks/agc035_b 解法 まず，辺の数が奇数の時は答えは No になる．偶数の時は答えを構成することができる． 簡単な場合として根付き木を考える．このとき各頂点の出次数の偶奇は葉から各辺の向きを…

問題 解法 解答 問題 atcoder.jp 解法 i の偶奇で場合分けする． i が奇数の場合，サイコロの目として出てはいけない組み合わせ（禁止された組み合わせ）は (1, i - 1), (2, i - 2), ... となる．この組み合わせの個数を p とおき，これら 2 * p 個の数のう…

問題 解法 解答 問題 atcoder.jp 解法 まず，s[0] は必ず 1 で s[|s| - 1] は必ず 0 でなければならない．なぜなら，葉に繋がる辺を切れば必ず大きさ 1 の部分木が出来て，どこかの辺で切ったら木全体が２つに分けられるため大きさ |s| の部分木は出来ないか…

問題 解法 解答 問題 atcoder.jp 解法 dp(i, j) := 左から i 個のブロックまでの全てを爆破済みで，区間の右端が j になるような区間で爆破するときの通り数 と DP を立てる．j <= K のとき，爆破する区間を取ることが出来ないので dp(i, j) = dp(i, j + 1) …

問題 解法 解答 問題 atcoder.jp 解法 頂点をいくつかのグループに分けるとき，全てグループに含まれる頂点の数字の和が S になるように N 個の頂点をグループ分けし，それらのグループを互いに全て結べば答えが求められる．N が偶数の時，(1, N), (2, N - 1…

問題 解法 解答 問題 atcoder.jp 解法 dp(i) := i 個目の石までの塗り方の数 とする．このとき，i 個目の石と同じ色の石が j (j < i) 個目にあるとき，[j, i] の区間を i 個目の石の色で塗ることが可能．塗るときの塗り方の数は考えられる j について dp(j -…

問題 解法 解答 問題 beta.atcoder.jp 解法 0 ~ L - 1 の長さのパスを作りたいのだから，とりあえず長さ 2^0, 2^1, 2^2, ... , 2^20 の辺を張っておきたいと考える（2^20 までなのは，2^20 > 10^6 であるから）（log2(10^6) が大体 20 なので制約から察する…

問題 解法 解答 問題 D - Median of Medians 長さ N の数列 a の全ての連続する部分列の中央値を集めた数列の中央値を求める問題． 解法 以下の２つの条件を満たす x は数列の中央値になる： 数列の中に x 以上の要素が半分以上含まれる x は 1. を満たす整…