글 읽기 - 반례를 구해봅니다..

p_ce1052 3년 전 0

코드가 좀 길어서 주석을 달았습니다

기본적인 아이디어는 입력받은 배열을 반으로 나누고 각각에 대해

(팀1의 점수 - 팀2의 점수 , 해당 차이를 만드는 선별 상태 비트마스킹 중 최솟값) 을 모두 구해놓고

배열 1과 배열 2에서 저 차이를 더해서 0에 최대한 가까워야 되므로

배열 1의 원소를 하나씩 보면서 (차이값 * -1) 한 값을 배열 2에서 이분탐색으로 찾습니다.

상태 1과 상태 2를 하나로 합쳐서 (전체 차이, 상태) 를 만들고 최종적인 답과 비교하여 갱신해줍니다.

upper_bound로 찾았으므로 그 근방의 값을 1~2개 정도 더 고려해서 답을 갱신해줍니다.

배열1의 원소에 첫 번째 원소부터 높은 비트를 부여하였고 팀 1이되면 비트를 켜지 않음, 팀2가 되면 해당 비트를 켬 으로 정하였습니다.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
int n;
long long unit = 1;
vector<pi>arr1,arr2;
vector<pi>ret1,ret2;
map<ll,ll>m1,m2;	
ll mindiff = INT64_MAX;
ll minstate = INT64_MAX;

void dfs1(int cur,ll sum,ll state){ //첫 번째 배열에 대해 부분집합 만들기
	if(cur==arr1.size()){
		if(m1.find(sum)!=m1.end()) m1[sum] = min(m1[sum],state); //해당 차이값을 가지는 부분집합이 있다면 갱신
		else m1[sum] = state; //부분집합이 없었다면 현재 상태를 입력
		return; 
	}
	
	int index = arr1.size()-1-cur;
	dfs1(cur+1,sum+arr1[cur].first,state); //1번 팀에 넣는다면 비트를 켜지 않음, 점수는 +시킴
	dfs1(cur+1,sum-arr1[cur].second,state|(1<<index)); //2번 팀에 넣는다면 비트를 켜고 점수는 -시킴 
}
void dfs2(int cur,ll sum,ll state){
	if(cur==arr2.size()){
		if(m2.find(sum)!=m2.end()) m2[sum] = min(m2[sum],state);
		else m2[sum] = state;
		return;
	}
	int index = arr2.size()-1-cur;
	dfs2(cur+1,sum+arr2[cur].first,state);
	dfs2(cur+1,sum-arr2[cur].second,state|(1<<index));
}
ll merge(ll state1,ll state2){ //배열 1의 상태와 배열 2의 상태를 합친다. 
	ll ret = 0;
	ll cnt = 0;
	for(int i=0; i<arr2.size(); i++){
		if(state2%2) ret|=(unit<<cnt);
		state2/=2;
		cnt++;
	}
	for(int i=0; i<arr1.size(); i++){
		if(state1%2) ret|=(unit<<cnt);
		state1/=2;
		cnt++;
	}
	return ret;
}
void solve(ll cur,ll state){
	int l = 0;
	int r = ret2.size()-1;
	while(l<=r){ //cur 값과 합해서 0이 되는 -cur 과 가장 가까운 값을 찾는다. 
		int mid = (l+r)/2;
		if(ret2[mid].first<=cur*-1) l = mid+1;
		else r = mid-1;
	}
	ll newstate;
	
	if(l==0){
		ll made = abs(cur+ret2[l].first);
		newstate = merge(state,ret2[l].second);
		if(made<mindiff){
			mindiff = made;
			minstate = newstate;
		}
		else if(made==mindiff) minstate = min(minstate,newstate);
		l++;
		if(l!=ret2.size()){ //찾은곳 근처도 탐색 
			made = abs(cur+ret2[l].first);
			newstate = merge(state,ret2[l].second);
			if(made<mindiff){
				mindiff = made;
				minstate = newstate;
			}
			else if(made==mindiff) minstate = min(minstate,newstate);
		}
	}
	else if(l==ret2.size()){
		l--; //찾은곳 근처도 탐색
		ll made = abs(cur+ret2[l].first);
		newstate = merge(state,ret2[l].second);
		if(made<mindiff){
			mindiff = made;
			minstate = newstate;
		}
		else if(made==mindiff) minstate = min(minstate,newstate);
		l--; //찾은 곳 근처 탐색
		if(l>=0){
			made = abs(cur+ret2[l].first);
			newstate = merge(state,ret2[l].second);
			if(made<mindiff){
				mindiff = made;
				minstate = newstate;
			}
			else if(made==mindiff) minstate = min(minstate,newstate);
		}
	}
	else{
		ll made = abs(cur+ret2[l].first);
		newstate = merge(state,ret2[l].second);
		if(made<mindiff){
			mindiff = made;
			minstate = newstate;
		}
		else if(made==mindiff) minstate = min(minstate,newstate);
		
		l--;
		made = abs(cur+ret2[l].first);
		newstate = merge(state,ret2[l].second);
		if(made<mindiff){
			mindiff = made;
			minstate = newstate;
		}
		else if(made==mindiff) minstate = min(minstate,newstate);
		l--;
		if(l>=0){
			made = abs(cur+ret2[l].first);
			newstate = merge(state,ret2[l].second);
			if(made<mindiff){
				mindiff = made;
				minstate = newstate;
			}
			else if(made==mindiff) minstate = min(minstate,newstate);
		}
	}
}
int main(){
	cin>>n;
	arr1 = vector<pi>(n);
	for(int i=0; i<n; i++) cin>>arr1[i].first;
	for(int i=0; i<n; i++) cin>>arr1[i].second;
	for(int i=0; i<n/2; i++){
		arr2.push_back(arr1.back());
		arr1.pop_back();
	}	
	reverse(arr2.begin(),arr2.end());
	dfs1(0,0,0);
	dfs2(0,0,0);
	//이분탐색을 위해 배열에 옮겨담기
	for(auto it = m1.begin(); it!=m1.end(); it++) ret1.push_back(pi(it->first,it->second));
	for(auto it = m2.begin(); it!=m2.end(); it++) ret2.push_back(pi(it->first,it->second));
	sort(ret1.begin(),ret1.end());
	sort(ret2.begin(),ret2.end());
	
    //각각의 배열1의 상태에 대해 가장 가까운 배열2의 상태 이분탐색 
	for(int i=0; i<ret1.size(); i++) solve(ret1[i].first,ret1[i].second);
	stack<int>st; //하위비트부터 배열2의 마지막 원소 -> 배열2의 첫 원소 -> 배열1의 마지막 원소-> 배열1의 첫 원소 
                  //순으로 들어가있으므로 스택을 사용한다. 
	while(n--){
		st.push(minstate%2+1);
		minstate/=2;
	}
	while(st.size()){
		cout<<st.top()<<" ";
		st.pop();
	}
}

snrnsidy 3년 전 3

50 50 50 1

30 30 30 150

답은 1 2 2 1가 출력이 되어야 합니다.

p_ce1052 3년 전 0

감사합니다 감사합니다 감사합니다

p_ce1052 3년 전 0

저 1 2 2 1 을 하면 두 팀간 차이가 9가 나오지 않나요? 제 코드는 1 1 1 2 를 출력하는데 이 경우 팀 차이는 0으로 이쪽이 팀 차이를 최소로 만드는 것에 더 부합하는게 아닌지

p_ce1052 3년 전 1

팀원 수가 같게 만들어야 되는군요... 가장 중요한 조건을 놓치고 문제를 풀고 있었네요.

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

문제

문제

출처

ICPC

반례를 구해봅니다..

p_ce1052 3년 전 0

snrnsidy 3년 전 3

p_ce1052 3년 전 0

p_ce1052 3년 전 0

p_ce1052 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말