1250 1251

年末なのでPKUやって終わることに。

1250

人のINとOUTの列が与えられる。N個のスペースがあって、INかOUTの時点ですいていれば利用できる。利用できなかった人数は何人か答えよ、という問題。

書いてある通り実装するだけ。(多分英語の方が難しい問題。)

1251

N都市間の道のメンテナンスコストが与えられる。各都市の間で移動できるように道を残しつつ、メンテナンスコストができるだけ小さくなるように道を除くことを考えるとき、最小コストを答えよ、という問題。

MSTの問題。プリムの方が実装が楽なような気がしてならない。しかもこの問題はO(N^3)で問題なく通ったりする。ちゃんとライブラリ持っておいた方がいいかも。