Submission #66028988

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#if 0
#include <stdlib.h>
int cmp(const void* x, const void* y) {
  int a = *(const int*)x, b = *(const int*)y;
  return a < b ? -1 : a > b;
}
#endif
int N, D;
int A[212345];
#if 0
int memo[212345];
int calc(int pos) {
  int ans = N + 1, candidate;
  if (pos >= N - 1) return 0;
  if (memo[pos]) return ~memo[pos];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>

#if 0
#include <stdlib.h>

int cmp(const void* x, const void* y) {
	int a = *(const int*)x, b = *(const int*)y;
	return a < b ? -1 : a > b;
}
#endif

int N, D;
int A[212345];

#if 0
int memo[212345];

int calc(int pos) {
	int ans = N + 1, candidate;
	if (pos >= N - 1) return 0;
	if (memo[pos]) return ~memo[pos];
	/* 飛ばす */
	if (A[pos + 1] - A[pos] <= D) {
		int no = pos + 1, yes = N;
		while (no + 1 < yes) {
			int m = no + (yes - no) / 2;
			if (A[m] - A[pos] <= D) no = m; else yes = m;
		}
		candidate = calc(yes) + (yes - pos - 1);
		if (candidate < ans) ans = candidate;
	}
	/* 飛ばさない */
	if (A[pos + 1] - A[pos] != D) {
		candidate = calc(pos + 1);
		if (candidate < ans) ans = candidate;
	}
	return ~(memo[pos] = ~ans);
}
#endif

int count[1123456 * 2];
int memo[1123456 * 2][2];
char visited[1123456 * 2];

int calc(int pos, int prev_erased) {
	int ans;
	visited[pos] = 1;
	if (count[pos] <= 0) return 0;
	if (memo[pos][prev_erased]) return ~memo[pos][prev_erased];
	/* 消す */
	ans = calc(pos + D, 1) + count[pos];
	/* 消さない */
	if (prev_erased) {
		int candidate = calc(pos + D, 0);
		if (candidate < ans) ans = candidate;
	}
	return ~(memo[pos][prev_erased] = ~ans);
}

int main(void) {
	int i;
	int ans = 0;
	if (scanf("%d%d", &N, &D) != 2) return 1;
	for (i = 0; i < N; i++) {
		if (scanf("%d", &A[i]) != 1) return 1;
		count[A[i]]++;
	}
#if 0
	qsort(A, N, sizeof(*A), cmp);
	printf("%d\n", calc(0));
#endif
	if (D == 0) {
		for (i = 0; i <= 1000000; i++) {
			if (count[i] > 1) ans += count[i] - 1;
		}
	} else {
		for (i = 0; i <= 1000000; i++) {
			if (count[i] > 0 && !visited[i]) {
				ans += calc(i, 1);
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}

/*

全ての組み合わせを考える → ソートしてよい

差がDになるならそこを消せばいい？ → いいえ

7 1
1 3 4 4 4 5 10

貪欲にやると 4 を消したくなるが、3 と 5 を消したほうがよい

行動を「消さない」「差がDを超えるところまで消す」から選ぶメモ化探索

↑大嘘
・「差がDを超えるところまで消す」では、1→3でD(=1)を超えるので消せない
・隣接する数値の差がD未満のとき、隣接しない数値の差がDになることがある

-----------

同じ数値はまとめる
差がDになる数値に辺を張る (それぞれの数値から高々2本しか出ない)
連結成分ごとに消す/消さないを考える

複雑な「グラフ」として考えなくても、「差がDになる」ということは等差数列である
それぞれの数列ごとに、「消す」「消さない」の行動を選んでいくメモ化探索
奇数番目/偶数番目を消す だと 2 1 1 2 (個) みたいなパターンに対応できない
「消さない」連続はダメ

*/

Submission Info

Judge Result