ありそうで意外になかった?問題。
http://codeforces.com/contest/909/problem/F
問題
正整数Nが与えられる。
1~Nのpermutation P,Qのうち、以下を満たすものがあれば一例を答えよ。
- P[i] != i かつ P[i] and i = 0
- Q[i] != i かつ Q[i] and i != 0
解法
P
Nが奇数の場合解なし。
最下位ビットが経つものが(N+1)/2個あるので、どう並べ替えてもP[i] and iが正になるものができてしまう。
そうでない場合、まずP[i] = ~iと取れば確実にP[i] and i=0となる。
あとは大きすぎる値を1~Nに収まるようにしていく。
具体的には以下のようにする。
- P[i]の値を2進数で上位桁から見ていき、N以下になるようビットを削っていく。
- Nが2の累乗でない場合、同じ値が2回出る場合があるので、その場合片方は最上位ビットを1つ落とす。
Q
- N≦5およびNが2の累乗のときは解なし。Nが2の累乗の場合、Nより小さい値MでN & Mが正になりえないことより明らか。
- N=6,7は総当たりしよう。
- N=8は解なしなので、N≧9の例を考える。
- 先頭7個はN=7のケースを使いまわす。
- 以降は、最上位ビットが等しいもの同士を1つrotateすればよい。
void getP(int N) { vector<int> V; int i; if(N%2==0) { _P("YES\n"); set<int> S; FOR(i,N) { V.push_back(((1<<20)-1)^(i+1)); for(int j=19;j>=0;j--) { if((V.back()&(1<<j)) && (V.back()>N || S.count(V.back()))) V.back()^=1<<j; } S.insert(V.back()); } FOR(i,N) _P("%d%c",V[i],(i==N-1)?'\n':' '); //FOR(i,N) _P("%d:%d%c",V[i]==(i+1),V[i]&(i+1),(i==N-1)?'\n':' '); } else { _P("NO\n"); } } void getQ(int N) { if(N<6 || (N&(N-1))==0) return _P("NO\n"); _P("YES\n"); if(N==6) { _P("3 6 2 5 1 4\n"); return; } vector<int> V={3,6,1,5,4,7,2}; int i; for(i=8;i<=N;i++) V.push_back(i); int x=8; while(x<=V.back()) { rotate(V.begin()+x-1,V.begin()+x,V.begin()+min(2*x-1,N)); x*=2; } V.resize(N); FOR(i,N) _P("%d%c",V[i],(i==N-1)?'\n':' '); //FOR(i,N) _P("%d:%d%c",V[i]==(i+1),V[i]&(i+1),(i==N-1)?'\n':' '); } void solve() { int i,j,k,l,r,x,y; string s; cin>>x; getP(x); getQ(x); }
まとめ
最初Pがすんなり解けたと思ったら間違っていて、結果的にPの方が苦戦した。