Codeforces #183 Div1. A. Lucky Permutation Triple

この回は本番A,Bを解いてほどほどの順位。後でCを解いたけど実行時間を落とすのにかなり苦労した。

うーん、CFの未回答問題が溜まってきたし、SRMに比べここに書くまでの時間が空いてきた。
これでは解いた当時の考え方を忘れてしまう…。
http://codeforces.com/contest/303/problem/A

問題

数Nに対し、0～(N-1)で構成されるpermutation A,B,Cを考える。
このときA[i]+B[i] = C[i] (mod N)となるA,B,Cを返せ。
そのようなA,B,Cが返せないとき、-1を返せ。

解法

Nが奇数の場合、A[i]=B[i]=i、C[i]=(i*2)%Nでよい。
Nが偶数の場合、そのようなA,B,Cは存在しない。

本番はNが偶数のケースで存在しない、と自信がないまま出してしまった。
ただ、Editorialに綺麗な証明があったね。
S=0+1+...+(N-1)とすると、A[i]とB[i]のすべての和は2S、C[i]の和はSだけど、前者は偶数、後者は奇数、Nが偶数なら2S % Nは偶数、S % Nは奇数なので一致しない。

int N;
vector<int> V;

void solve() {
	int f,r,i,j,k,l, x,y,ma,num,nt;
	
	N=GETi();
	if(N%2==1) {
		FOR(i,N) _P("%d ",i);
		_P("\n");
		FOR(i,N) _P("%d ",i);
		_P("\n");
		FOR(i,N) _P("%d ",(i*2)%N);
		_P("\n");
	}
	else {
		_P("%d\n",-1);
	}
	return;
}

まとめ

こういう数列の構築問題、CFに多いね。