kmjp's blog

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

CODE FESTIVAL 2016 Relay : I - 目があったら負け / 3y3s Challenge

考えすぎたけど簡単だった。
http://cf16-relay-open.contest.atcoder.jp/tasks/relay_i

問題

N頂点に対する有向グラフを(N-1)回作る。
各回では、各頂点はそれ以外の頂点に対し1回ずつ有向辺を張るようにしたい。
この時、2頂点間に双方向の辺ができないようにしたい。

Nが与えられるので、そのようなグラフを(N-1)回作成せよ。

解法

Nが奇数の時は簡単である
頂点番号を0-originで考えたとき、i回目のグラフでは、頂点vは(v+i)%N番の頂点に辺を張ればよい。

Nが偶数の場合、この方法ではN/2回目にvと(v+N/2)%Nの頂点で双方向の辺ができてしまう。
そこでここを少しずらすことを考える。
番号は後半の頂点(N/2~(N-1)番)についてはN/2回目と(N/2+1)回目で指す頂点を逆にすればよい。
なお、N=2の時だけはこの手段が取れず解なしとなる。

int N;
int ret[101][101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	if(N==2) return _P("-1\n");
	if(N%2==1) {
		FOR(y,N) FOR(x,N-1) _P("%d%c",(x+y+1)%N+1,(x==N-2)?'\n':' ');
	}
	else {
		FOR(y,N) FOR(x,N-1) {
			if(y>=N/2 && x==N/2-1) _P("%d%c",(x+y+2)%N+1,(x==N-2)?'\n':' ');
			else if(y>=N/2 && x==N/2) _P("%d%c",(x+y)%N+1,(x==N-2)?'\n':' ');
			else _P("%d%c",(x+y+1)%N+1,(x==N-2)?'\n':' ');
		}
	}
	
}

まとめ

Nが偶数のとき、無駄に複雑に動かそうとしてしまった。