原案:admin

最終的な \(A\) を \((A'_1,A'_2,\dots,A'_N)\) とします。
\(C_1=0\) とし、\(C_{i+1} = B_i-C_i\) によって \(C\) を定めます。
\(D_i=C_i-A_i\) と置きます。
\(s=A'_1 \pmod M\) とすると、\(A'_i \equiv C_i+(-1)^{(i+1)}s \pmod M\) なので、必要な操作回数の最小値は \(\sum_{i=1}^{N}{((D_i+(-1)^{(i+1)}s) \pmod M)}\) です。
これの最小値が求まればよいです。
実は、ある \(i\) で \((D_i+(-1)^{(i+1)}s) \pmod M\) が \(0\) になるような \(s\) のみを考えればよいです（証明後述）。
そのような \(s(0 \leq s \lt M)\) を列挙し、各 \(s\) について小さい方から \(\sum_{i=1}^{N}{(D_i+(-1)^{(i+1)}s) \pmod M}\) を差分更新によって求めていきます。 \(s\) が \(1\) 増えたとき、\((D_i+(-1)^{(i+1)}s) \pmod M\) は基本的には \(i\) が奇数ならば \(1\) 増え、偶数ならば \(1\) 減ります。
\(0\) と \(M-1\) が切り替わる時だけが例外ですが、この切り替わりは \(N\) 回しか起こりません。
適切に例外が起こる \(s\) のタイミングを記録して差分更新を行うことで、答えを求めることができます。 計算量は、列挙した \(s\) をソートするパートがボトルネックで、全体で \(O(N\log N)\) です。

ある \(i\) で \((D_i+(-1)^{(i+1)}s) \pmod M\) が \(0\) になるような \(s\) のみを考えればよいことの証明

\(\sum_{i=1}^{N}{(D_i+(-1)^{(i+1)}s) \pmod M}\) が最小値を取るような \(s\) のうち、\(\min{((D_i+(-1)^{(i+1)}s) \pmod M)}\) が最小となるもの \(s'\) を取ります。 すべての \(i\) で \(D_i+(-1)^{(i+1)}s \not\equiv 0 \pmod M\) と仮定します。
\(s'+1 \pmod M\) と \(s'-1 \pmod M\) のいずれかを取ると、以下のいずれかが成り立ちます。

• \(\sum_{i=1}^{N}{(D_i+(-1)^{(i+1)}s) \pmod M}\) が小さくなる
  
• \(\sum_{i=1}^{N}{(D_i+(-1)^{(i+1)}s) \pmod M}\) は変わらず、\(\min{((D_i+(-1)^{(i+1)}s) \pmod M)}\) が小さくなる
  

よって背理法により示せました。