2021年3月から毎日問題が公開されている「競プロ典型90問」、皆さま解いていらっしゃいますでしょうか？
一昨日、第40問として公開された「Get More Money」が解説を読み、その後いろいろな記事を見ても理解が難しかったので整理してみました。
当然のことながらこの問題の解法に触れますので、問題に挑戦したい方はこの記事は後からお読みいただくことをお勧めします。
何が理解できなかったのか
公式解説にもある通り、この問題はいわゆる「燃やす埋める問題」というタイプの問題です。公式解説は紙面の都合もあって要点を絞って書かれているので、ほとんど予備知識がなかった筆者の場合はあまり腹落ちしませんでした。そこで「燃やす埋める問題」というキーワードを元にググってみて記事を色々と読んだのですが、どうもこの問題を解くやり方はいくつかパターンがあるようで、書いてある記事によってパターンが違ってなかなか理解が追いつきませんでした。
最終的に、以下の記事にある3パターンあるようだったので、それぞれ今回の問題に当てはめてみるとどうなるかを整理して理解を深めてみました。
- 最小カットを使って「燃やす埋める」問題を解くスライドのフォロー(診断人氏ブログ)
筆者と同じように、ネット上の記事をいろいろ読んで混乱した方は本記事に一度目を通してから読み直すと、頭の中が整理しやすくなるのではないかと思っています。
燃やす埋める問題とは
燃やす埋める問題とは以下のような問題です。
$N$個の品物があり、それぞれの物を「燃やす」か「埋める」必要がある
品物$i$を燃やすのに$x_i(\ge 0)$円、埋めるのに$y_i(\ge 0)$円かかる
また、以下の形式のルールが$M$個ある
・品物$a_j$を燃やして品物$b_j$を埋めると、罰金$c_j(\ge 0)$円かかる
最小で何円必要か
品物を処分するコストを最小化する問題のようです。
今回の典型90問の問題は以下のような問題でした。
$\ $AtCoder共和国には$N$軒の家があり、$1$から$N$までの番号が付けられています。
はじめ、家$i$の中には、現金$A_i$円と、$k_i$本の鍵（それぞれ家$c_{i,1},c_{i,2},…,c_{i,k_i}$の鍵）が置いてあり、家に入ることでこれらを回収できます。 ただし、任意の$j$ $(1\le j\le k_i)$に対して$c_{i,j}\gt i$ が保証されます。
また、家$i$に入るためには、以下の2つのことをする必要があります。
・AtCoder共和国の中に家$i$の鍵があれば、それらをすべて回収した状態にする
・料金$W$円を支払う
あなたはAtCoder共和国の家にある現金を集めることで、できるだけ多くの金額を得ようと考えています。家に入る手順をうまく決めたときに、最大で何円得するかを求めてください。 すなわち、家に入って回収した金額を$I$円、家に入るために支払った料金を$O$円として、$I−O$の最大値を求めてください。 ただし、家に入るための費用は必要ならいつでも支払えるものとします。
$\ $この問題は、予め各家から現金$A_i$円を回収しておいて、訪れないことにした家には$A_i$円返金する(支払う)と解釈することで、以下のように言い換えられます。
$N$件の家があり、それぞれの家を「訪れる」か「訪れない」必要がある
家$i$を訪れるのに$W(\ge 0)$円、訪れないのに$A_i(\ge 0)$円かかる
また、以下の形式のルールが$\sum_{i} k_i$個ある
・家$c_{i,j}$を訪れて、家$i$を訪れないと、罰金$\infty$円かかる(鍵を持っていないので)
最小で何円必要か
$\ $予め回収しておいた$\sum_{i} A_i$円から、この問題で求めた最小コストを引くと、元々の問題の答えになります。
これによって、今回の問題は「燃やす埋める問題」に帰着できました。
最小カット問題とは
解き方のパターンは最初にも触れたように3パターンあるのですが、いずれも問題の状況を有向グラフで表して「最小カット」問題に帰着させるという点では同じです。ということで、まずは「最小カット」問題を説明します。
「最小カット」というのは、自分流にイメージしやすいたとえで言えば、以下のような問題です。
- sとtを含む有向グラフがある(自国sと敵国t、他の点は街と想定)
- 各辺は容量が決まっている(街の間の輸送のキャパシティと想定)
- 各街を自国と敵国に分けて、自国から敵国方向への輸送を遮断した時に、遮断される輸送量が最小になるようにする(自国に入ってくる方は遮断しない)
出ていく方だけ遮断し、それを最小にするということを覚えやすくするために、「自国」「敵国」という表現にしてみました。
なお、この問題の点や数値の設定はプログラミングコンテストチャレンジブック(通称「蟻本」)を参考にしました。
上記の場合、11が最小値になります。
証明は省略しますが、この問題は以下のような最大流の問題として解くことができます。
- 自国拠点sから敵国拠点tへの輸送量の最大値はいくらか
この問題も確かに答えは11となっています。これを解くアルゴリズムは後述します。
最小カットへの帰着3パターン
ここまでを整理すると、今回の問題は「燃やす埋める問題」に帰着でき、「燃やす埋める問題」は「最小カット問題」に帰着でき、「最小カット問題」は「最大流問題」に帰着できるので、最終的に今回の問題は最大流の問題として解くことができます。
ネット記事を見ていて混乱したのは、「燃やす埋める問題」を「最小カット問題」に帰着する際の考え方がちょっとずつ異なるものが3パターンあり、よくわからなくなったところでした。3パターンはいずれも冒頭に紹介した以下のサイトに掲載されています。
- 最小カットを使って「燃やす埋める」問題を解くスライドのフォロー(診断人氏ブログ)
この3パターンを今回の問題に当てはめてみます。
3つのパターン全てに共通するのは、始点s、終点tと家1〜NのN+2点からなる有向グラフを作って最小カットを行うというところです。矢印や容量を何だと見立てるかがそれぞれ異なっています。
パターン1：公式解説方式
まずは今回の問題の出題者であるE869120氏による公式解説のパターンです。診断人氏ブログの[B]に該当します。
このパターンでは、訪れる家を赤(自国)、訪れない家を青(敵国)として塗り分ける問題だと見立てます。最小カットでは遮断する輸送量を最小化しますので、今回の場合はコストを輸送量と見立てます。
家1を訪れる(赤＝自国)とすると、家1とt(青＝敵国)を遮断する必要があるので、訪れた時に支払うコストである訪問料金は家1→tに割り当てます。また家1を訪れない(青＝敵国)とすると、s(赤＝自国)→家1を遮断する必要があるので、訪れない時に支払うコストである返金額を割り当てます。
鍵の条件については、家1に家2の鍵があるというのは、家1に訪れていない(青＝敵国)のに、家2に訪れる(赤＝自国)ということはできないという意味なので、このパターンになった時に遮断に無限のコストがかかるように家2→家1に∞のコストを割り当てます。
図示するとこんな感じです。
なお、問題設定は例題に記載されている以下を使用しています。
- 家は全部で5件
- 訪問料金は500円(W)
- 各家にはそれぞれ100円、300円、1200円、700円、1000円置いてある(A)
- 家1には家2と家5の鍵、家2には家5の鍵、家3には家4の鍵が置いてある(c)
これを最小カットで解くと以下のようになります。(最小カットの解き方は後述)
カットした辺の合計値2400が最小のコストになっており、最初に各家から回収した3300円との差額が最大獲得金額となります。
Javaのコードで書くと以下のような感じです。
Scanner sc = new Scanner(System.in);
int N = Integer.parseInt(sc.next());
long W = Long.parseLong(sc.next());
DinicNetwork net = new DinicNetwork(N + 2);
long sum = 0;
for ( int i = 1 ; i <= N ; i++ ) {
long A = Long.parseLong(sc.next());
net.addEdge(0, i, A); // sと家を接続
net.addEdge(i, N + 1, W); // 家とtを接続
sum += A; // 予めお金を回収
}
for ( int i = 1 ; i <= N ; i++ ) {
int k = Integer.parseInt(sc.next());
for ( int j = 0 ; j < k ; j++ ) {
int c = Integer.parseInt(sc.next());
net.addEdge(c, i, DinicNetwork.INF); // 家同士を無限大で接続
}
}
sc.close();
System.out.println(sum - net.maxFlow(0, N + 1));
DinicNetworkというのが最小カット(=最大流)を解くためのアルゴリズムで、この実装は後述します。
パターン2：診断人氏方式
先ほどから紹介している診断人氏のブログでも紹介されていますが、氏自身による以下のSlideShareの方式です。診断人氏ブログの[A]に該当します。
このパターンでは、各選択肢とその際のコストを辺に割り当てています。パターン1とよく似ていますが、パターン1では各頂点の塗り分けで選択肢を表していたのに対して、本パターンでは選択肢が辺で表現されているのがちょっと違います。
訪れる・訪れないをどの辺に割り当てるかは、元々の見立てである「燃やす」＝「訪れる」、「埋める」＝「訪れない」として、上記スライドのやり方と合わせています。その結果、パターン1とはちょっと違うグラフになっています。
ただし、左側を「訪れない」、右側を「訪れる」とすることにすれば、パターン1と全く同じグラフを解いていることになります。
解いた結果は以下の通りです。
当然のことながら、結果はパターン1と一致します。
これもJavaコードをつけておきます。(辺の割り当て方がちょっと違うだけです)
Scanner sc = new Scanner(System.in);
int N = Integer.parseInt(sc.next());
long W = Long.parseLong(sc.next());
DinicNetwork net = new DinicNetwork(N + 2);
long sum = 0;
for ( int i = 1 ; i <= N ; i++ ) {
long A = Long.parseLong(sc.next());
net.addEdge(0, i, W); // sと家を接続
net.addEdge(i, N + 1, A); // 家とtを接続
sum += A; // 予めお金を回収
}
for ( int i = 1 ; i <= N ; i++ ) {
int k = Integer.parseInt(sc.next());
for ( int j = 0 ; j < k ; j++ ) {
int c = Integer.parseInt(sc.next());
net.addEdge(i, c, DinicNetwork.INF); // 家同士を無限大で接続
}
}
sc.close();
System.out.println(sum - net.maxFlow(0, N + 1));
パターン3：Project Selection Problem
これはtokoharu氏が推奨している定式化です。診断人氏ブログの[C]に該当します。以下の記事に説明があります。
より正確には、このパターンは元の問題を「燃やす埋める問題」に帰着するのではなく、元の問題を「Project Selection Problem」に帰着し、それを最小カットに帰着します。
では、「Project Selection Problem」とは何でしょうか？以下のように定式化されています。
$N$個の要素がある。最初どの頂点も集合$B$に属しているが、これを集合$A$に移すことで利益を最大化したい。要素$i$が$A$に属する時には利得$p_i$を得るという情報が与えられる。さらに 3 つ組の列$(x_j, y_j, z_j)$が与えられ、これは$x_j$が$A$に属し、かつ$y_j$が$B$に属していた時に$z_j (\ge 0)$だけ損失をすることを意味する。得られる利得の最大値を答えよ。
言っていることはわかるのですが、Project Selectionという言葉との関係が最初よくわかりませんでした。いろいろ考えた結果、以下のような意味合いなのだろうと推測しました。
$N$個のプロジェクトがある。最初どのプロジェクトも「実施しない($B$)」予定であるが、これを「実施する($A$)」ことにして利益を最大化したい。プロジェクト$i$を実施する時には利得$p_i$を得るという情報が与えられる。さらに3つ組の列$(x_j, y_j, z_j)$が与えられ、これはプロジェクト$x_j$を実施し、かつプロジェクト$y_j$が実施しなかった時に$z_j (\ge 0)$だけ損失をすることを意味する。得られる利得の最大値を答えよ。
こうすると、実施するプロジェクトを選ぶ問題ということで、名は体を表している感じがします。
$\ $今回の場合だと、「家を訪れること」をプロジェクトとみなし、それを実施した際の利得は$A_i-W$であり、家iに家jの鍵があるというのは、家jプロジェクトを実施し(訪れる)、かつ家iプロジェクトを実施しない(訪れない)というのは、鍵がなく不可能なので無限大の損失をする、とすれば良さそうです。注意事項としては、利得$A_i-W$は負の値である可能性があるというところです。
Project Selection Problemは最大流(=最小カット)への帰着の仕方も定式化されており、以下のようになっています。
この問題に対する解は、
$$\sum_{v\in V}\max(0,p_v) - {\rm maxflow}(s,t)$$
で求めることができる。ただし、${\rm maxflow}(s, t)$とは、
1. 要素に対応する点の他に、新しくs,tの頂点を導入した$N+2$頂点のグラフの上に
2. $p_v \gt 0$であればsから$v$に容量$p_v$の辺を張り、
3. $p_v \lt 0$であれば$v$からtに容量$−p_v$の辺を張り、
4. $x_j$から$y_j$に容量$z_j$の辺を張ったときの、
5. s-t 間の最大流の値である
今回の問題でグラフを描いてみると以下のようになります。
今までと違うのは、各家について訪れる・訪れないのそれぞれのコストを出すのではなく、訪れるとした場合の利得だけを考えているというところです。なので、各家はs,tのどちらかにしか線が接続されていません。
また先ほどの式の最初のΣの部分は、意味としては正の利得だけ足した、つまり正の利得分は最初に得ていることにした、ということになります。グラフでは正の利得はs側から接続していて、やらないとした場合は(切断した場合は)利得予定だった分を損するという考え方になっているので、辻褄があっています。一方、利得が負になっているものは最初には計上しておらず、何もしなければ(=訪れなければ)そのまま損得0で、訪れることにする(=カットする)と損失として計上されるので、これも辻褄があっています。
解いた結果は以下の通りです。
パターン1,2とはちょっと様子が違いますが、結局は同じことになっています。これもJavaコードを貼っておきます。
Scanner sc = new Scanner(System.in);
int N = Integer.parseInt(sc.next());
long W = Long.parseLong(sc.next());
DinicNetwork net = new DinicNetwork(N + 2);
long sum = 0;
for ( int i = 1 ; i <= N ; i++ ) {
long A = Long.parseLong(sc.next());
if ( A - W > 0 ) {
net.addEdge(0, i, A - W); // sと家を接続
sum += A - W; // 正の利得だけ先に足しておく
} else {
net.addEdge(i, N + 1, W - A); // 家とtを接続
}
}
for ( int i = 1 ; i <= N ; i++ ) {
int k = Integer.parseInt(sc.next());
for ( int j = 0 ; j < k ; j++ ) {
int c = Integer.parseInt(sc.next());
net.addEdge(c, i, DinicNetwork.INF); // 家同士を無限大で接続
}
}
sc.close();
System.out.println(sum - net.maxFlow(0, N + 1));
パターンの比較
で、結局どのパターンで考えるのが良いのか、ということですが、そもそもこの方法をちゃんと学んだのが今日初めてなのでまだ使い分け方がよくわかっていないのが正直なところです。もう少しこの手の問題の経験を積んでから評価するのが良いと思いますが、初見では以下のような印象を持ちました。
- パターン1は塗り分け問題として考えやすいが、コストをどこにマッピングするかが混乱しやすそう
- パターン2は辺＝選択肢というのが直感的だが、頂点間を結ぶ方向が混乱しやすそう
- パターン3は実行する・しないというイメージがつきやすいが、解き方含めてきちんと覚えておく必要がありそう
最大流を解くアルゴリズム(Dinic法)
ここまでで最小カット＝最大流への帰着のさせ方がわかったので、最後に最大流を解くアルゴリズムを紹介しておきます。基本的には蟻本の受け売りです。
以下3つのステップを経て、高速なDinic法へ到達します。(実際にはより高速な解法もあるようです)
Step1：貪欲法(嘘解法)
この方法は嘘解法なので正しい解は導けないのですが、正しい解を求める際のベースになるのでまずはここから紹介します。基本的には以下のようなやり方です。
- sからtに向けて、正の容量の辺だけを使ったDFSで経路を探索
- その経路に目一杯流す(正確にはその経路上の容量の最小値の分だけその経路に流す)
- sからtへの容量が残った経路がなくなるまで繰り返す
Step2：Ford-Fulkerson法
さて、Step1の貪欲法は嘘解法で、見つけた10という値は実は最大値ではありません。最初に見つけた経路でs→A→B→tを5流してしまいましたが、最終図をじっと眺めてみると、流すのを4に留めておけば、次のs→A→C→tで6流すことになり、その後さらにs→B→tに1流せる余地が残っていたはずです。
Step1の最後の状況と、上記のようにさらに1流した状況を比べると、A→Bに流れている5の分を1だけ押し戻すということを許容し、Step1の最後の状況に対してs→B→A→C→tに1流したことに相当します。このような押し戻しを加味して貪欲法で求めるのがFord-Fulkerson法です。
- sからtに向けて、正の容量の辺だけを使ったDFSで経路を探索
- その経路に目一杯流す(正確にはその経路上の容量の最小値の分だけその経路に流す)
- その際に、後で押し戻せるように逆向きに同じ容量のパスを追加する
- 追加したパスも含めて、sからtへの容量が残った経路がなくなるまで繰り返す
$\ $証明は省略しますが、これは正しい解法になっています。このアルゴリズムは、最大流量を$F$、$|E|$を辺の数とすると、DFS部分が1回あたり$O(|E|)$、運悪く毎回1だけ流せるパスを見つけてしまった場合にDFSがおよそ$F$回実行されることになるので、最悪のケースで$O(F|E|)$で動作します。
Step3：Dinic法
Dinic法はFord-Fulkerson法のDFS部分にルールを作って無闇に実行しないようにすることで、実行オーダーを最大流量$F$ではなく、頂点数と辺の数に依存するようにしたものです(と筆者は解釈しました。適切でなければご指摘ください)。
細かい説明は省略しますが、以下のようなアルゴリズムになります。
- sからBFSで各頂点にsからの距離(level)を付与
- その結果、tにたどり着けなくなっていればそこまでで流した量が最大流量
- sからtに向けて、正の容量の辺だけを使い、かつ距離が狭義単調増大するDFSで経路を探索
- その経路に目一杯流す(正確にはその経路上の容量の最小値の分だけその経路に流す)
- その際に、後で押し戻せるように逆向きに同じ容量のパスを追加する
- 追加したパスも含めて、sからtへの容量が残った経路がなくなるまでDFSを繰り返す。その際に既に調べた経路はもう調べない
- DFSで経路が見つからなくなったら、BFSからやり直す
3つ目の図で、s→A→C→tも残っているように見えますが、C→tが両方level=2なので狭義単調増加になっておらず、DFSでの経路はなくなったので、BFSからやり直しになっています。
このアルゴリズムを実装したJavaコードを以下に貼っておきます(蟻本のJava移植版です)
public class DinicNetwork {
static final long INF = Long.MAX_VALUE;
int[] level = null;
int[] iter = null;
ArrayList<Edge> edges[] = null;
public class Edge {
int to = 0;
long cap = 0;
int rev = 0;
Edge( int to, long cap, int rev ) {
this.to = to;
this.cap = cap;
this.rev = rev;
}
}
public DinicNetwork(int N) {
level = new int[N];
iter = new int[N];
edges = new ArrayList[N];
for ( int i = 0 ; i < N ; i++ ) {
edges[i] = new ArrayList();
}
}
public void addEdge(int from, int to, long cap) {
edges[from].add(new Edge(to, cap, edges[to].size()));
edges[to].add(new Edge(from, 0, edges[from].size() - 1));
}
private void bfs(int s) {
Arrays.fill(level, -1);
Deque<Integer> queue = new ArrayDeque<Integer>();
level[s] = 0;
queue.add(s);
while ( !queue.isEmpty() ) {
int v = queue.poll();
for ( Edge e : edges[v] ) {
if ( e.cap > 0 && level[e.to] < 0 ) {
level[e.to]= level[v] + 1;
queue.add(e.to);
}
}
}
}
private long dfs(int v, int t, long f) {
if ( v == t ) return f;
while ( iter[v] < edges[v].size() ) {
Edge e = edges[v].get(iter[v]);
if ( e.cap > 0 && level[v] < level[e.to] ) {
long d = dfs(e.to, t, Math.min(f, e.cap));
if ( d > 0 ) {
e.cap = add(e.cap, -d);
edges[e.to].get(e.rev).cap = add(edges[e.to].get(e.rev).cap, d);
return d;
}
}
iter[v]++;
}
return 0;
}
private long add(long a, long diff) {
return a == INF ? INF : a + diff;
}
public long maxFlow(int s, int t) {
long flow = 0;
while ( true ) {
bfs(s);
if ( level[t] < 0 ) return flow;
Arrays.fill(iter, 0);
long f = 0;
while ( (f = dfs(s, t, INF)) > 0 ) {
flow += f;
}
}
}
}
アルゴリズムの説明の中で、DFSについて「その際に既に調べた経路はもう調べない」と書きましたが、iterという配列で実行したindexの位置を記録している部分がそれにあたります。
$\ $このアルゴリズムの計算量は、頂点数$|V|$、辺の数$|E|$として、$O(|E||V|^2)$となっていますが、この計算量から見積もるよりもだいぶ高速に動くようです。
計算量の詳細については以下のサイトが詳しいのでご参照ください。