ヒント

ヒント1

$\bmod$ をとる操作をなくし、何か別の方法で代用しましょう。

ヒント2

条件を、$A_i\ne A_{i+1}$ かつ $|A_i-A_{i+1}| \lt M$ と言い換えましょう。

ヒント3

最終的な数列を固定しましょう。どのような数列が条件を満たし、どのような数列が $A$ から作れるでしょうか。

ヒント3の答え

明らかに、最終的な $A_i$ を $M$ で割った余りは $B_i$ でないといけません。また、$A$ の大小関係は変化しないので大小関係も保っていないといけません。

ヒント4

最終的な $A_1$ を固定すると、最終的な $A$ のすべての要素も定まります。

ヒント5

最終的な $A$ を固定したとき、たいていの場合は操作回数の自明な下界を達成することが可能です。それ以外の場合は簡単です。

ヒント6

絶対値の和を最小化したいです。このようなシチュエーションで使える有名な事実があるはずです。

解説

\(M=2\) のときは先に計算しておきます。これは、\(A,B\) が一致していれば 0 、そうでない場合は -1 です。以降、\(3\leq M\) を仮定します。

\(\bmod\) をとる操作をなくして、単に操作を以下のようにします。

• \(A_i\leftarrow A_i+1\) とする (これを、以降加算操作とする)
• \(A_i\leftarrow A_i-1\) とする (これを、以降減算操作とする)

このとき、\(A_i\ne A_{i+1}\) に加えて、\(|A_i-A_{i+1}|< M\) という条件も保ったまま変化させる必要があることになります。

最終的な数列を \(C\) とすると、\(C_i\bmod M=B_i,|C_i-C_{i+1}|< M\) である必要があります。\(B\) は良い数列であることから、\(C_i=C_{i+1}\) となることはありません。

また、\(A_i\) と \(A_{i+1}\) の大小関係は変化しないことから、 \(A_i\) と \(A_{i+1}\) の大小関係と \(C_i\) と \(C_{i+1}\) の大小関係は一致している必要もあります。

ところで、$C_1$ を決めたとき、その他の項も一意に定まります。実は、$3\leq M$ のとき必ず $C$ にすることが可能なこと、 $\sum_{i=1}^{N} |A_i-C_i|$ がそのまま操作回数になることが示せます。以下で、実際に構築しながら証明します。

証明

$A_i \lt C_i$ である $i$ をプラスの項、そうでない $i$ をマイナスの項と呼ぶことにします。

プラスの項には加算操作のみを、マイナスの項には減算操作のみをすることができればよいです。

$i$ の小さい項から操作することを考えます。また、$i-1$ 項目まではそろっていると仮定します。

まず、$i-1$ 番目を気にする必要はありません。$i-1$ 番目の項によって操作ができないとすると $C$ の条件に矛盾します。

$i$ 項目がプラスの項であるとき、$A_i+1=A_{i+1}$ であるとき、または$A_i+1-A_{i+1}=M$ であるときそのままでは加算操作ができません。そうでない場合は加算操作をすればよいだけなので、この条件を満たしてしまう場合を考えます。

このときは、$i+1$ 番目に再帰的に加算操作をすればよいです。これが可能であれば、$i$ 項目に加算することが可能になります。

この操作を再帰的に続けていったとき、ひとつ前の項を気にする必要がないことは容易に示せます。また、$N$ 項目では必ず加算できるので、操作が終了することは示せます。

これらがマイナスの項であると問題ですが、どちらの条件を満たす場合もマイナスの項であると矛盾が発生します。よって、再帰的に加算操作をする項はすべてプラスの項です。

$i$ 項目がマイナスの項であっても同様に示せます。よって、必ず $C$ にすることが可能なこと、 $\sum_{i=1}^{N} |A_i-C_i|$ がそのまま操作回数になることが示せました。

よって、あとは \(C_1\) の最適な求め方を求めさえすればよいです。\(C\) としてありうるものは \(C_1=B_1\) として定めた数列のすべての項に \(M\) を整数倍したものを足したものに限られることがわかります。いったん、\(M\) の整数倍足すことを忘れて任意の数足せることにします。

すると、これは \(\sum_{i=1}^{N}|x_i-a|\) の形で表せる関数を最小化すればよいことがわかります。最小値をとる \(a\) は \(x\) の中央値であることが示せます。これは傾きの変化する点について考えればよいです。 また、その考察をせずともSlope Trickというデータ構造を使うと容易です。

\(M\) の整数倍足すことを思い出します。これは、もともと最小値をとっていた \(a\) の前後の \(M\) の倍数だけ考えればよいです。最小値を取っていた \(a\) から離れるほどこの値は大きくなってしまうためです。

これは高々 \(2\) 通りなので、そのどちらもについて試せばよいです。計算量は、中央値を求めるのがボトルネックとなり \(O(N \log N)\) です。ただし、Median of Mediansという手法を使うことで \(O(N)\) に落とすことが可能です。どちらでも十分高速なので、この問題を解くことができました。

想定解 (PyPy3)

def space(x,y):
    if x<y:return -1
    if x==y:return 0
    if x>y:return 1

N,M=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
if M==2:
    if A==B:
        print(0)
    else:
        print(-1)
    exit()
C=[B[0]]
for i in range(1,N):
    for j in range(C[-1]//M-3,C[-1]//M+3):
        if space(A[i-1],A[i])==space(C[-1],j*M+B[i]) and abs(C[-1]-(j*M+B[i]))<M:
            C.append(j*M+B[i])
            break
add=[]
for i in range(N):
    add.append(C[i]-A[i])
add.sort()
mid=add[N//2]
ans=1<<60
for i in range(mid//M-3,mid//M+3):
    now=0
    for j in range(N):
        now+=abs(A[j]+i*M-C[j])
    ans=min(ans,now)
print(ans)