ABC467 E - Adjacent Sums (hard)

考え方

C問題の、$M$ の範囲拡大版。

各数に何回操作を行うかは $0,1,\dots M-1$ の $M$ 通りだけ考えればよい。
$M$ 回以上行うのは $M$ で割った余りに影響がないまま無意味に操作回数を増やしているだけである。
よって、全体で $M^N$ 通りのパターンを考えることになるが、これを全探索するのは間に合わない。
そこで、高速化を考える。

例えば、先頭の $A_1$ には操作を $D_1$ 回、次の $A_2$ には操作を $D_2$ 回行うとする。
このとき、$A_1+D_1+A_2+D_2$ を $M$ で割った余りが $B_1$ でなければならない。
つまり、$D_2$ は $B_1-A_1-D_1-A_2$ を $M$ で割った余りになっていなければならないのである。
（C++の場合、負数の剰余の仕様が単純な $\bmod$ 演算になっていないため、実装時に注意）
このように考えると、実は $D_1$ を決めた時点で $D_2$ にはすでに選択の余地がない。

この先も、$D_2$ を決めた時点で $D_3$ にはすでに選択の余地がなく、以下すべて同様。
つまり、全探索の自由度は $D_1$ を $0,1,\dots M-1$ のどれにするかの $M$ 通りしかない。

ということで、まずは $D_1=0$ の方がこの方法で $O(N)$ で調査できる。
ここまではC問題とほぼ同じ発想である。

$D_1$ を $M$ パターン全て試すのは、計算量 $O(MN)$ になる。
これがC問題では $M=2$ なので間に合ったが、E問題では間に合わないというのが相違点である。
そこで、さらなる高速化を考える。

まず、全ての数に $1$ 回以上操作を行うものは、貪欲法により探索を省略できる。
というのは、$D$ の偶数番目と奇数番目を交互に $1$ 回増減した解で代替できるため。
全体の長さが偶数ならどちらを $+1$ しても回数は悪化せず、奇数なら $-1$ を $1$ つ多くする。
その変換を初めてどこかに $0$ が出現するまで繰り返すと、上位互換（悪くても同等）解が得られる。

これにより、$M$ パターン全て試さなくても、$D$ のいずれかの数が $0$ になる $N$ 通りだけ試せばよくなった。
（もう少し考えると、実は奇数番目が $0$ になるパターンだけでよく、半分に減らすこともできる）
しかし、これでもまだ計算量は $O(N^2)$ でまだ間に合わない。

だが、ここから $D_1=0$ のときの解を使ってさらに高速化できる。
というのは、同様に偶数番目奇数番目交互に値を足し引きする上での変化は簡単に求められるため。
$D_1=0$ のときの解の偶数番目の数、奇数番目の数をわけてソートして保持しておく。
片方を $K$ ずつ減らしたときに負数になる個数は、今 $0$ にしようとしている数が何番目にあるかでわかる。
逆を $K$ ずつ増やしたときに $M$ 以上になる数は、二分探索かツーポインタ法でわかる。

これで、どれかが $0$ になる全 $N$ パターンを調査しても間に合うようになる。
計算量はソート部分が支配的で、$O(N \log N)$。

入力例1での動作

入力を受け取る。

n: 3
m: 10
a: {4, 6, 7}
b: {5, 5}

先頭の値に $1$ すら足さない場合に、各値へ何回足すかを記録する配列 d を、すべて $0$ で初期化する。

d の奇数番目の要素を記録する odd は空、偶数番目の even には d[0] の値 $0$ を入れておく。

d: {0, 0, 0}
odd: {}
even: {0}

$i=1$ のとき、b[0]-a[1]-a[0]-d[0] の値は $5-6-4-0=-5$ である。

これを $m=10$ で割った余りは $5$ なので、d[1]=5 とする。

$i$ は奇数なので、d[1] を odd に加える。

d: {0, 5, 0}
odd: {5}
even: {0}

$i=2$ のとき、b[1]-a[2]-a[1]-d[1] の値は $5-7-6-5=-13$ である。

これを $m=10$ で割った余りは $7$ なので、d[2]=7 とする。

$i$ は偶数なので、d[2] を even に加える。

d: {0, 5, 7}
odd: {5}
even: {0, 7}

d の要素の合計を result に入れておく。

result: 12

odd と even をそれぞれソートする。

odd: {5}
even: {0, 7}

節約できる操作回数の最大値 dec を $0$ で初期化する。

dec: 0

odd[0]=5 を $0$ に変える場合を調べる。

even には m-odd[0]=5 以上の要素が $1$ 個ある。

節約できる操作回数は、$(1-0)\times10+5\times(1-2)=5$ となる。

dec を最大値更新する。

dec: 5

even[0]=0 を $0$ に変える場合を調べる。

odd には m-even[0]=10 以上の要素がない。

節約できる操作回数は、$(0-0)\times10+0\times(2-1)=0$ となる。

dec は変更しない。

dec: 5

even[1]=7 を $0$ に変える場合を調べる。

odd には m-even[1]=3 以上の要素が $1$ 個ある。

節約できる操作回数は、$(1-1)\times10+7\times(2-1)=7$ となる。

dec を最大値更新する。

dec: 7

result から実際に dec を引けば答え。

result: 5

注意点

答えは、int 型からはみ出る。
long long 型を用いること。
$D_i$ を求める部分も、$10^9$ 級の数を $3$ つ以上加減算するので注意。

別解

特になし。