February 2012 Cook-off

結果。
2/5完。整理できてないままコーディングを始めると混乱すると分かっているのになぜ書き始めてしまうのか。
数学ゲーの方が簡単らしいけどグラフに逃げた。解けたので結果オーライだけど、戦略としてはよくない。

CodeChef-DAILY : Daily Train

問題概要(適当)

全探索すれば解ける問題。

CodeChef-BEARS : Bears and Bees

問題概要

G=(V,E)からG'を以下のように得る。G'=(V',E')とすると、V'=Eで、辺aと辺bがGで同じ頂点に接続していたら(a,b) in E'となる。今、グラフG[0]=(V,E)(|V|, |E|<1000)がある。G[0]を変換してG[1]を得る。G[1]を変換してG[2]を得る。G[2]を変換してG[3]を得る。G[3]の頂点数と辺数を求める問題。

解法

まず、|E|<1000なのでG[1]は陽に持てる(らしいけど実際は定数倍でTLEした)。次に、G[2]の次数列を計算する。G[2]の次数列が計算できたらG[3]の頂点数が分かる(次数列の和の半分)。また、G[3]の次数列そのものは分からなくてもG[3]の次数列の和はsum d[i]*(d[i]-1)で求めることができるので、G[3]の頂点数はG[3]の次数列の和の半分となる。