よく正解できたな…。
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; } }
まとめ
よく通ったなこれ。