olpheの競プロ帖

競プロ問やアルゴリズム等の考察します

2017-05-17から1日間の記事一覧

タクシー(14予選5)

N個の町、K本の道がある。各町にはタクシー会社が存在し、それぞれ決められた数までの道を移動できる。また、料金も決まっている。 1~Nに移動するために必要なコストの最小値を求める問題。 基本的にはdijkstraでよいが、各頂点を訪れるごとに移動できる場…

魚の生息範囲(13予選5)

N種類の魚がいて、それぞれの生息範囲が直方体で与えられる。 同時にK種類の魚が存在しうる領域の体積を求めよという問題。 まず、座標の範囲が0~1000000と非常に大きいにもかかわらず、魚の種類は最大でも50なので無駄っぽい。なのでそれぞれについてソート…