問題 解法 解答 問題 beta.atcoder.jp 解法 何回目に操作が終了するかで場合分けをする．k 回目に操作が終了する確率は (n / n) * ( ( n - 1 ) / n) * ( ( n - 2 ) / n) * ... * ( ( n - ( k - 2 ) ) / n) * ( ( k - 1 ) / n) になる．k 回目までのさいころ…

問題 解法 解答 問題 beta.atcoder.jp 解法 (x, y) の組をグラフ上の１つの頂点に対応させて考える．(x, y) に１回操作してなる数の組 (tx, ty) から (x, y) に辺を張る．そうすると，(x, 0) と (0, y) から到達できる組はいつか操作が終了する組だと分かる…

問題 解法 解答 問題 beta.atcoder.jp 解法 問題を読むと DP という気持ちになるので，以下のように DP を定義する： dp(i, f) := i 番目の要素まで見たときの最大値（f が true の時，効用を０にすることが可能で，f が false の時，効用を０に出来ない） f…

問題 解法 解答 問題 beta.atcoder.jp 解法 偶数行・列の長さの累積和と奇数行・列の長さの累積和の２つを計算しておく．そうすれば，各クエリにおいて座標が (偶数，偶数) と (奇数，奇数) の黒マスの面積の合計が O(1) で計算でき，この２つを足し合わせれ…

結果 A - Measure B - Exchange C - Align 結果 ３完（700 点・80:31），1389 位中 248 位，レート変動無し．途中参加になってしまったので Beginner の方に参加した．C 問題を一発 AC 出来たのはよかった． A - Measure beta.atcoder.jp B - Exchange beta.…

問題 解法 解答 問題 beta.atcoder.jp 解法 小さい数，大きい数，小さい数，... のように並べていくのが最適だと分かるので，隣り合う要素の差の合計の式を書くと， (a_2 - a_1) + (a_2 - a_1) + ... + (a_(n-1) - a_n) になる．ここで，両端の要素を除いた …

問題 解法 解答 問題 beta.atcoder.jp 解法 N 個の建物から K 個選び，それらを左から高さが増加していくようにすることを考える．制約より，選び方を bit 全探索する．i 番目の建物の前までの max を前計算で求めて置き，K 個選んだあとは，前計算の結果も…

問題 解法 解答 問題 beta.atcoder.jp 解法 好きな曲の BPM の範囲は，[140, 170), [280, 340), ... と両端の数値が２倍ずつ増えていき変化する．よって，BPM の範囲を全て列挙し，それぞれの範囲と [L, R) の共通範囲の個数を計算し，それらの和を求めれば…

問題 解法 解答 問題 beta.atcoder.jp 解法 ある連続する区間積が P になればよいので，この連続する区間が数列 A にあるかどうかを判定すればよい．尺取り法を使って考えると，区間積が P より大きくなったら左端を縮める，P より小さくなったら右端を伸ば…

問題 解法 解答 問題 beta.atcoder.jp 解法 まず，「よい文字列」が存在するときその長さは lcm(N, M) になるのは自明．なぜなら，lcm(N, M) の倍数で考えても見るべき X の場所の組は変わらないから． 長さを固定できたので，あとは構成した X が条件に当て…

問題 解法 解答 問題 beta.atcoder.jp 解法 「ゾンビ島」（ JOI 2015/2016 予選 問題５ ）にめちゃくちゃ似ている（というかほぼそのまま）． イノシシがいるマスから BFS で各マスのイノシシのいるマスまでの最短距離を調べる．ここで，最短距離が X 以下で…

問題 解法 解答 問題 beta.atcoder.jp 解法 １円，10 円，100 円の順番に分ける枚数を決めていく．この時，各硬貨の枚数が偶数になれば条件を満たす．ここで，各硬貨の枚数に mod 20 をとる．なぜならば，１つ上の硬貨に位上げしても，位上げの枚数は必ず偶…

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

問題 解法 解答 問題 beta.atcoder.jp 解法 まず，それぞれの到達させたい点と原点の距離の偶奇が一致することを確かめる．一致しなければ，どんなに頑張っても不可能． それぞれの到達させたい点と原点の距離の偶奇が一致するとき，ロボットの腕の長さを 2^…

問題 解法 解答 問題 beta.atcoder.jp 解法 奇数個のコインがあるマスから (1, 1) -> ... -> (1, W) -> (2, W) -> ... -> (2, 1) -> ... のように他の奇数個のコインがあるマスにコインを移していく．これをやると，最小でも HW - 1 個は偶数個にすることが…