kmjp's blog

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

AtCoder ARC #131 : E - Christmas Wreath

何とか解けてよかった。
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;
	}
	
}

まとめ

ちょっと手間取ったけど、まぁまぁの時間で思いつけて良かった。