とりあえず考えること 要素/総和のmod/パリティに注目する 操作回数を求めることができるか(特に総和を用いて) 逆操作が可能か 操作が単純な操作に分解できるか 階差数列を考える 数列2つを一致させるなら差を取る 操作の縮約ができないか/周期を持たないか …

問題 解法 K個以上の区間は消せる Greedyは厳しそう dp[i] := (最後に[i,i+K) を消したときのmax ) とすると..? dp[i+1] = max_{ j, [i,i+K) と [j,j+K) の区間が被っている } ( dp[j] + sum_b [j+K, i+K) ) と, dp[i+1] = max_{ j, [j,j+K) の区間は [i,i+K…

問題 解法 考察 XOR swapによりswapが可能( a ^= b, b ^= a ) これによってa_i, a_j (i!=j) で操作ができる あるbitだけ立っている要素があればそれを使ってそのbitを自由に立たせることが可能 そのような要素は {1101, 1001} のような1bitだけ異なる数があ…

問題 問題概要 N個の整数からなる数列が与えられる. x,yについて,a[y]にa[x]を足す,という操作を繰り返して, a[0] <= a[1] <= ... <= a[N] を満たすようにしたい. 条件を満たす2N回以内の操作を出力せよ. そのような操作が存在することは保証されている. 2 <…