TopCoder SRM 773 : Div1 Medium Div2 Hard ChristmasTravel

既出だったみたいね。
https://community.topcoder.com/stat?c=problem_statement&pm=15865

問題

整数N,Aが与えられる。
N頂点の完全グラフの辺をA色で彩色し、同色の辺で奇数長の閉路が構築されないようにせよ。
ただし全色1回は使うこと。

解法

まず最小の色数で彩色し、最後に未使用な色があれば既存の2回以上登場する辺を置き換えよう。
頂点u,vの2進数表記において、異なる値を持つ最小の桁をdとすると、d色目で塗るようにすればよい。
同じ色dで塗られた頂点同士は、頂点番号のd bit目か異なる頂点同士を結んでいることになるので必ず二部グラフになる。

class ChristmasTravel {
	public:
	vector <string> plan(int N, int A) {
		vector<string> R,none;
		int i,x,y;
		FOR(i,N) R.push_back(string(N,'-'));
		
		vector<pair<int,int>> cand[26];
		FOR(i,A) {
			FOR(y,N) FOR(x,y) if(R[y][x]=='-' && (x&(1<<i))!=(y&(1<<i))) {
				R[y][x]=R[x][y]='A'+i;
				cand[i].push_back({y,x});
			}
		}
		
		FOR(i,A)  {
			FOR(x,A) if(cand[i].empty() && cand[x].size()>1) {
				cand[i].push_back(cand[x].back());
				cand[x].pop_back();
				R[cand[i][0].first][cand[i][0].second]='A'+i;
				R[cand[i][0].second][cand[i][0].first]='A'+i;
			}
			if(cand[i].empty()) return none;
		}
		
		FOR(y,N) FOR(x,N) if(x!=y && R[y][x]=='-') return none;
		FOR(y,N) cout<<R[y]<<endl;
		
		return R;
		
	}
}

まとめ

AtCoderで似たようなのが出てたみたい。