SRM388

TopCoder

250

1..Nの数で最大の素因数がk以下のものの数を求めよという問題．ふるいを作るときに最大の素因数も一緒に更新してけばいい．

500

グラフが与えられて，今各頂点に情報を1種類だけ伝えることができ，このときその情報は伝えた頂点とまわりの頂点で共有される．頂点すべてに伝えることのできる情報の種類の最大値を求めよという問題．(たとえば完全グラフならば各頂点に別々の情報を渡しておけば隣接点で情報が共有されるので答えは頂点数と等しくなる)

グラフの極小な頂点被覆集合を全部求めて，その上で下式に従ってDPを行う．

m[S|v] = max(m[S] + 1, m[S|v]) (vは頂点被覆集合, Sとvは背反)

2^15 * |極小な頂点被覆集合|の計算量がかかるのでTLEかと思ったけどSystem Testに通った．
ちゃんと計算量を評価するとO(2.8^n)ぐらいだということがわかるので実は問題なかった．

追記(極小な頂点被覆集合の個数に関して)

いま集合Sの大きさをnとし，Sの部分集合v(|v|=k)が極小な頂点被覆集合のとき, vに含まれるような集合およびvを含むような集合は2^k + 2^{(n-k)}ある，これは相加相乗平均の定理より2^k + 2^{(n-k)} \ge 2 \sqrt{2^n}
これからSの極小な頂点被覆集合は高々2^n / (2^{n/2 +1}) = 2^{n/2 -1}しかないことがわかる．