KMCoder SRM Beta 4
250 (SPOJ HANGOVER)
PKU1003なので有名問題
500 (SPOJ OPTM)
各ビットごとに最小カット
最小カットに使う辺を具体的に求める段階で混乱して組み終わらなかった
1000 (SPOJ MOBILE)
まずはまともな行列であることを確認
3つ以上に分岐している棒は同じ高さにある複数の棒とみなしてよいので、2分木っぽくとらえる
集合と高さの上限を状態にして再帰。最初は全体・INFではじめる
行列のうち適当な1行だけなめて最大値を求めれば最も高い棒がわかるので、見るべきところがいい感じに節約できて、結局O(N^2)で解ける
Result
245.20 + Opened + 455.19 = 700.40
1位
ついに500を落としてしまったorz