kmjp's blog

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

TopCoder SRM 693 Div1 Medium BipartiteConstruction

無駄に難しく考えすぎた。
https://community.topcoder.com/stat?c=problem_statement&pm=14290

問題

白黒同数の頂点群と、白黒頂点間を結ぶ辺からなる二部グラフで、完全マッチングの組み合わせがちょうどK通りであるものを構築せよ。
なお、辺は多重辺が許可され、かつ頂点のマッチングが同じでも異なる辺を選んだマッチングは異なるマッチングと判断される。

解法

多重辺を持つ白黒頂点対を沢山作ると、倍々ゲームの要領で組み合わせを増やすことができる。

以下白黒i番の頂点をそれぞれWi,Biと書く。
W1とB1、W2とB2~W19とB19をそれぞれ3本ずつ辺を張ると、3^19通りの組み合わせを作ることができる。

さらに、WiとB(i-1)に辺を張ろう。
仮にW0とBiに1本辺を張り、そこをマッチングさせると、W0~Wiのマッチング相手は一意に決まるので、その場合残りの頂点により3^(19-i)通りのマッチングが生成できる。
このことから、Kを3進数表現してi桁目の値だけW0とB(19-i)の間に辺を張るとよい。

class BipartiteConstruction {
	public:
	vector<int> V;
	void add(int i,int j) { V.push_back(i*20+j);}
	vector <int> construct(int K) {
		int i,j;
		
		V.clear();
		V.push_back(20);
		for(i=1;i<=19;i++) add(i,i),add(i,i),add(i,i),add(i,i-1);
		
		for(i=19;i>=1;i--) {
			FOR(j,K%3) add(0,i);
			K/=3;
		}
		
		return V;
	}
}

まとめ

本番累乗の要領で組み合わせを増やすのではなく、階乗の要領で無駄に頑張って時間切れした。