357.1

250 (level1)

N人のお客様を誘致するのにCだけコストがかかる、というパッケージが何種類か与えられるので、少なくともK人のお客様を誘致するのにかかる最小のコストを求めなさい、という問題。

言わずもがな、単純DPでしたとさ。

500 (level2)

WEBサイトのランクを計算せよという問題。リンク関係が与えられるので、リンク元のスコアを計算してからそれを足し込んでいく。

循環パスが出てきたら切るらしいけれど、
その切り方を理解できていない。
(いつかちゃんとやる、かも。)

1100 (level3)

正方形の上に傷がたくさんついてるから、傷の付いていない長方形エリアの最大面積を求めなさい、という問題。上の方の人達にしてみれば、どこかで解いたことあるんだろうなぁ。

多分x軸方向でソートして、区間グラフを取りつつ、
2点ペアを作ってスイープ。
とやるとN二乗なのでTLEするんだろうなぁ。