ARC128-Dを解いた 問題 数列が与えられる。を満たすを削除する操作を好きなだけ行う。最終的なの数mod998244353を求める。 解法 まず、2つ以上同じ数が連続している部分について考える。ここに含まれる数は絶対に削除できない。 以後2つ以上連続している部分…

ARC168-Dを解いた 問題 個の白いマス目と個の操作が与えられる。個目の操作では、を満たすマス目を黒く塗る。ここで、操作前よりも操作後のほうが黒いマスが多くないといけない。最大操作回数は? 解法 区間]だけ考えた時の最大操作回数 としてDPする。とを合…

ARC136-Cを解いた 問題 円環状で要素がすべての数列の連続部分列にを加算する操作を何回か行う。所望の数列に一致させる最小操作回数は何回? 解法 から減算を繰り返して数列の要素をすべてにすることを考える。 、 (はとして) 、と置く。減算する区間の端に…

AGC054-Cを解いた 問題 順列について、隣接swapで各について自分より前のであるの数を以下に抑えたい。操作回数はなるべく小さく。操作後のはになる。元のとして考えられる順列の数をで求める。 解法(自分の) としてふさわしいものを考えると、以上以下の数…

AGC053-Bを解いた 問題 長さが偶数の非負整数列が与えられる。先手がから一つ選び、後手はの中央のindexの値を選ぶ。先手が選んだ要素の和を最大化する。 解法 、とする。先手はどちらかの数列の要素を一つ選び、後手は先手が選ばなかった方の数列の先頭を選…

ARC127-Dを解いた 問題 非負正整数列が与えられる。を求める。 解法 として、上位bitから見ていく。bit目を見た時にのbit目とのbit目が異なる整数組はとのどちらが小さいか定まる。等しい組に関しては、再帰的にbit目を見ていく。 考察 上位bitから見ていく…

ARC140-Dを解いた 問題 数列が与えられる間に辺を張っていく。の時はは自由に決めていい。あり得るすべてのグラフの連結成分数の総和を求める。 解法 であるについて先に辺を張ってみる。すると連結成分は全てなもりグラフか木。なもりグラフの連結成分には…