New Year Contest 2015 : K - チーム戦

答えだけ見れば簡単なんだけど、自分で発想するのは難しい。
http://nyc2015.contest.atcoder.jp/tasks/nyc2015_11

問題

N人の人が最大でN^2回以下の練習を行う。
１回の練習では３人が参加できる。

任意の２人組について、一緒に練習した回数が等しくなるような練習順を答えよ。

解法

N≦8の時、なので３人の組み合わせを総当たりすればよい。

それ以上はわからず、Writer解を見て解いた。

Nが奇数の場合

N人を円形に並べたとし、端から0～(N-1)番の番号をふったとする。
i番の人は1≦j≦N/2となるjに対し(i-j), i, (i+j) (mod N)番の３人で練習を行うようにする。
各i,jについて処理を行うと,練習の回数はN*floor(N/2)回。
２人組の組み合わせもN*floor(N/2)組で、各組３回ずつ練習できる。

Nが偶数の場合

• 0～(N-2)番を円形に並べ：
  • i番目の人は1≦j≦N/2となるjに対し(i-j), i, (i+j) (mod (N-1))番の３人で練習を行う。
  • さらに2≦j≦N/2となるjに対し再度(i-j), i, (i+j) (mod (N-1))番の３人で練習を行う。
• 続けて最後の1人(N-1)番の人を真ん中に置き：
  • 0≦i≦N-2の各iに対し、i,(i+1),(N-1)の３人の練習を２回ずつ行う。
  • 最後に0≦i≦N-2の各iに対し、(i-1),(i+1),(N-1)の３人の練習を１回ずつ行う。

合計練習回数は(N-1)*((N-2)/2+(N-4)/2) + 3*(N-1) = (N-1)*N回。
２人組の組み合わせはN*(N-1)/2組で、各組６回ずつ練習できる。

int N;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	if(N<=8) {
		_P("%d\n",N*(N-1)*(N-2)/6);
		FOR(i,N) FOR(x,i) FOR(y,x) _P("%d %d %d\n",y+1,x+1,i+1);
	}
	else if(N%2==1) {
		_P("%d\n",N*(N-1)/2);
		FOR(i,N) {
			for(j=1;j<=(N-1)/2;j++) _P("%d %d %d\n",i+1,(i+N-j)%N+1,(i+j)%N+1);
		}
	}
	else {
		_P("%d\n",(N-1)*((N-2)/2*2-1) + (N-1)*3);
		FOR(i,N-1) {
			for(j=1;j<=(N-2)/2;j++) _P("%d %d %d\n",i+1,(i+(N-1)-j)%(N-1)+1,(i+j)%(N-1)+1);
			for(j=2;j<=(N-2)/2;j++) _P("%d %d %d\n",i+1,(i+(N-1)-j)%(N-1)+1,(i+j)%(N-1)+1);
		}
		FOR(i,N-1) _P("%d %d %d\n",N,i+1,(i+1)%(N-1)+1);
		FOR(i,N-1) _P("%d %d %d\n",N,i+1,(i+1)%(N-1)+1);
		FOR(i,N-1) _P("%d %d %d\n",N,i+1,(i+2)%(N-1)+1);
	}
}

まとめ

こういうの問題考える方も解く方もすごいな。