ABC467 C - Adjacent Sums (easy)
隣接和（易）
考え方
まず、前提として。
E問題と $M$ の制約が違うだけで、しかも $M=2$ のときだけ特殊な対応が必要になるわけでもない。
よって、E問題が解ける人は、あちらを解いて、そのコードをそのままC問題にも投げるだけである。
以下は、E問題は見なかったことにしてまずは $M=2$ 固定で解こうとする人用の解説。
各数に何回操作を行うかは $0$ か $1$ の $2$ 通りだけ考えればよい。
$2$ 回以上行うのは $2$ で割った余りに影響がないまま無意味に操作回数を増やしているだけである。
よって、全体で $2^N$ 通りのパターンを考えることになるが、これを全探索するのは間に合わない。
そこで、高速化を考える。
例えば、先頭の $A_1$ には操作を $D_1$ 回、次の $A_2$ には操作を $D_2$ 回行うとする。
このとき、$A_1+D_1+A_2+D_2$ を $2$ で割った余りが $B_1$ でなければならない。
つまり、$D_2$ は $B_1-A_1-D_1-A_2$ を $2$ で割った余りになっていなければならないのである。
（C++の場合、負数の剰余の仕様が単純な $\bmod$ 演算になっていないため、実装時に注意）
このように考えると、実は $D_1$ を決めた時点で $D_2$ にはすでに選択の余地がない。
この先も、$D_2$ を決めた時点で $D_3$ にはすでに選択の余地がなく、以下すべて同様。
つまり、全探索の自由度は $D_1$ を $0$ にするか $1$ にするかの $2$ 通りしかない。
ということで、まずは $D_1=0$ の方がこの方法で $O(N)$ で調査できる。
$D_1=1$ の方は $O(N)$ 同じようにもう一度調査してもよいし、$D_1=0$ の場合の解を利用してもよい。
（$0$ or $1$ が入れ替わるだけなので、$D_1=0$ の結果を $N$ から引けば $D_1=1$ の方の答え）
小さい方がこの問題の答えである。
入力例1での動作
入力を受け取る。
n: 3
m: 2
a: {1, 1, 1}
b: {1, 1}先頭の値に $1$ すら足さない場合に、各値へ何回足すかを記録する配列 d を、すべて $0$ で初期化する。
d: {0, 0, 0}$i=1$ のとき、$b[0]-a[1]-a[0]-d[0] = 1-1-1-0 = -1$ を $m$ で割った余りは $1$ なので d[1]=1 とする。
d: {0, 1, 0}$i=2$ のとき、$b[1]-a[2]-a[1]-d[1] = 1-1-1-1 = -2$ を $m$ で割った余りは $0$ なので d[2]=0 とする。
d: {0, 1, 0}d の要素の合計である $1$ が、先頭の値に $1$ を足さない場合の操作回数である。
また、それを $N$ から引いた $2$ が、先頭の値に $1$ を足す場合の操作回数である。
小さい方である $1$ が答え。
注意点
特になし。