글 읽기 - 상남자 곽철용 반례를 찾고있습니다.

pichulia 4년 전 1

제가 왠만해서는 이런 질문글을 안올리려고 하는데..이건 너무 이상해서 질문글을 올려봅니다.

"각 참가자의 점수는 두 장의 카드에 적힌 숫자를 K로 나눈 나머지의 차이다."

라는 의미는 카드에 적힌 값이 j, k 라면 점수는 abs(j%K - k%K) 임을 의미한다고 생각했고, 이거 말고 다른걸 의미했다면(abs(j-k)%K였다면) 이건 출제자가 혼나아된다고 생각했습니다.

암튼 그래서 점수계산법이 위와 같은 상황이 맞다면 결국 내 점수 (제 코드상에서는 'q'라는 변수로 관리됩니다.)보다 크게 되는 숫자카드 쌍이 최대 몇개이냐를 묻는 문제가 됩니다.

해당 문제를 풀기 위해서 double pointer 기법이랑..뭐 이래저래 자잘한 증명과 함께 해당 문제를 푸는 알고리즘을 구현했고, 게임 참가자 수가 m명이라서 정답은 최대 m-1까지밖에 안된다는것을 반영해서 답을 잘 구했습니다...만... 계속해서 '틀렸습니다'를 받고있기 때문에 이렇게 '맞왜틀'을 시전해봅니다.

중간중간 있는 printf("wahaha")는 가끔 있는 data 오류를 검출하고자 있는 저만의 무결성 검증방식이고... 아쉽게도(?) 이 문제는 데이터의 문제는 없는걸로 판명났습니다 ㅠㅠ

올려둔 코드 중 146번째 줄 부터는 제 코드의 정당성?을 증명하기 위해 작성한 테스트코드로,

bruteforce로 탐색한 정답과, 제 코드의 정답을 비교해서 반례를 찾으려고 시도했던 흔적입니다.

랜덤 데이터는 적당히 다 통과되고 있어서 현재는 가능한 "모든"(이라고 해봤자 a값이 6 이하인 경우만 보고있지만...) 데이터를 다 집어넣어봐서 답을 비교해보고 있는 상태입니다. 질문글을 작성하는동안 p=7인 케이스까지는 틍과가 됐습니다.

#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
int n, m, p, q;
int b[400009];
int a[400009];
void input() {
	int i, j, k;
	scanf("%d %d %d", &n, &m, &p);
    if(m<1 || m>n || n>100000)for(i=2;i>0;i++)printf("wahaha\n");
    if(p<1 || p > 4*n)for(i=2;i>0;i++)printf("wahaha\n");
    
	for (i = 1; i <= 4 * n; i++) { b[i] = 0;}
    for(i=0;i<p;i++)a[i]=0;
	for (i = 0; i < m; i++) {
		scanf("%d %d", &j, &k);
    if(j<1 || j > 4*n)for(i=2;i>0;i++)printf("wahaha\n");
    if(k<1 || k > 4*n)for(i=2;i>0;i++)printf("wahaha\n");
		b[j]++;
		b[k]++;
	}
	scanf("%d %d", &j, &k);
    if(j<1 || j > 4*n)for(i=2;i>0;i++)printf("wahaha\n");
    if(k<1 || k > 4*n)for(i=2;i>0;i++)printf("wahaha\n");
	b[j]++;
	b[k]++;
	j %= p;
	k %= p;
	q = j - k;
    if(q<0)q=-q;

	for (i = 1; i <= 4 * n; i++) {
		if (b[i] > 1) {
			for (i = 2; i > 0; i++)printf("wahhaha\n");
		}
		if (b[i] == 0) {
			a[i % p]++;
		}
	}
}
#define I 524288
int ma[I];
int ms[2 * I];
int geta(int dep, int qr, int ll, int rr) {
	if (rr <= qr) {
		return ms[dep];
	}
	else if (qr < ll) return -1;
	return max(geta(dep * 2, qr, ll, (ll + rr) / 2), geta(dep * 2 + 1, qr, (ll + rr) / 2 + 1, rr));
}
void update(int i, int k) {
	bool skip = true;
	if (k >= 0) {
		ma[i]++;
		if (ma[i] == 1) { skip = false; }
	}
	else {
		ma[i]--;
		if (ma[i] == 0) { skip = false; }
	}
	if (!skip) {
		i = i + I;
		ms[i] = k;
		i >>= 1;
		while (i > 0) {
			ms[i] = max(ms[i * 2], ms[i * 2 + 1]);
			i >>= 1;
		}
	}
}
void process() {
	int i, j, k;
	int res = 0;
	for (i = 0; i < 2 * I; i++) { ms[i] = -1; }
    for(i=0;i<I;i++)ma[i] = 0;
	i = 0;
	j = q + 1;
	for (; i<p && j < p && res < m - 1;) {
//		printf("%d %d ,, %d %d\n", i, j, a[i], a[j]);
		if (a[i] > 0) {
			if (a[j] == 0) {
				j++;
			}
			else {
                // select force
				if (j - i > q) {
					a[i]--;
					a[j]--;
					res++;
					update(j, j);
				}
				else if (j < i) { for(i=2;i>0;i++)printf("wahaha\n");j++; }
				else if (j == i) {
                    // x~ri i~j ---> x~i + ri~j
                    // if i==j, then a[i]>=2
                    if (a[i] >= 2) {
						int ri = geta(1, j - q - 1, 0, I - 1);
				//		printf("~~ %d %d ri : %d\n", j, j - q - 1, ri);
						if (ri >= 0) {
							update(ri, -1);
							update(i, i);
				        	update(j, j);
							a[i]--;
							a[j]--;
							res++;
						}
						else {
							j++;
						}
					}
					else {
						j++;
					}
				}
				else {
                    // x~ri i~j ---> x~i + ri~j
					int ri = geta(1, j - q - 1, 0, I - 1);
			//		printf("%d %d ri : %d\n",j, j-q-1,  ri);
					if (ri >= 0) {
						update(ri, -1);
						update(i, i);
					    update(j, j);
						a[i]--;
						a[j]--;
						res++;
					}
					else {
						j++;
					}
				}
			}
		}
		else {
			i++;
		}
	}
    if(res>m - 1)res=m - 1;
	printf("%d\n", res);
}
int main() {
	input();
	process();
}

// 이하 bruteforce 데이터와 정답을 비교하기 위해 작성한 코드.
#include<stdio.h>
#include<algorithm>
#include<queue>
#include<random>
using namespace std;
int n, m, p, q;
int a[400009];
int orig_a[400009];
int nextint(int s, int t) {
	static mt19937 rnd;
	return (int)(rnd() % (t - s + 1)) + s;
}
void input_data() {
	scanf("%d", &p);
	for (int i = 0; i < p; i++) {
		scanf("%d", &orig_a[i]);
	}
	scanf("%d", &q);
}
void build_data() {
	p = nextint(1, 15);
	for (int i = 0; i < p; i++) {
		orig_a[i] = nextint(0, 4);
	}
	q = nextint(0, p - 1);
}
void build_data_every() {
	static int is_first = 1;
	if (is_first) {
		is_first = 0;
		p = 1;
		orig_a[0] = 0;
		q = 0;
	}
	q++;
	if (q == p) {
		q = 0;
		orig_a[0]++;
		for (int i = 0; i < p; i++) {
			if (orig_a[i] >= 6) {
				orig_a[i] = 0;
				orig_a[i+1]++;
			}
			else
				break;
		}
		if (orig_a[p] == 1) {
			orig_a[p] = 0;
			printf("%d test done\n", p);
			p++;
		}
	}
}
#define I 524288
int ma[I];
int ms[2 * I];
int geta(int dep, int qr, int ll, int rr) {
	if (rr <= qr) {
		return ms[dep];
	}
	else if (qr < ll) return -1;
	return max(geta(dep * 2, qr, ll, (ll + rr) / 2), geta(dep * 2 + 1, qr, (ll + rr) / 2 + 1, rr));
}
void update(int i, int k) {
	bool skip = true;
	if (k >= 0) {
		ma[i]++;
		if (ma[i] == 1) { skip = false; }
	}
	else {
		ma[i]--;
		if (ma[i] == 0) { skip = false; }
	}
	if (!skip) {
		i = i + I;
		ms[i] = k;
		i >>= 1;
		while (i > 0) {
			ms[i] = max(ms[i * 2], ms[i * 2 + 1]);
			i >>= 1;
		}
	}
}
int process() {
	int i, j, k;
	int res = 0;
	for (i = 0; i < p; i++) {
		a[i] = orig_a[i];
	}
	for (i = 0; i < 2 * I; i++) { ms[i] = -1; }
	for (i = 0; i < I; i++)ma[i] = 0;
	i = 0;
	j = q + 1;
	for (; i < p && j < p;) {
		//		printf("%d %d ,, %d %d\n", i, j, a[i], a[j]);
		if (a[i] > 0) {
			if (a[j] == 0) {
				j++;
			}
			else {
				if (j - i > q) {
					a[i]--;
					a[j]--;
					res++;
					update(j, j);
				}
				else if (j < i) { for (i = 2; i > 0; i++)printf("wahaha\n"); j++; }
				else if (j == i) {
					if (a[i] >= 2) {
						int ri = geta(1, j - q - 1, 0, I - 1);
						//		printf("~~ %d %d ri : %d\n", j, j - q - 1, ri);
						if (ri >= 0) {
							update(ri, -1);
							update(i, i);
							update(j, j);
							a[i]--;
							a[j]--;
							res++;
						}
						else {
							j++;
						}
					}
					else {
						j++;
					}
				}
				else {
					int ri = geta(1, j - q - 1, 0, I - 1);
					//		printf("%d %d ri : %d\n",j, j-q-1,  ri);
					if (ri >= 0) {
						update(ri, -1);
						update(i, i);
						update(j, j);
						a[i]--;
						a[j]--;
						res++;
					}
					else {
						j++;
					}
				}
			}
		}
		else {
			i++;
		}
	}
	return res;
}
int naive_res;
void dfs(int dep, int cnt, int maxi) {
	if (dep == p) {
		if (naive_res < cnt) {
			naive_res = cnt;
		}
		return;
	}
	if (a[dep]) {
		if (maxi < dep + q + 1)maxi = dep + q + 1;
		for (int i = maxi; i < p; i++) {
			if (a[i]) {
				a[dep]--;
				a[i]--;
				dfs(dep, cnt + 1, i);
				a[dep]++;
				a[i]++;
			}
		}
	}
	//no look pass
	dfs(dep + 1, cnt, maxi);
}
int naive() {
	int i, j, k;
	for (i = 0; i < p; i++) {
		a[i] = orig_a[i];
	}
	naive_res = 0;
	dfs(0, 0, 0);
	return naive_res;
}
int main() {
	int tc = 0;
	while (1) {
		//input_data();
		//build_data();
		build_data_every();
		int res1 = naive();
		int res2 = process();
		//printf("%d vs %d\n", res1, res2);
		tc++;
		if (tc % 1000 == 0) {
			printf("pass %d\n", tc);
		}
		if (res1 != res2) {
			printf("wrong!\n");
			printf("%d %d\n", p, q);
			for (int i = 0; i < p; i++) {
				printf("%d ", orig_a[i]);
			}
			printf("\n");
			scanf("%d", &p);
			scanf("%d", &p);
			scanf("%d", &p);
			scanf("%d", &p);
			scanf("%d", &p);
			scanf("%d", &p);
		}
	}
}