考え方 回答例 考え方最小値の最大値なので，二分探索を考える．すべての要素を$x$以上にできるかは， $x + b$以上の要素から$b$減らせる操作回数 $x$未満の要素から$a$増やさなければならない操作回数 の2つを比較することで判定できる．回答例 N, a, b = m…

考え方 回答例 考え方逆順に操作していって$A$を空の数列にまで戻せるかを確かめる．flip回数の偶奇性を記録しておき，「操作Bを逆順に（できるだけ）行う→操作Aを逆順に行う」を繰り返す．flip回数が奇数なら0を1で置き換えて考えれば良い．操作Bを逆順に（…

解法1 考え方 回答例 解法1考え方$S_{1} = [A_{1},...,A_{K}]$と$S_{2} = [A_{K + 1},...,A_{N}]$の中から1つずつ$A_{i} $S_{2}$を前から見ていって，$A_{i - 1} > A_{i}$となる$i$があれば，$A_{i}$を$A_{i - 1}$で置き換える．こうしてできた配列を$S_{2}^…

考え方 回答例 考え方部分列の中含まれる「(1の数) - (0の数)」のパターンが何通りあるか，という問題．累積和のパターンが何通りあるかを考えれば良さそうだが，1の数が変化しても，0の数が変化しても累積和が変化してほしい．そこで，0を-1で置き換えて累…

考え方 回答例 考え方「$y-x$を大きい方から順に調べて，初めて$\gcd(x,y) = 1$となるものを出力すれば，制限時間内に止まるだろう」という方針でうまくいく．コンテスト中に計算量まで考えるのはなかなか大変． Editorial - AtCoder Regular Contest 137回…

考え方 回答例 考え方\begin{aligned} \Biggl|\frac{B_{i}}{M} - \frac{A_{i}}{N} \Biggr| = \frac{1}{MN} | N B_{i} - M A_{i}| \end{aligned}であるから，$| N B_{i} - M A_{i}|$を最小化すれば良い．そこで，はじめに\begin{aligned} B_{i} = \biggl\lflo…

考え方入力例1の3番目をもとに考察するとよい（具体例大事！）．$R \leq B$とする（例は既にそうなっている）．以下の手順で全てGに変えることができる． R G B 1 2 4 3 1 3 2 3 2 1 5 1 0 7 0つまり，すべてGにしたければ，RとBを同じ個数に調整できればよ…

B - アリの高橋くん 考えたこともっと簡単な方法があるんだろうな，とは思いつつも，計算で解が出せるので解いてしまった．現在地$(x_{0}, y_{0})$を中心とする円で各辺に接するものの半径を求め，それらのうちの最小値が答えになる．隣り合う頂点の座標を$(…

D - Card Eater考えたこと同じカードが3枚以上あれば，そのカードを3枚選ぶことで，2枚ずつ減らせる．この操作を繰り返せば，同じカードは2枚以下にできる．よって，すべてのカードは1枚 or 2枚であるとして良い（※ 1枚になるのは同じカードが奇数枚あったと…

Aだけ解けました．Bまでは解けるべきでした． A - God Sequence B - ARC Wrecker C - Tricolor Pyramid D - Miracle Tree E - Zero-Sum Ranges 2 F - Gateau A - God Sequence$A$個の正整数の数列を$1,2,3,...$とつくり，$B$個の負整数の数列を$-1,-2,-3,...…