글 읽기 - 어떤 반례가 있을까요?

p_ce1052 3년 전 0

사용되지 않은 모든 수를 k로 나눈 나머지로 관리하고 곽철용의 점수를 score라고 하면

어떤 수 x와 (x + score+1 이상의 수) 를 매칭시키고 삭제하는 작업을 반복하여 개수를 구했습니다

마지막에 min(쌍의 개수 , 참여한 사람 수 -1)을 출력하여 주었습니다.

37% 쯤에서 틀리는데 어디가 논리적으로 잘못되었는지 모르겠습니다

#include<bits/stdc++.h>
using namespace std;
bool used[400005];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n,m,k;
	cin>>n>>m>>k;
	int tmp = m;
	while(m--){
		int a,b;
		cin>>a>>b;
		used[a] = true;
		used[b] = true;
	}
	multiset<int>st;
	int ans = 0;
	int a,b;
	cin>>a>>b;
	used[a] = true;
	used[b] = true;
	int score = abs(a%k - b%k);
	for(int i=1; i<=4*n; i++){
		if(!used[i]) st.insert(i%k);
	}
	while(st.size()){
		int cur = *st.begin();
		auto it = st.upper_bound(score-cur);
		if(it==st.end()) break; //지금도 없다면 cur이 더 증가해도 당연히 없음 
		ans++;
		st.erase(it);
		st.erase(st.begin());
	}
	cout<<min(ans,tmp-1);
}

p_ce1052 3년 전 0

30번째 줄을 score+cur로 바꿔도 바로 틀리네요

slah007 3년 전 2

1. 위의 30번째줄에 score - cur은 말도 안됩니다. score == K-1인 경우 답이 0이어야 하는데 0이 안나옵니다.

2. score+cur로 바꾸면, 가능한 가장 작은 수를 찾는 것인데 이 역시 최적이 아닙니다.

예를 들어 score = 1이고 숫자가 1 2 3 4 5 6 이렇게 남아있다면

위의 알고리즘은 (1, 3), (2, 4) 매칭해서 총 2개지만

실제로는 (1, 4), (2, 5), (3, 6) 3개가 매칭 가능합니다.

10 10 40
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 40 39
19 20

ans: 9

result: 8

slah007 3년 전 1

사실 저도 계속 틀려서 정해가 뭔지는 모르겠습니다

p_ce1052 3년 전 0

감사합니다 일단 위의 알고리즘이 틀린 이유는 이해가 됬습니다. 정해는 계속 고민해봐야겠네요

p_ce1052 3년 전 0

주신 반례에서 영감을 받아 풀었습니다! 감사합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어떤 반례가 있을까요?

p_ce1052 3년 전 0

p_ce1052 3년 전 0

slah007 3년 전 2

slah007 3년 전 1

p_ce1052 3년 전 0

p_ce1052 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말