何とか解けてよかった。
https://atcoder.jp/contests/arc131/tasks/arc131_e
問題
整数Nが与えられる。
N頂点の完全グラフの辺を、以下のように塗り分けたい。
- 赤白黒の3色で塗る。その際、各色の辺の数は等しい。
- 長さ3の閉路の中で、3色の辺がいずれも登場することはない。
可能ならその1例を示せ。
解法
辺の数が3の倍数でなければ明らかに不可。
それ以外の場合、Nが6以上なら可能。
頂点Uについて、Uより大きい番号の頂点Vとの辺に対しては同じ色で塗ることを考える。
そうすると、3頂点(A,B,C) (A<B<C)からなる閉路においては、辺A-BとA-Cが同色になるので、3色が登場することはない。
あとは、どの頂点(からそれより大きな頂点番号への辺)にどの色を割り当てるかという問題となる。
これはN-1,N-2,N-3,....,1を総和が等しくなるように3等分する問題となるが、適当にどん欲で取っていっても割とうまくいく。
int N; int E[55][55]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; if((N*(N-1)/2)%3||N<6) { cout<<"No"<<endl; return; } int NE=N*(N-1)/2/3; vector<int> C[3]; int S[3]={}; for(i=N-1;i>=0;i--) { FOR(j,3) { if(S[j]+i<=NE) { S[j]+=i; C[j].push_back(i); break; } } assert(j<3); } FOR(i,3) { FORR(c,C[i]) { y=N-1-c; for(x=y+1;x<N;x++) E[y][x]=E[x][y]=i; } } FOR(k,N) FOR(y,k) FOR(x,y) { assert(E[y][x]==E[y][k]||E[y][x]==E[x][k]||E[y][k]==E[x][k]); } cout<<"Yes"<<endl; FOR(y,N) { for(x=y+1;x<N;x++) cout<<"RBW"[E[y][x]]; cout<<endl; } }
まとめ
ちょっと手間取ったけど、まぁまぁの時間で思いつけて良かった。