ABC288D 別解法メモ - こゃーその雑記

前書き

なるべく愚直な操作でなんとかする解法です。（実質的には同じかもしれませんが、）mod $K$ での累積和を使っていません。

コンテスト中、解法が思いつかずになんとかして無理やり解く方法を考えたもので、綺麗な解法ではないです。

公式解説を読むほうが勉強になると思います。

問題

atcoder.jp

考え方

$l_i=1$ であれば、左から順に可能な限り0にしていき、0にできない残り $K-1$ 個が0になっているかを確かめればよい
$l_i \ne 1$ であるときは、一旦左から順に0にしていったあと、左から 元の数列の値に戻していく ことを考えていく
すると、 $l_i$ から $K-1$ 個については、0ではない値になる

「左から0にする」操作のあと、「左から元の数列に戻す」ということをすると、0で初期化された長さ $r - l + 1$ の数列に範囲の右から $K - 1$ 個の値と左から $K-1$ 個の値をそれぞれ足した数列ができる
範囲の長さが以上のとき:
- 範囲左右端の値の間は、 $r - l + 1 - 2 (K - 1) = r - l - 2K + 3$ 個の0で埋められることになる
- ここで、 $0, \dots, 0, a$ (0はK個)は、操作で $a, 0, \dots, 0$ にすることができる*1
- つまり、 $r - l - 2K + 3$ 個の0は、 $(r - l + 3) \% K$ 個でも同じになるため、最終的にできる数列の長さは $3(K-1)$ 以下にできる
あとは、できた数列に対して愚直に操作を実行して、すべて0にできるか確かめればよい
計算量について:
- 範囲の両端の $K-1$ 個の値の事前計算: $\mathcal{O}(NK)$
- 愚直に作った数列が0にできるか確かめる計算量: $\mathcal{O}(K^2)$
- よって、全体で $\mathcal{O}(K(N + QK))$ で解ける

AC提出

atcoder.jp

なお、

D問題、あまりにも頻出・有名過ぎるのでDに置かれてる系だと思うので、知らん人が初見で解けないのは仕方ない気はする。
— chokudai(高橋直大)🐙🔥@AtCoder社長 (@chokudai) 2023年2月4日

https://

あ、一応。典型の考え方も含めて。「この問題そのものが有名」という話ではない。
・区間に足し引きする問題は、imos法の逆の考え方で、始点・終点に足し引きする問題に変換できる
・足す区間が一定（長さK）の場合は、modKが同じ場所しか互いに影響を与えないので独立で考えられる
の2つが典型
— chokudai(高橋直大)🐙🔥@AtCoder社長 (@chokudai) 2023年2月4日

ということだそうなので、こちらの考え方を持っておいたほうが活かせる気がしています。

https://twitter.com/chokudai/status/1621872224465727489?s=20&t=rGTI6O6y-GB3eZShdcJysg

*1:本当はもっと強い主張ができる（公式解説参照）。なぜこれがわかったのに、解説のやり方が思いつかなかったのか……