Educational Codeforces Round 69 D. Yet Another Subarray Problem

お題箱より。

問題概要

※解説の都合上、0-indexedと半開区間での記述に書き換えます。

非負とは限らない整数列 $a_{0}, ..., a_{n-1}$ と、正整数 $m, k$ が与えられる。

この数列の連続部分列 $a_{l}, ..., a_{r-1}$ について、そのスコアを $\sum_{i=l}^{r-1}a_{i} - k\lceil \frac{r-l}{m}\rceil$ と定める。ただし長さ0の連続部分列のスコアは0とする。

スコアの最大値を求めよ。

制約

$1 \le n \le 3\times 10^{5}$
$1 \le m \le 10$
$1 \le k \le 10^{9}$
$-10^{9} \le a_{i} \le 10^{9}$

解法

連続部分列の和（区間和）は、累積和を取ってその差を考えるのが鉄則です。以下のように要素の「区切り位置」と累積和を対応させ、区間を半開区間として捉えると、累積和の差と区間和がキレイに対応します。

f:id:betrue12:20191123015831p:plain

もしスコア計算に $-k\lceil \frac{r-l}{m}\rceil$ の項がなければ、この問題は以下のように解けます。

累積和 $S_{i}$ を計算する。
各位置を左から見ていきながら「その位置が右端 $r$ となるような区間和の最大値」を求める。これは具体的には、これまで見てきた累積和（ $S_{r}$ も含む）のうち最も小さいものを $S_{l}$ として $S_{r} - S_{l}$ で計算できる。
これらの最大値が区間和の最大値である。

$-k\lceil \frac{r-l}{m}\rceil$ の項がある場合も、このやり方を応用して解けます。この項は区間の長さが長いほどスコアにペナルティが付くことを意味しています。具体的には長さを1ずつ大きくしていくと、 $1, m+1, 2m+1, ...$ に到達するたびにスコアが $k$ 減ることになります。

直感的には、位置が遠い累積和ほどそこを左端として選んだときのスコアが減るように補正を掛けたいです。左端の累積和はスコアにマイナスで入るので、それぞれの累積和からの距離が $1, m+1, 2m+1, ...$ に到達するたびに $k$ 足すようにすると辻褄が合います。

f:id:betrue12:20191123025347p:plain

ではこれらの累積和をどのように管理するのが良いでしょうか？右端の位置を進めるごとに「補正後の」累積和の値は変わっていくため、単純に最小値だけを持つのは上手くいきません。とはいえ全ての累積和を持って、それぞれについて補正を増やしたり毎回最小値を取っていると間に合いません。

今回は $m$ が小さいことに注目して、 $i$ を $m$ で割った余りごとに $S_{i}$ を分類しましょう。見ていく右端の位置を進めていくとき、 $m$ で割った余りが等しい $S_{i}$ 達には同じタイミングで $k$ が足されます。つまりこれらについては $\min(S_{i}+k, S_{i-m}+2k, S_{i-2m}+3k, ...)$ という風に、補正差を考慮した最小値を1つだけ覚えておけば良いです。