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}まず $D_1=0$ として順に値を決めると、
$$
(D_1,D_2,D_3)=(0,5,7)
$$
となる。
このときの操作回数は $0+5+7=12$ 回である。
0-indexed で添字が奇数の値と偶数の値を分けると、次のようになる。
odd: {5}
even: {0, 7}どちらも既に昇順である。
次に、いずれかの $D_i$ が $0$ になる場合だけを調べる。
$D_2=5$ を $0$ にする場合、反対側の even では
$10-5=5$ 以上の値が $1$ 個ある。
この場合、元の $12$ 回から $5$ 回節約できる。
実際、操作回数は
$$
(D_1,D_2,D_3)=(5,0,2)
$$
となり、合計は $7$ 回である。
$D_1=0$ の場合は最初の状態そのもので、節約できる回数は $0$ 回である。
$D_3=7$ を $0$ にする場合、反対側の odd では
$10-7=3$ 以上の値が $1$ 個ある。
この場合、$7$ 回節約できる。
実際、操作回数は
$$
(D_1,D_2,D_3)=(3,2,0)
$$
となり、合計は $5$ 回である。
最大で $7$ 回節約できるので、答えは $12-7=5$ となる。
注意点
答えは、int 型からはみ出る。
long long 型を用いること。
$D_i$ を求める部分も、$10^9$ 級の数を $3$ つ以上加減算するので注意。
別解
特になし。