11/23 PKU

1201 Intervals

いくつかの整数の区間と、それぞれに含まれるべき整数の個数が与えられる。整数の集合で、これらの区間についての制約をすべて満足しかつ、集合の大きさが最小のものの大きさを求めよ。

累積和をとると線形計画問題になる。この線形計画問題は「やさしい」問題で、最短路問題に帰着される。負辺があってうれしくないが、Dijkstraを適当に改造したのを使ったら通った。

1716 Integer Intervals

各区間に含まれる整数の個数が2個になっただけで↑と全く同じ問題

3352 Road Construction

3177と全く同じ問題で3177と全く同じコードで通る

1647 One-move checkmate

チェス盤の上に白のキングとクイーン、黒のキングの３駒しかない。クイーンを１回動かしてチェックメイトにする方法を求めよ。

やるだけ

1578 Instruens Fabulam

問題文に従って表を作れ。

やるだけ

2215 Parliament

２次元累積和やるだけ