634.1

なんかめんどくさいだけに見えた。

250

商品の買われた個数が与えられる。それぞれの人が高々一個しか各商品について購入していない。N人の人がいるとき、K個以上の商品を購入した人の数の最小値を答えよ、という問題。

K個以上買った人は全部一個ずつ買ったことにしてしまえば最適なのは自明。後は、残りの商品を残りの人でK-1個ずつ買うことができるかを考える。残りの人数よりもたくさん残っている商品はないはずなので、購入できないパターンはないはず、らしい。あんまり自明じゃなかったので、愚直にシミュレーションするステップを高速化したら通りましたよ、という感じ。うまくいかないケースも頑張れば作れるのかも？

500

N個の点があるので、二色に色分けして、同じ色の点を任意に線分で結ぶ。違う色の線分が交差しないようにしたいとき、各線分の得点表が与えられるので、総得点を最大化せよ、という問題。

どれかを使うと使えなくなるとか、そういう条件があちこちにいるっぽいので、多分フローとかになるんじゃないかなぁ、程度には思ったけれど、良く分からない。

1000

N個の点があるので、直線で二つのグループに分けたときに、異なるグループの点との距離の二乗和の合計の最大値を答えよ、という問題。

ある点を決めて、その点との角度でソートしてやると、その点を通る直線で適当に点集合を二等分できる。後はその直線を回転させていけば、変化のある点は一個なので、N^3くらいの計算量になる。多分これじゃ通らないので、何か適当に最適化するんだろうなぁ、程度のところまで。