kmjp's blog

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

TopCoder SRM 736 Div1 Medium MinDegreeSubgraph

よく正解できたな…。
http://community.topcoder.com/stat?c=problem_statement&pm=14951

問題

N頂点M辺のシンプルな有向グラフを全通り考える。
その時、その部分グラフとして頂点の最小の次数がKとなるものがどの程度あるか。

  • 全くない
  • 一部ある
  • 全て

のいずれか答えよ。

解法

まず全くないか少しはあるかを判定しよう。
部分グラフとして(K+1)頂点の完全グラフが構築できれば条件を満たすので、N,Mが(K+1)頂点の完全グラフを構築できるか判定すればよい。

次に、少しはあることが分かったとして、次にすべてかどうかを判定する。
辺が多い場合、部分グラフとして次数の最小値が(K+1)以上となる選び方がどうしてもできてしまう。
よって、部分グラフをどう選んでも次数の最小値が(K+1)以上にならないような、できるだけ辺の多いグラフを考えよう。

以下が最大である証明はできていないが、自分は以下のようにしたら通った。

  • まずK頂点の完全グラフを考える。
  • 残り(N-K)頂点は、これらK頂点全てと辺をつなぐと(K+1)の完全グラフができてしまうので、(K-1)頂点とだけ辺を結ぶ。

つまり、M>Comb(K,2)+(N-K)*(K-1)だと常に次数K以上の部分グラフが構築できてしまう。

サイズ(K+1)の完全グラフを含まなくても、条件を満たすより辺の少ないグラフが存在することに注意。
Turan Theoremは適用できない。

string NONE="NONE";
string AL="ALL";
string SOME="SOME";

class MinDegreeSubgraph {
	public:
	string exists(int n, long long m, int k) {
		
		ll N=n,M=m,K=k;
		if(K==0) return AL;
		// can create
		if(N<K+1) return NONE;
		if(M<K*(K+1)/2) return NONE;
		
		ll t=K*(K-1)/2;
		t+=(K-1)*(N-K);
		if(M<=t) return SOME;
		return AL;
	}
}

まとめ

よく通ったなこれ。