\(D=0\) の場合

\(D=0\) の場合，\(|A_i-A_j|=0 \Leftrightarrow A_i=A_j\) なので，\(A\) に同じ値が現れないようにすればよいです．

\(A\) に現れる相異なる値の個数を \(X\) としたとき，それぞれの値を持つ要素を \(1\) つだけ残せるので，\(B\) の長さは最大で \(X\) です．よって，最小の操作回数は \(N-X\) です．

\(D \geq 1\) の場合：問題の言い換え

\(A\) に \(x \; (0 \leq x \leq 10^6)\) が現れる個数を \(C_x\) とします．\(A\) の要素を \(1\) つ削除することは，\(C\) の非ゼロの要素を \(1\) 減らすことに対応します．また， \(|A_i-A_j|=D\) なる \(i,j\) が存在することは，\(C_x>0\) かつ \(C_{x+D}>0\) なる \(x\) が存在することと対応します．よって，問題は以下のように言い換えられます．

• \(C_x\) の非ゼロ要素を \(1\) つ選んで \(1\) 減らすことを最小で何回繰り返せば，すべての \(x\) について \(C_x=0\) または \(C_{x+D}=0\) が成り立つようにできるか？

「すべての \(x\) について \(C_x=0\) または \(C_{x+D}=0\)」という条件は，\(x\operatorname{mod} D\) に注目することで，以下のように分解することができます．

• すべての \(i=0,1,\dots,D-1\) について以下が成り立つ
  • すべての \(j=0,1,\dots,\lfloor (10^6-i) / D \rfloor - 1\) について \(C_{i+Dj}=0\) または \(C_{i+D(j+1)}=0\)

動的計画法による解法

この問題は，\(i=0,1,\dots,D-1\) について独立に解くことができます．動的計画法を用います．\(i\) を固定し，\(\mathrm{dp}[j]\) を，「\(C_{i},C_{i+D},\dots,C_{i+Dj}\) の間で条件を満たすために必要な操作回数」とします．

\(\mathrm{dp}[0],\dots,\mathrm{dp}[j]\) までわかっているときに，\(\mathrm{dp}[j+1]\) を計算する方法を考えます．\(C_{i+D(j+1)}\) を \(0\) にするか否かで場合分けをします．

• \(C_{i+D(j+1)}\) を \(0\) にする場合：\(C_{i+D(j+1)}\) 回操作をする必要があります．このとき，\(C_{i+Dj}\) の値は何でも良く，単に \(C_{i},\dots,C_{i+Dj}\) の間で条件を満たしていれば良いので，全体の操作回数は \(\mathrm{dp}[j]+C_{i+D(j+1)}\) です．
• \(C_{i+D(j+1)}\) を \(0\) にしない場合：\(C_{i+D(j+1)}\) には \(1\) 回も操作する必要がありません．このとき，\(C_{i+Dj}\) を \(0\) にする必要があり，さらに \(C_{i},\dots,C_{i+D(j-1)}\) の間で条件を満たす必要があります．全体の操作回数は \(\mathrm{dp}[j-1] + C_{i+Dj}\) です．

以上 \(2\) 通りのうち，小さい方を取ればよいので， \(\mathrm{dp}[j+1] = \min\{\mathrm{dp}[j]+C_{i+D(j+1)},\mathrm{dp}[j-1]+C_{i+Dj}\}\) という漸化式が得られます．\(\mathrm{dp}[\lfloor (10^6-i) / D \rfloor]\) が答えです．

以上の動的計画法を各 \(i\) について実行し，総和を求めることで，問題を解くことができます．時間計算量は， \(M=10^6\) として \(O(M)\) です．

実装例 (Python)