D - Forbidden Difference https://atcoder.jp/contests/abc403/tasks/abc403_d

abc403_d.py

M = 10**6 + 1
N, D = map(int, input().split())
A = list(map(int, input().split()))
cnt = [0] * M
for x in A:
    cnt[x] += 1

if D == 0:
    print(sum(max(x - 1, 0) for x in cnt))
    exit()

ans = 0
for i in range(D):
    x = cnt[i::D]               # i, i+D, i+2D, ... の出現回数を並べた配列
    if not x:
        continue
    # dp[0][j]: j 番目まで見て、j 番目の値を「残す」場合の最小削除数
    # dp[1][j]: j 番目まで見て、j 番目の値を「すべて削除する」場合の最小削除数    
    dp = [[0] * (len(x) + 1) for _ in range(2)]
    for j in range(len(x)):
        dp[0][j + 1] = x[j] + min(dp[0][j], dp[1][j])
        dp[1][j + 1] = dp[0][j]
    ans += min(dp[0][-1], dp[1][-1])
print(ans)