これは割とすぐ思いつけた。
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と解いた時間に差が無いな。