テストケースを見ながらacceptした。 構造を見抜くだけでなく、条件を詰めてバグ無く実装仕切るのがむずかしい。気づき 減らせるだけ減らして、水を足す。 同じ状態になったらループするので成功。 たとえばk=100、y=3とする。 まず100-3-3...-3>lと3を引い…

全然わからなかった。 気づき suffixに操作を加えても一つ前の値との差は変わらない 一つ前の値と同じにすることだけ考えれば良い 操作はsuffix全体にたいしてインクリメント・デクリメントなので、A[0]の値に揃えるのが最善で、順番に揃えていくと、一つ前…

DP難しい。 全事象は塔を建てるか建てないかの2通りの組み合わせで、通り。このうち題意をみたす塔の立て方のパターン数の確率を求めれば良い。 良い塔の建て方は、奇数の和でNになる場合の数なので、これをDPで求めたい。 気づき 累積和＋DPは貰うDPのほう…

A. Add Candies A=[1,2,3,...,N]は図にすると階段状の三角形になるので、逆向きの三角形を足せば四角形になって、値が一致する（和の公式の考え方）。 よって、[N,N-1,..,1]を足せば良い。 B. Numbers Box 気づき マイナス記号を自由に移動できる 負 負 は正…

怒涛のギャグ問題回。 A. Specific Tastes of Andre ギャグ問題。 部分列の和が、長さで割り切れるといっているので、部分列の和と長さが等しければ常に条件を満たすことは自明。 よって全部を1にすれば、どの部分列をとっても、和と長さが等しくなる。 B. V…

解けなくはないけど、ややこしい。 問題を少し言い換えて、左からの減少列と右からの減少列（左から見れば増加列）の和で、与えられた数列をつくれるかを判断する。 気づき 左からの減少列をなるべく長く延したほうが得 証明はできなかったけど、小さい例で…

強いサンプルがあればともかく、なかなか本番で詰めきれる気がしない。 気づき 大きく分けて、プラスになる、0になる、マイナスになる、の三通りがある 丁寧に場合分けする。 とする。 プラスにできる => 負の数をi=0,2,4...ととったとき、 が成り立つ。 0に…

B. Reverse Binary Strings B問題がまったくわからず、ドツボにハマっていたアカウントがこちらです。 結局カンかつ未証明で通したけど、解説みるまでまったく見えてなかった。 たとえば「11101000」にたいして「10101010」あるいは「01010101」のどちらに変…

A. Boring Apartments 1,11,111,1111,2,22, ... , 9,99..,9999 を作って、何個目まで使えるか試せばOK B. Yet Another Bookshelf 右端からの0のエリアと左端からの0のエリアに移動するのは無駄。 右から最初の1と左から最初の1の間にある0を埋めるように移動…

A. Box is Pull ネズミの開始位置が任意なことに注意 B. Belted Rooms ちゃんと紙に書きましょう問題 '>'が0、または' そうでないなら、連続する'-'の個数。 場合分けと円環上で連続するアイテムを数えられるか問題。 C. ABBB ABを優先して消す。 解法。 答…

A. Three Indices jを固定して、条件をみたすi,kが存在するか探す。より二乗で間に合う。 B. Universal Solution ギャグ問題。 全部同じ手をだして、勝利を最大化すればOK。 ローテーションしていくからはのすべての手と一回戦うことになる。よって場所は関…

B. Barrels 最大量を増やせば良い。 一つでも移動すると、移動元は0になって、それが最小値になる。 よって大きい方から個の和。 C. Numbers on Whiteboard 足して2で割ったものを小さくしたいということは、足す2数を小さくしたい。 よって大きい数から消費…

C問題で限界。難しい。 気づき r（全体のマス）が小さい より有名人は同じ時間に登場しない＆単調増加。少なくとも1分離れている。 まず、典型的なDPで答えを求めることができる。 DPテーブルを、dp[i]をi番目までみたときの、写真を取れる有名人の数の最大…

なかなか計算が合わなかった。 気づき ある値が「何回数えられるか」を数える典型の考え方 この手の、問題は総和の順番を変えて、ある値が「何回数えられるか」に見方を変えるのが典型なので、その方向で考える。 入力を「abcd」とすると、たとえば「c」を削…

なんでこれが難しかったのかよくわからない。 3日くらい悩んでた。 気づき n,mの制約が小さい 座標もまででやや小さい 具体的に書いてみるとわかるが、階段状になるので範囲毎に値が決まってそうな気持ちになる。 で、まずは失敗解法を思いついた。 うまく行…

C. k-Amazing Numbers 添字と境界条件の扱いがめんどくさい問題。 気づき 範囲を全部試すのは無理 ある値を選んだとき、全体を覆うのに必要な最短の範囲を求めることができる fig.1 現れる数字は1からNまでしかないので、順番にどれだけの範囲があれば全体を…

AtCoder Beginner Contest 178 D問題 Redistribution 気づき 制約が小さい（） 長さが1のときは1通り modを取りながらの除算（逆元）とコンビネーションは持っている前提とする。 公式解説はDPなので、ここでは単純に高校数学範囲のでやる。 項の和がとなる…

Codeforces Round #670 (Div. 2) C. Link Cut Centroids どうやって証明ができるのかわからない。 気づき 問題文に不可能な場合がないので、連結成分の最大の最小は2以下らしい 2つの場合は連結成分の大きさが等しいので、どちらかから一つの頂点を引いて、…

Codeforces Round #669 (Div. 2) D. Discrete Centrifugal Jumps この問題難しくね？ ちょっと理解が足りてないのでふわっとした説明になってます。 気づき min max の要素数が小さいのなら場合分けをしてみる（今回は4パターン） 場合分けをすることで、イ…

Codeforces Round #668 (Div. 2) D. Tree Tag 気づき Aliceが一回の移動で木の全部に移動できるなら必勝 1.でないとき、Bobがaliceの2倍より大きく動けるなら必勝 1.については、は具体的にいくつか書いてみれば気づくと思う。 問題は、一回で全域をカバーで…

Codeforces Round #668 (Div. 2) C. Balanced Bitstring 気づき インデックス mod K で一致する 範囲内で片方がより多く存在したら不適 1.について 問題を眺めていても閃かないので、この手の問題の常套手段をまず確認する。 具体的に手を動かす 抽象的に手…

Codeforces Round #666 (Div. 2) D. Stoned Game 問題文を眺めてても見えてこないので、まずは極端な状態を考える。 山がn個あって、それぞれに一つずつ石が置いてある 山がn個あって、n-1個には一つずつ石があり、一つの山に大量の石が置いてある 1.につい…

Codeforces Round #666 (Div. 2) C. Multiples of Length長さ（）の配列（）が与えられる。 操作を3回行って、全ての要素を0にせよ。 気づき 任意の長さの配列を3回の操作ですべてにできることが証明できると書いてあるので、選択肢は多くない。 選択した範…

Educational Codeforces Round 94 (Rated for Div. 2) D. Zigzags かつ 気づき 制約からは良さそう 2つの位置を動かして二重ループで解ける？ とを固定してもうまく行かない とを固定すればよさそう！（ここが重要） とを固定（つまり2重ループでとの組み合…