kmjp's blog

競技プログラミング参加記です

Codeforces #383 Div1 C. Arpa’s overnight party and Mehrdad’s silent entering

なんかこれはすぐに思いつけた。
http://codeforces.com/contest/741/problem/C

問題

男女のペアN組、計2N人を円形に並べる。
各人がどの位置に来るかが入力として与えられる。

2N人それぞれに2種類の料理のいずれかを配る。
その際以下の条件を満たすような配りかたが存在するか。
存在するなら一例を示せ。

  • 同じペアの男女は異なる料理を食べる。
  • 連続する3人が同じ料理を食べることはない。

解法

後者の条件が一見厄介で、3SAT問題に見える。
全体では両方の料理はN人ずつ食べる。
そこで2N人を隣接する2ずつN組に分け、組内で両者を1人ずつ食べることを考えよう。
こうすると3人以上同じ料理を食べることはない。

あとは料理未確定の人がいたらその人の料理を確定させると、組になる隣の人の料理が決まり、対応するペアの相方の料理が決まり…と連鎖的に決まっていく。
組または男女ペアで連結した人は偶数長の閉路を成すので、矛盾が生じる危険はない。

int N;
int A[202020],B[202020];
int C[202020];
int X[202020];

void dfs(int cur,int col) {
	int oth=cur^1;
	
	if(X[C[oth]%N]>=0) return;
	int ocol = col^1;
	
	int tar;
	if(C[oth]>=N) {
		tar=A[C[oth]%N];
		X[C[oth]%N]=ocol^1;
	}
	else {
		tar=B[C[oth]];
		X[C[oth]]=ocol;
	}
	
	dfs(tar,col);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	MINUS(X);
	cin>>N;
	FOR(i,N) {
		cin>>A[i]>>B[i];
		A[i]--;
		B[i]--;
		C[A[i]]=i;
		C[B[i]]=N+i;
	}
	FOR(i,N) if(X[i]==-1) {
		X[i]=0;
		dfs(A[i],0);
	}
	
	FOR(i,N) _P("%d %d\n",X[i]+1,(X[i]^1)+1);
}

まとめ

これのおかげでレートがかなり上がった。