なんかこれはすぐに思いつけた。
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); }
まとめ
これのおかげでレートがかなり上がった。