めちゃくちゃ苦労したけど、コンテスト外でやっと解けたので記録してくおく。 最初に考えたこと。 差分計算したい。 更新時に未使用の色のうち、インデックスが一番小さいものを採用すればよさそう。 ある色が採用されたとき、いくつのボールが利用されるか…

解説をよんで最初分からなかった部分が腹落ちしたので書いておく。 疑問に感じたのは、途中で使ったボールの操作を打ち消すのに、最新の状態のDPテーブルへの操作で良い理由。 合計K以上のDPテーブルを持たなくて良い理由の部分。 の2点。 直感的にはボール…

公式解説の通りです。 実装の方針だけ。 任意の頂点pを選んで2回操作した場合もとに戻る 操作の順番が違っても結果は同じ 任意の頂点pだけを反転するには、頂点pにたいして操作をして、頂点pの子に操作する（戻す操作）で可能 以上により必要な操作の最小回…

AtCoder ARC127 A. Leading 1s 地獄のような桁dpを書いた。 dp[i桁目][先頭から連続して使用した1の個数][1が連続しているか][未満フラグ] として、遷移はnext = 0から9 leading zeros に注意（nextが1の時だけ初期状態に+1）。 dpの結果（場合の数）にたい…

にたいしてを最大値として採用できるように、かつをできるだけ小さくするを求めて、これらの最小値が答え。 どうやって計算するか。 2進数で考える。 より30桁考えれば良い。上の桁から決めていきたいので、以下では左から0,1,2..桁目と数えることとする。 …

グラフを作ってからメモ化再帰で答えをもとめる。 数字が大きいところにしか辺を貼れないので、グラフはDAGになる。 あるマスから行または列の、自分の次に数が大きいマス（複数ありうる）に辺を貼る。 「自分の次に数が大きいマス」にだけ辺を貼れば良い。…

kyopro_friendsさんの公式の解説の通り。 解説動画がくれば詳しく解説してくれそうだけど、実装に時間がかかったので残しておく。 dp[i][j] = i番目の試合でj番目の選手が勝ったときの、得られるポイントの最大値とする。 遷移はdp[i+1][j] = (i+1)番目の試…

NOMURA プログラミングコンテスト2022（AtCoder Beginner Contest 253） F問題 Operations on a Matrix 状態が多くて脳が破壊された。 だいたいの情報は両端キューで管理して適宜pop_front()するとすこし楽になる。 まずタイプ1(l,r,x)のクエリによってj列目…

公式解説が丁寧だけど、累積和の理解に時間がかかったのでメモしておく。 公式とは少し違うみたい。 距離D毎に射る。座標0付近を中心に左右にほぼ均等に割り振る。中心を0から距離Dより離す必要はない。 よって中心を0からDまで試せば良い。 （ここまで公式…

全体を回転しながら、上となる辺を数えた。 全体を回転させて同じ処理を4回行うっていうのは、過去のABCの解説動画にもあった方法。 fig.1この方法でAC。 公式解説の4マスを調べる方法がよくわからなかった。 マスに注目しているというより、多角形の頂点と…

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

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