考えすぎたけど簡単だった。
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が偶数のとき、無駄に複雑に動かそうとしてしまった。