2/8 PKU

3667 Hotel

N部屋があるホテルがあり、各部屋1〜Nの番号がついている。最初ホテルは全部屋空室である。「D人の客を泊める」クエリと、「ある範囲の部屋をすべて空室にする」クエリを処理せよ。客を泊めるときは、D人が連続する番号の部屋に泊まるようにし、その中でも部屋番号が最小になるような部屋に泊める。それが不可能なときは、泊めない。

Segment Treeで、各ノードに「そこ以下が全部空室/満室か」と「そこ以下での空室情報の概要」を持たせておく。空室情報は、「左端/右端にある連続する空室数」「最大の連続する空室数」を含む。そして、ある範囲を全部空室/満室にする関数と、D人を泊める位置を求める関数を実装するとよい。

1815 Friendship

グラフが与えられる。グラフ上において、頂点Sから頂点Tまでの経路が存在しなくなるようにS,T以外の頂点を取り去るとき、取り去る頂点の数を最小化し、また取り去る頂点を出力せよ。但し辞書順最小にせよ。

頂点AをAとA'の2つに分けて考え、A->A'に流量1の辺を張る。A->Bに辺があるときには、A'->Bに流量無限の辺を張る。S'->Tの最小カット＝最大流を求めればいい。頂点Xを取り去る操作はX->X'の辺を撤去する操作に該当する。
最大流に還元した後、難しいのは「辞書順最小」の頂点集合を求めることであるが、ある頂点Xを使ってはいけない条件は、X->X'の辺を取り除いても最大フローが変わらない、すなわち残余グラフにX'->Xを含む閉路が存在することである。最初からX->X'にフローが流されていない場合は、X->X'を含むような閉路に1流すことでX->X'にフローを流すことができるが、このときは自明にX'->Xを含む閉路が存在するので無視してよい。閉路が存在するかの判定はすぐにできる。閉路が存在しない場合は、その辺を使ってよい。すなわち、T->X'->X->Sにフローを1流して押し戻し、X->X'を撤去する。これを頂点1から順に行う。