yukicoder No.119 旅行のツアーの問題 解説

余談が本編

問題

リンクはこちら

概要

$N$ 個の国があり、それぞれの国 $i \; (0 \leq i < N)$ に対して以下の行動のうち一つを選ぶ。

• 選択 $p$ : ツアー旅行に行く。利得 $b_i$
• 選択 $q$ : 個人旅行に行く。利得 $c_i$
• 選択 $r$ : 行かない。利得 $0$

ただし、いくつかの国のペア $i, j$ に対して「国 $i$ のツアー旅行に行くならば、国 $j$ の個人旅行に行ってはならない」という形の制約が課される。得られる最大の利得を求めよ。

解法

パッと見た感じだとProject Selection Plobrem（PSP、「燃やす埋める」などとも呼ばれています）を使って解けそうだけど、取りうる状態が三つあるので少し工夫が必要です。ここでは二種類の方針を紹介します。

注意 :「燃やす埋める」という名前を嫌う人がいるので記事中ではPSPと表現していますが、この記事でやっていることは紛れもなく「燃やす埋める」です（考え方が少し違うらしい）。本物のPSPについてはこちらの記事で解説されています。

1. 辺の切断

まず多くの人が解説している方針を紹介します。

一般的にはPSPは頂点の割り振りに関する問題として捉えられますが、ここでは「辺をいくつか選んで切断する」という、本来の最小カット問題に近い形式で問題を解釈してみます。

各 $i$ について、無条件に利得 $b_i + c_i$ が得られるとした上で、始点 $\mathrm{S}$ から頂点 $i$ にコスト $b_i$ 、頂点 $i$ から終点 $\mathrm{T}$ にコスト $c_i$ の辺を張ります。すると、 $\mathrm{S}$ から $\mathrm{T}$ を到達不可能にするためには、少なくともこのどちらかの辺は切らなくてはなりません。最終的に得られる利得に注目すると、前者を切ることが $q_i$ 、後者を切ることが $p_i$ 、そしてどちらも切ることが $r_i$ に相当していることがわかります。

次に禁止制約「 $p_i \to \lnot q_j$ 」を考えると、これは $p_i$ と $q_j$ が同時に選ばれたときに $\mathrm{S}$ から $\mathrm{T}$ への経路が残っているようにすればいいので、 $i$ から $j$ にコスト $\infty$ の辺を張ることで表現できます。

しかし、これだとサンプル3のようなケースで失敗してしまいます。

国 2 に行かないので本当は大丈夫なはず

禁止制約の辺が連鎖して、本来許されるはずの選択までブロックしてしまっています。そこで、制約の連鎖が起こらないように、各頂点を2つずつに分割して以下のように辺を張り直してみます。

天才

$i_1$ と $i_2$ は元々同じ頂点を表しているので、これらは分断されないようにコスト $\infty$ の辺で繋いでおきましょう。こうすることで、禁止制約は上流から下流への一方通行になり、連鎖することを防げます。

このグラフで始点から終点への最小カット（=最大流）を求めればいいです。最小カットのコストを $K$ とすると、最終的な答えは $\sum_{i} (b_i+c_i) - K$ となります。

let u = |i| { 2 * i }; // i_1
let v = |i| { 2 * i + 1 }; // i_2
let source = u(n);
let sink = v(n);
let mut ans = 0;
let mut din = Dinic::new();
for &(i, j) in &cl { // 禁止制約
  din.add_edge(u(i), v(j), INF);
}
for (i, &(b, c)) in plans.iter().enumerate() { // 各選択の報酬
  ans += b + c;
  din.add_edge(source, u(i), b);
  din.add_edge(u(i), v(i), INF);
  din.add_edge(v(i), sink, c);
}
ans -= din.max_flow(source, sink).0;

2. 頂点の分配

続いて、一般的なPSP同様、頂点を始点側と終点側に割り振る問題として捉える方針で解いてみます。 ソースを $\text{True}(\top)$ 、シンクを $\text{False}(⊥)$ として、頂点を割り振っていきます。

以下の二頂点を用意します。

• $u_i$ : 国 $i$ のツアー旅行に行くか、国 $i$ を訪れない（$p_i \lor r_i$）
• $v_i$ : 国 $i$ のツアー旅行に行く（$p_i$）

こうすることで、$u_i$ と $v_i$ の真偽と行動選択が以下の通りに対応します。

• $u_i \land v_i = (p_i \lor r_i) \land p_i = p_i$
• $u_i \land \lnot v_i = (p_i \lor r_i) \land \lnot p_i = r_i$
• $\lnot u_i \land v_i = \lnot (p_i \lor r_i) \land p_i = ⊥$
• $\lnot u_i \land \lnot v_i = \lnot (p_i \lor r_i) \land \lnot p_i = \lnot p_i \land \lnot r_i = q_i$

よって、 $u_i, v_i$ の割り当てに応じたコストは以下の表の通りとなります。

$$ \begin{array}{c|cc} & u_i & \lnot u_i \\ \hline v_i & -b_i & \infty \\ \lnot v_i & 0 & -c_i \\ \end{array} $$

無条件で $b_i + c_i$ の利得が得られることにすると、以下のようにコストは全て正の値となります。

$$ \begin{array}{c|cc} & u_i & \lnot u_i \\ \hline v_i & c_i & \infty \\ \lnot v_i & b_i + c_i & b_i \\ \end{array} $$

ちゃんと劣モジュラになってるので、これは通常の2変数に関するコストとして表現可能です。例えばこんな感じ。

さらに、追加制約「$p_i \to \lnot q_j$」は、$v_i \to u_i$ を用いることで

$$ \begin{aligned} p_i \to \lnot q_j & \Leftrightarrow (u_i \land v_i) \to \lnot (\lnot u_j \land \lnot v_j) \\ & \Leftrightarrow v_i \to (u_j \lor v_j) \\ & \Leftrightarrow v_i \to u_j \end{aligned} $$

と言い換えることができるので、以下のように辺を張ればいいです。

これで始点から終点まで流せばOKです。最終的な答えは $\sum_{i} (b_i+c_i) - K$ です。

let u = |i| { 2 * i };
let v = |i| { 2 * i + 1 };
let source = u(n);
let sink = v(n);
let mut ans = 0;
let mut din = Dinic::new();
for &(i, j) in &cl { // 禁止制約
  din.add_edge(v(i), u(j), INF);
}
for (i, &(b, c)) in plans.iter().enumerate() { // 各選択の報酬
  ans += b + c;
  din.add_edge(v(i), u(i), INF);
  din.add_edge(source, u(i), b);
  din.add_edge(u(i), v(i), b + c);
  din.add_edge(v(i), sink, c);
}
ans -= din.max_flow(source, sink).0; 

提出

解法 1(Rust)
解法 2(Rust)

余談

初見で解いていたとき、「三種類の値を取るときは、各要素に対して二つの頂点を用意していい感じに包含関係を入れるといい」という話を何となく聞いたことがあったので、二種類の命題

• $x_i$ : 国 $i$ を訪れる（$p_i \lor q_i$）
• $y_i$ : 国 $i$ のツアー旅行に行く（$p_i$）

を頂点として作ることにしたのですが、間違いでした。$p$ と $q$ には「国を訪れる」という分かりやすい共通項がある上、元問題文では禁止制約があたかも「国を訪れる」という括りがあるかのように表現されていたために纒めたくなってしまいましたが、実際には完全に別の事象として捉えるべきでした（というか実際にそう）。まんまと罠にかかりました。

$x, y$ の真偽もうまく $p, q, r$ に対応して、コストも劣モジュラになりますが、禁止制約が「 $y_i \to \lnot x_j \lor y_j$ 」となってしまい、グラフで表現することができません。

包含関係をどのように設定すればうまくいきそうか、を判断する材料として、二種類の方針を紹介します。

1. 包含関係のある条件の一般的な表現

こちらの記事の後半で紹介されている考え方です。 $k$ 状態を取りうる変数を、今回作ったグラフのように

• $a_1 = s_1$
• $a_2 = s_1 \lor s_2$
• $\vdots$
• $a_{k - 1} = s_1 \lor s_2 \lor \cdots \lor s _ { k - 1 }$

という $k - 1$ 個の頂点 $a_1, a_2, ..., a _ { k - 1 } $ で表現すると、グラフの形は以下のようになります。

a_k-1 -> a_k-2 -> ... -> a_2 -> a_1

$a_k = s_1 \lor s_2 \lor \cdots \lor s _ k$ は必ず $\top$ になるので、頂点を用意する必要はありません。また、 $a _ {i - 1} \to a _ i$ が成り立つので、 $a _ {i-1} \land \lnot a _ i$ という状態に無限のコストがかかるように逆向きの辺を張っています。

まずは一つの変数のみに着目します。 1変数関数は必ず劣モジュラであるので、適切に辺コストを割り振りさえすればこのグラフによって各 $s _ i$ のコストは必ず表現できます。 例えば $s_i$ を選んだ際のコストを $\theta(s _ i)$ として、以下のように対応していたとします。

$$ \begin{array}{c|cccc} i & 1 & 2 & 3 & 4 \\ \hline \theta(s _ i) & -5 & 6 & 2 & -8 \\ \end{array} $$

このとき、任意の定数 $w$ を用いて、無条件に $w$ の報酬がもらえるとした上で、以下のように辺のコストを定めることで $\theta$ が表現できます。

$a _ i \land \lnot a _ { i - 1 } \to s _ i $ が成り立つので、$ a _ i , a _ { i - 1 } $ 間の辺を切るときには 「その選択肢のコスト $\theta(s _ i)+$ 無条件にもらえてしまった報酬 $w$」のコストがかかるようにします。 $w$ はどの辺を選んでも打ち消される値なのでなんでもよく、適切な値をとることで負辺をなくすことができます。

次に、全ての変数 $i$ に対してこれらの頂点 $a ^ { i } _ {d} \;( 1 \leq d < k ) $ を用意したあと、ある頂点から別の頂点に張った辺がどのような意味を持つのかを考えてみます。 $a ^ { i } _ { n }$ から $a ^ { j } _ { m }$ へとコスト $c$ の辺を張ってみます。

辺は適当に省略しています

このコストがかかるのは $a ^ { i } _ { n } \land \lnot a ^ { j } _ { m }$ のときです。つまりこの辺は「 $i$ が $s_1, s_2, \ldots, s _ n$ のどれかであるとき、$j$ が $s_1, s_2, \ldots, s _ m $ のどれかでないならコスト $c$ がかかる」と翻訳できます。 先程挙げたブログの言葉を借りてこれを一般化すると、包含関係のある集合 $A_1 \subset A_2 \subset A_3 \subset \cdots$ に変数 $v_1, v_2, v_3, \ldots$ を配置していくとき、「 $v _ i \in A _ n$ かつ $v _ j \not \in A _ m $ ならコスト $c \;(> 0)$ がかかる」という条件を表現できます。

これを踏まえて元の問題の禁止制約「$p _ i \to \lnot q _ j$」を「$p _ i \to p _ j \lor r _ j$」と解釈すれば、 $p, p \lor r$ という括りを作ることで上手くいきそうだ、とあたりをつけることができるかと思います。

2. Monge行列への意識

本問題では、禁止制約に関するコスト行列は以下のようになっています。

$$ \begin{array}{c|ccc} & p_i & q_i & r_i \\ \hline p_j & 0 & 0 & 0 \\ q_j & \infty & 0 & 0 \\ r_j & 0 & 0 & 0 \\ \end{array} $$

これがMongeになるよう選択肢を並び替えます。

$$ \begin{array}{c|ccc} & p_i & r_i & q_i \\ \hline p_j & 0 & 0 & 0 \\ r_j & 0 & 0 & 0 \\ q_j & \infty & 0 & 0 \\ \end{array} $$

するとここをこうまとめたくなります。（？）

$$ \begin{array}{c|c:cc} & p_i & r_i & q_i \\ \hline p_j & 0 & 0 & 0 \\ r_j & 0 & 0 & 0 \\ \hdashline q_j & \infty & 0 & 0 \\ \end{array} $$

「 $p_i \land \lnot q_j$ 」 $=$ 「 $p_i \land \lnot (p_j \lor r_j)$ 」の場合にコストをかけたいので、 $p, p \lor r$ という二種類の頂点があればグラフで表現出来そうだな、という風に思える、らしいです。また、このようにすると $q, q \lor r$ という二種類の頂点を作ってもなんとかなりそうに思えますね（実際なんとかなる）。

正直この方法にどのくらい汎用性があるのかは分かりません。ただ、これに限らず、グラフ表現をする上でコストが劣モジュラであることが必要だということを常に念頭におきながら問題を整理することで、なんとなく見通しを立てやすくなるのかもしれません。

参考記事

• 『燃やす埋める』と『ProjectSelectionProblem』 - とこはるのまとめ
• Project Selection (燃やす埋める) 周りの話についてもう少し考えた - とこはるのまとめ
• 最小カットとProject Selection Problemのまとめ - うさぎ小屋
• 燃やす埋める問題と劣モジュラ関数のグラフ表現可能性 その① - 私と理論