人権なし

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

AtCoder 700 点問題

技術室奥プログラミングコンテスト#4 Day2:G - 平均レーティング

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

技術室奥プログラミングコンテスト#4 Day2:F - Segtree☆Magica

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

AtCoder Grand Contest 035:C - Skolem XOR Tree

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

AtCoder Grand Contest 035:B - Even Degrees

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

AtCoder Regular Contest 102:E - Stop. Otherwise...

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

AtCoder Regular Contest 103:E - Tr/ee

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

全国統一プログラミング王決定戦本戦:E - Erasure

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

AtCoder Grand Contest 032:B - Balanced Neighbors

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

AtCoder Grand Contest 031:B - Reversi

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

AtCoder Regular Contest 102:D - All Your Paths are Different Lengths

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

AtCoder Regular Contest 101:D - Median of Medians

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