kmjp's blog

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

Codeforces #455 Div2 F. AND-permutations

ありそうで意外になかった?問題。
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の方が苦戦した。