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}

まず $D_1=0$ とする。

$B_1=1$ なので、$D_2$ は

$$
1-1-0-1\equiv1\pmod 2
$$

より $D_2=1$ と決まる。

続いて $B_2=1$ なので、$D_3$ は

$$
1-1-1-1\equiv0\pmod 2
$$

より $D_3=0$ と決まる。

したがって、

$$
(D_1,D_2,D_3)=(0,1,0)
$$

となり、操作回数は $1$ 回である。

$D_1=1$ とした場合は $0$ と $1$ が全て入れ替わるので、

$$
(D_1,D_2,D_3)=(1,0,1)
$$

となり、操作回数は $2$ 回である。

小さい方を選び、答えは $1$ となる。

注意点

特になし。

別解

特になし。