kmjp's blog

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

第一回日本最強プログラマー学生選手権-予選- : D - Classified

これは割とすぐ思いつけた。
https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_d

問題

N頂点の完全グラフの辺を彩色する。
その際、同色の辺で奇数長の閉路ができないようにしたい。
最少で何色の色でどう彩色すればよいか。

解法

例えば1色でどのぐらい辺を張れるかを考えてみる。
まずは1-2-3-4...とつないでみる。
そうすると、もっと辺を増やしても奇数長の閉路ができないことがわかる。すなわち、偶奇が異なる辺はすべてつないでしまって問題ない。
次に、奇数だけ取り出した1,3,5,7...を2色目の辺でどう結ぶか考えてみる。同様に番号の差が4の倍数の頂点間に辺を張ってはならず、4の倍数ではないが2の倍数の頂点間に辺に張るとよい。

…こうやるとだいぶ法則が見えてきて、頂点xとyに張る頂点は、|x-y|を割り切る最大の2の累乗の値が2^cあるとき、(c+1)色目で塗るとよい。

int N;
int A[505][505];

int hoge(int a,int b) {
	int x=abs(a-b);
	int i;
	FOR(i,10) if(x&(1<<i)) return i+1;
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	
	FOR(y,N) {
		for(x=y+1;x<N;x++) {
			cout<<hoge(x,y)<<" ";
		}
		cout<<endl;
	}
}

まとめ

すぐ思いつけたと思ったけどCと解いた時間に差が無いな。