D - Forbidden Difference
Source: atcoder
Difficulty: 425

Problem Statement
You are given a length-
N
integer sequence
A=(A_1,A_2,\dots,A_N)
and a non-negative integer
D
.
We wish to delete as few elements as possible from
A
to obtain a sequence
B
that satisfies the following condition:
|B_i - B_j|\neq D
for all
i,j \; (1 \leq i < j \leq |B|)
.
Find the minimum number of deletions required.
Constraints
1 \le N \le 2\times 10^5
0 \le D \le 10^6
0 \le A_i \le 10^6
All input values are integers.
Input
The input is given from Standard Input in the following format:
N
D
A_1
A_2
\dots
A_N
Output
Print the answer.
Sample Input 1
5 2
3 1 4 1 5
Sample Output 1
1
Deleting
A_1=3
yields
B=(1,4,1,5)
, which satisfies
|B_i - B_j|\neq 2
for all
i<j
.
Sample Input 2
4 3
1 6 1 8
Sample Output 2
0
The sequence
A
may already satisfy the condition.
Sample Input 3
10 3
1 6 2 10 2 3 2 10 6 4
Sample Output 3
2

C++ solution:
#include <bits/stdc++.h>
using namespace std;

const int mx = 1e6 + 10; // 定义最大数值范围
int cnt[mx];             // 计数数组，记录每个数值出现的次数

void solve() {
  int n, d; // n: 数字数量, d: 模数
  cin >> n >> d;

  // 读取输入并统计每个数字出现的次数
  for (int i = 0; i < n; i++) {
    int val;
    cin >> val;
    cnt[val]++;
  }

  // 处理d=0的特殊情况(所有相同数字只能保留一个)
  if (d == 0) {
    int dup = 0; // 统计不同数字的数量
    for (int i = 0; i < mx; i++)
      dup += (cnt[i] > 0);
    cout << n - dup << '\n'; // 输出需要删除的数量(总数-不同数字数)
    return;
  }

  int ans = 0;
  // 对每个余数分组处理(0到d-1)
  for (int i = 0; i < d; i++) {
    int take = 0, skip = 0; // take: 取当前数字, skip: 不取当前数字

    // 处理当前余数分组(i, i+d, i+2d...)
    for (int j = i; j < mx; j += d) {
      // 动态规划状态转移:
      // 不能连续取两个相邻的数字(在模d意义下相邻)
      tie(take, skip) = make_pair(skip, min(take, skip) + cnt[j]);
    }
    ans += min(take, skip); // 取当前余数分组的最优解
  }
  cout << ans << '\n'; // 输出需要删除的最小数量
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0); // 加速输入输出
  solve();
  return 0;
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"sort"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)
var wr = bufio.NewWriter(os.Stdout)

func out(x ...interface{}) {
	fmt.Fprintln(wr, x...)
}

func outSlice[T any](s []T) {
	if len(s) == 0 {
		return
	}
	for i := 0; i < len(s)-1; i++ {
		fmt.Fprint(wr, s[i], " ")
	}
	fmt.Fprintln(wr, s[len(s)-1])
}

func getI() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getF() float64 {
	sc.Scan()
	i, e := strconv.ParseFloat(sc.Text(), 64)
	if e != nil {
		panic(e)
	}
	return i
}

func getInts(N int) []int {
	ret := make([]int, N)
	for i := 0; i < N; i++ {
		ret[i] = getI()
	}
	return ret
}

func getS() string {
	sc.Scan()
	return sc.Text()
}

// min, max, asub, absなど基本関数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

// min for n entry
func nmin(a ...int) int {
	ret := a[0]
	for _, e := range a {
		ret = min(ret, e)
	}
	return ret
}

// max for n entry
func nmax(a ...int) int {
	ret := a[0]
	for _, e := range a {
		ret = max(ret, e)
	}
	return ret
}

func chmin(a *int, b int) bool {
	if *a < b {
		return false
	}
	*a = b
	return true
}

func chmax(a *int, b int) bool {
	if *a > b {
		return false
	}
	*a = b
	return true
}

func asub(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

func abs(a int) int {
	if a >= 0 {
		return a
	}
	return -a
}

func lowerBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] >= x
	})
	return idx
}

func upperBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] > x
	})
	return idx
}

func main() {
	defer wr.Flush()
	sc.Split(bufio.ScanWords)
	sc.Buffer([]byte{}, math.MaxInt32)
	// this template is new version.
	// use getI(), getS(), getInts(), getF()
	N, D := getI(), getI()
	a := getInts(N)
	const maxn = int(1e6 + 10)
	b := make([]int, maxn)
	for i := 0; i < N; i++ {
		b[a[i]]++
	}

	if D == 0 {
		// 同じ値は１つだけしか残せない
		ans := 0
		for i := 0; i < maxn; i++ {
			ans += max(0, b[i]-1)
		}
		out(ans)
		return
	}
	const inf = int(1e18)
	ans := 0
	for i := 0; i < D; i++ {
		cnt := make([]int, 0)
		for j := i; j < maxn; j += D {
			cnt = append(cnt, b[j])
		}
		dp := make([][2]int, len(cnt)+1)
		for j := 0; j < len(cnt); j++ {
			dp[j][0] = inf
			dp[j][1] = inf
		}
		dp[0][0] = 0
		for j := 0; j < len(cnt); j++ {
			dp[j+1][0] = min(dp[j][0]+cnt[j], dp[j][1]+cnt[j])
			dp[j+1][1] = dp[j][0]
		}
		ans += min(dp[len(cnt)][0], dp[len(cnt)][1])
		// out(i, cnt)
	}
	out(ans)
}

Java solution:
import java.io.*;
import java.util.*;
import java.util.function.*;
import java.util.stream.*;

public class Main {
    public static void main(String[] args) throws Exception {
        FastScanner sc = new FastScanner();
        int n = sc.nextInt();
        int d = sc.nextInt();
        int[] counts = new int[1000001];
        for (int i = 0; i < n; i++) {
            counts[sc.nextInt()]++;
        }
        if (d == 0) {
            int ans = 0;
            for (int x : counts) {
                if (x > 0) {
                    ans += x - 1;
                }
            }
            System.out.println(ans);
            return;
        }
        int ans = 0;
        for (int i = 0; i < d; i++) {
            int live = 0;
            int delete = 0;
            for (int j = i; j <= 1000000; j += d) {
                int nextLive = delete;
                int nextDelete = Math.min(live, delete) + counts[j];
                live = nextLive;
                delete = nextDelete;
            }
            ans += Math.min(live, delete);
        }
        System.out.println(ans);
    }
}

class FastScanner {
    private DataInputStream din;
    private byte[] buffer;
    private int bufferPointer, bytesRead;
    private static final int BUFFER_SIZE = 1 << 16; // 65,536 バイト

    public FastScanner() {
        din = new DataInputStream(System.in);
        buffer = new byte[BUFFER_SIZE];
        bufferPointer = bytesRead = 0;
    }

    private byte read() {
        try {
            if (bufferPointer == bytesRead) {
                bytesRead = din.read(buffer, 0, BUFFER_SIZE);
                if (bytesRead == -1) return -1;
                bufferPointer = 0;
            }
            return buffer[bufferPointer++];
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    public String next() {
        byte b = read();
        // 空白文字を読み飛ばす
        while (isSpaceChar(b)) {
            b = read();
        }
        StringBuilder sb = new StringBuilder();
        while (!isSpaceChar(b)) {
            sb.append((char) b);
            b = read();
        }
        return sb.toString();
    }

    public int nextInt() {
        int ret = 0;
        byte c = read();
        while (isSpaceChar(c)) c = read();
        boolean neg = (c == '-');
        if (neg) c = read();
        do {
            ret = ret * 10 + c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return neg ? -ret : ret;
    }

    public long nextLong() {
        long ret = 0;
        byte c = read();
        while (isSpaceChar(c)) c = read();
        boolean neg = (c == '-');
        if (neg) c = read();
        do {
            ret = ret * 10L + c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return neg ? -ret : ret;
    }

    public double nextDouble() {
        double ret = 0, div = 1;
        byte c = read();
        while (isSpaceChar(c)) c = read();
        boolean neg = (c == '-');
        if (neg) c = read();
        do {
            ret = ret * 10 + c - '0';
            c = read();
        } while (!isSpaceChar(c) && c != '.');
        if (c == '.') {
            while (!isSpaceChar(c = read())) {
                ret += (c - '0') / (div *= 10);
            }
        }
        return neg ? -ret : ret;
    }

    private boolean isSpaceChar(byte c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    public void close() {
        try {
            if (din != null) din.close();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }
}

JavaScript solution:
"use strict";
var input=require("fs").readFileSync("/dev/stdin","utf8");
var cin=input.split(/ |\n/),cid=0;
function next(){return +cin[cid++];}
function nextstr(){return cin[cid++];}
function nextbig(){return BigInt(cin[cid++]);}
function nexts(n,a){return a?cin.slice(cid,cid+=n):cin.slice(cid,cid+=n).map(a=>+a);}
function nextssort(n,a){return a?cin.slice(cid,cid+=n).map(a=>+a).sort((a,b)=>b-a):cin.slice(cid,cid+=n).map(a=>+a).sort((a,b)=>a-b);}
function nextm(h,w,a){var r=[],i=0;if(a)for(;i<h;i++)r.push(cin.slice(cid,cid+=w));else for(;i<h;i++)r.push(cin.slice(cid,cid+=w).map(a=>+a));return r;}
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill().map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill().map(x=>"+r+")";return eval(r);}
var streams=[];function print(s){streams.push(s);}

var myOut = main();
if(myOut !== undefined)console.log(String(myOut));
if(streams.length)console.log(streams.join("\n"));

function main(){
  var q = 1;
  while(q--)print(solve());
}

function solve(){
  var [n,d] = nexts(2);
  var b = xArray(0,1e6+1);
  for(var i = 0; i < n; i++){
    b[next()]++;
  }
  var ans = 0;
  if(d === 0){
    for(var i = 0; i <= 1e6; i++){
      ans += b[i] ? b[i]-1 : 0;
    }
  }
  else for(var i = 0; i < d; i++){
    var dp0 = 0, dp1 = b[i];
    for(var j = i+d; j <= 1e6; j+=d){
      var dpx0 = dp1;
      var dpx1 = Math.min(dp0,dp1) + b[j];
      dp0 = dpx0;
      dp1 = dpx1;
    }
    ans += Math.min(dp0, dp1);
  }
  return ans;
}

Python solution:
import sys

sys.setrecursionlimit(10**6)
MOD = 998244353


def dprint(*args, **kwargs):
    print(*args, **kwargs, file=sys.stderr)


N, D = map(int, input().split())
A = [int(x) for x in input().split()]
if D == 0:
    print(N - len(set(A)))
    exit()
M = max(A)
count = [0] * (M + 1)
for a in A:
    count[a] += 1

ans = 0
for r in range(D):
    dp = [0, 0]  # 取らない, 取る
    i = r
    while i <= M:
        dp = [
            max(dp[0], dp[1]),
            dp[0] + count[i],
        ]
        i += D
    ans += max(dp)
print(N - ans)

Ruby solution:
n, d = gets.chomp.split.map(&:to_i)
aa = gets.chomp.split.map(&:to_i)

aamax = aa.max
rr = Array.new(aamax + 1, 0)
aa.each do |a|
  rr[a] += 1
end

if d == 0 then
  puts rr.select { |r| r > 1 } .map { |r| r - 1 } .sum
  exit
end

ans = 0
d.times do |di|
  ci = di
  tbds = []
  while ci <= aamax do
    (ci += d; next) if rr[ci] == 0 || ci - d < 0 || rr[ci - d] == 0
    if !tbds.empty? && tbds[-1][-1] == ci - d then
      tbds[-1] << ci
    else
      tbds << [ci - d, ci]
    end
    ci += d
  end
  tbds.each do |bb|
    dp = Array.new(bb.size + 1) { Array.new(2, n + 1) }
    dp[0] = [0, 0]
    bb.each_with_index do |b, i|
      i += 1
      dp[i][0] = [dp[i][0], dp[i - 1][1]].min
      dp[i][1] = [dp[i][1], dp[i - 1][0] + rr[b], dp[i - 1][1] + rr[b]].min
    end
    ans += dp[bb.size].min
  end
end
puts ans