noshi91のメモ

データ構造のある風景

JOI 2022/2023 春季トレーニング 警備員 (Security Guard)

アルゴリズム

解法の説明は公式解説に任せるとして、いくつかの事実についての証明を書きます。 公式解説を見れてないのでどこが証明されてどこが証明されてないか分からない (もしかすると方針自体違うかも)。 治安が低いほど S が大きいのが混乱の元なので、治安という言葉は全部 S に置き換える。

使う辺を固定した場合に必要な警備員の数

使う辺を固定した場合 (= 廃止しない船を決めた場合) に必要な警備員の人数を考える。 まず、各船につき \min ( S _ x , S _ y ) の警備員は明らかに必要である。 以降警備員と言ったら、これに追加して必要となる警備員のことを指すものとする。

L ( s ) を、 S が s 未満である頂点による誘導部分グラフと定義する。 すなわち、 L ( s ) := G \lbrack \lbrace v \mid S _ v \lt s \rbrace \rbrack である。 また、 S の最大値を S _ { \max } とする。 このとき、追加で必要な警備員の数は

\begin{align} W := \sum _ { s = 0 } ^ { S _ { \max } } L ( s ) \text{ の連結成分の個数 } \end{align}

である。

証明

セキュリティ条件を以下のように言い換える。

x から y への航路は | S _ x - S _ y | の長さをもち、航路上で S が線形に変化するものとする。 船は S が増える方向に 1 進むたびに、その区画の中点に警備員を 1 人置き去りにしなければならない。 S が減る方向に 1 進むと、そこを通るときに置き去りにした警備員を回収することができる。

必要性

W 人未満の警備員であらゆる客を輸送可能として矛盾を導く。 船は S の小さい方に停泊しており、警備員は全ていずれかの島に待機しているとしてよい。

ここで、警備員に階級というパラメータを導入する。 階級は以下のような手順で定められる。

  1. 最初、全ての警備員は階級が未定である。
  2. s = 0 , 1 , \dots , S _ { \max } の順に以下の操作を繰り返す。
    • L ( s ) のすべての連結成分 C について、 C 内の島に待機している階級が未定の警備員がいるなら 1 人選んで階級を s と定める。
  3. 最後まで階級が未定だった警備員は階級 \infty とする。

置き去りにする警備員を選ぶときは、常に船の中で階級が最小の警備員を選ぶものとしてよい。

主張

階級が s の警備員は S が s 未満の領域にしか存在できない。

主張の証明

背理法を用いる。 階級が s の警備員 g を S = s となる場所まで連れて行く手順が存在したとする。 そのような手順の中で s が最小であり、その中で手数が最小のものをとる。 警備員 g は最初 S \lt s な場所に居るから、どこかで S = s - 1 から S = s に移動したことになる。 このとき置き去りにされた警備員は g の階級以下の階級を持つはずだが、 s - 1 以下とすると s が最小になるように手順を選んだことに矛盾する。 したがって g とは別の階級 s の警備員が置き去りになっている。 しかし、階級 s の警備員が 2 人で同じ場所に存在するためには、どちらかは L ( s ) のうち最初に自身が属していた連結成分から外に出ていることになる。 これは手順の最短性に矛盾する。 \blacksquare

さて、警備員が全体で W 人未満であるから、階級の割り当ての際に階級が未定の警備員が存在せず、新たに階級を割り当てられなかったようなタイミングが存在する。 それが s = s ^ * のときであり、連結成分は C ^ * だったとする。 すると、 C ^ * 内には階級が s ^ * 以上の警備員が存在しない。 C ^ * は全体集合ではないから ( \because s ^ * \leq S _ { \max } )、 C ^ * 内から C ^ * 外に客を運ぶことができる。 そのような手順において、船が S = s ^ * - 1 から S = s ^ * に移動する最初のタイミングを考える (客を運ぶので必ず存在)。 主張より、そのとき置き去りになる警備員の階級は s ^ * 以上でなければならない。 しかし C ^ * 内部にはそのような警備員は居ないから、 C ^ * の外から警備員を連れてくる必要がある。 その警備員が C ^ * に入るためにはまず船を C ^ * 内から外に出す必要があり、そのような最初のタイミングを考えたのでこれは起こらない。 よって矛盾する。 \blacksquare

十分性

各 s = S _ { \min } + 1 , \ldots , S _ { \max } と L ( s ) の各連結成分について、連結成分内の好きな場所に階級 s の警備員を 1 人配置する。 このとき必要な警備員は W 人となるが、これで任意の客を輸送できることを示す。

任意の s ^ * ~ ( S _ { \min } \leq s ^ * \leq S _ { \max } ) と L ( s ^ * + 1 ) の連結成分 C ^ * について、以下の命題が成り立つことを示せばよい。

  • C ^ * 内の任意の 2 点について、階級が s ^ * 以下の警備員だけで客を輸送可能である

s ^ * についての数学的帰納法を用いる。

客を輸送した後にその手順を逆回しにして警備員を初期配置に戻せることを考えると、 C ^ * 内の任意の辺について、その辺に沿って双方向に客を輸送できることを示せばいい。 さらに、仮想的な客を輸送した後に逆回しで本来の客を輸送することを考えれば、辺についてどちらか一方の向きに輸送できれば十分である。 S = s ^ * である 2 点をつなぐ辺の間で輸送できることは明らか。 また、 S \lt s ^ * である 2 点をつなぐ辺の間で輸送できることは帰納法の仮定から従う。 したがって、 S _ x \lt s ^ * , ~ S _ y = s ^ * なる点 x , y をつなぐ辺に沿った輸送が問題となる。

s = s ^ * , s ^ * - 1 , \dots , S _ x + 1 の順に以下をおこなう。

  1. L ( s ) の連結成分のうち x が属するものを C _ x とする。
  2. C _ x 内に階級 s の警備員 g が存在するので、その警備員を客に見立て、階級 s - 1 以下の警備員だけで g を x に運ぶ。これは帰納法の仮定から実行可能である。
  3. 手順を逆回しにして、階級 s - 1 以下の警備員を初期位置に戻す。

すると階級 s ^ * , s ^ * - 1 , \dots , S _ x + 1 の警備員が x に集まる。 これは丁度 S _ y - S _ x 人なので、これを使って客を乗せた船を x から y に移動させることができる。 \blacksquare

以上をまとめると、各船に常駐する警備員も含めて必要な警備員の数は

\begin{align} \sum _ { \lbrace x , y \rbrace \in E } \min ( S _ x , S _ y ) + \sum _ { s = 0 } ^ { S _ { \max } } L ( s ) \text{ の連結成分の個数 } \quad \cdots \bigstar \end{align}

となる。

使う辺を木としてよい理由

連結性は明らかに必要なので、連結だが木ではないような辺を採用した場合に、それが最適解にならないことを示す。 辺のコストを \max ( S _ x , S _ y ) とした場合の、採用した辺だけでの最小全域木を作る。 すると、 \bigstar における第 1 項は減少する一方で第 2 項は変わらない。 これはクラスカル法を考えることで証明できる。 よってこの木を採用した方が得である。

注意: より得な木の選び方がある可能性は否定されないので、 \max ( S _ x , S _ y ) についての最小全域木は答えにはならない

使う辺が木の場合の \bigstar の変形

使う辺を木にした場合、 \bigstar はより扱いやすい形に変形できる。 S が最大となる点を選び、それを根とする根付き木にする。 \bigstar の第 1 項は、 x , y のうち親である方に支払わせる。 第 2 項は、各連結成分の LCA の親に支払わせる。 すると、各頂点 v の支払いは丁度 S _ v \times v \text{ の子の個数 } となることが分かる。 よって \displaystyle \bigstar = \sum _ { v } S _ v ( \mathrm{deg}(v) - 1 ) + S _ { \max } である。

貪欲法の証明

N 頂点の辺重み付き無向グラフがあり、各辺は赤または青に塗られている。 赤辺だけで連結であり、青辺だけでも連結とする。 以下の用語を定義する。

  • k -ST : 赤辺を丁度 k 本使った全域木
  • k -MST : 重み最小の k-ST

仮定より、任意の 0 \leq k \leq N - 1 について k-ST , k-MST は存在する。

補題

任意の 1 \leq k \leq N - 1 と X \colon k -MST について、ある ( k - 1 ) -MST が存在して、 X とのハミング距離が 2 。

証明

X ハミング距離が最小となる ( k - 1 ) -MST をとり、 Y とする。 グラフの全域木全体はマトロイドであり、以下の交換公理が成り立つ。

任意の e \in X \setminus Y に対し、ある f \in Y \setminus X が存在し、 X - e + f と Y - f + e はいずれも全域木となる。

ここで e を赤辺に選ぶことが必ずできる。 そのとき f が赤辺になったとすると、 X - e + f は k -ST であり、 Y - f + e は ( k - 1 ) -ST である。 しかしこれらのコストの和は変わっていないから、それぞれ k -MST、 ( k - 1) -MST になっていることが分かる。 Y - f + e は Y よりも X とのハミング距離が小さいから、 Y の取り方に矛盾する。 したがって f は必ず青辺となり、 X - e + f は ( k - 1 ) -ST となる。 同様の議論によりこれは ( k - 1 ) -MST でもあり、 X - e + f は X とのハミング距離が 2 であるから求める結果を得た。 \blacksquare

元の問題 (警備員) においては、元からある船を青辺、新たに追加する船を赤辺と思って上記の補題を適用すれば、貪欲法の証明が得られる。