SoundHound Inc. Programming Contest 2018 (春)
Updated:
SoundHound Inc. Programming Contest 2018 (春)
Source codes
Solutions
A - SoundHound
やるだけ。
B - 音量
やるだけ。
C - 広告
やったこと
最初は、 $i+j$ 偶数を奇数で分けるだけじゃんと思っていた。しかしそうではないことはすぐに気づいた。一番上と一番左が決まれば順次決まるパターンかと思ったけどそうでもなかった。そこで思いついたのは、最大フロー最小カットだ。しかしどう実装したらいいのかわからなかった。正解例を見るとどうやら最大フロー最小カットが正解のようだ。眠いので後で解読する。
基本知識
以下は、プログラミングコンテストチャレンジブック第 2 版 p.198 - 199 に書かれている。
定義 1 $G = (V, E)$ を無向グラフとする。
- 辺集合 $M \subset E$ が マッチング であるとは、 $M$ の任意の $2$ つの辺 $(u, v), (u’, v’)$ に対し、 $u, v, u’, v’$ が全て異なることをいう。
- 辺集合 $F \subset E$ が 辺カバー または 辺被覆 であるとは、任意の $u \in V$ に対し、 $v \in V$ が存在し $(u, v) \in E$ となることをいう。
- 点集合 $S \subset V$ が 安定集合 または 独立集合 であるとは、任意の $u, v \in S$ に対し $(u, v) \not\in E$ であることをいう。
- 点集合 $S \subset V$ が 点カバー または 点被覆 であるとは、任意の $e = (u, v) \in E$ に対し $u \in S$ または $v \in S$ が成立することをいう。
定理 2 $G = (V, E)$ をグラフとする。
- $G$ は孤立点がないものとする。辺集合 $M \subset E$ は最大マッチングであるとする。辺集合 $F \subset E$ が最小辺被覆であることする。このとき、 $\lvert M \rvert + \lvert F \rvert = \lvert V \rvert$ である。
- 点集合 $S \subset V$ は最大独立集合であるとする。点集合 $S’ \subset V$ は最小点被覆であるとする。このとき、 $\lvert S \rvert + \lvert S’ \rvert = \lvert V \rvert$ である。
まず 1. の証明は、調べても出てこなかったので自分で考えることにした。この記事の最後に書いておく。 途中でどうしてもわからなくなってしまったので、途中で放棄している。
一方で 2. の証明は簡単である。 $S \subset V$ が独立集合であることの必要十分条件は $V \setminus S$ が点被覆であることであるからである。例えば『アルゴリズムデザイン第 2 版』 p.411 に載っている。
定義 3 $G = (V, E)$ をグラフとする。 $G$ が 二部グラフ であるとは、 $A \subset V$ が存在し、 $B = V \setminus A$ とすると、任意の $(u, v) \in E$ に対し、 $u \in A$ かつ $v \in B$ となることをいう。
定理 4 $G = (V, E)$ を二部グラフとする。辺集合 $M \subset E$ は最大マッチングであるとする。点集合 $S \subset V$ は最小点被覆であるとする。このとき $\lvert M \rvert = \lvert S \rvert$ が成立する。
証明はこちらに書かれている。
以上より、次の系が成立する。
系 5 $G = (V, E)$ を二部グラフとする。辺集合 $M \subset E$ は最大マッチングであるとする。点集合 $S \subset V$ は最大独立集合であるとする。このとき $\lvert S \rvert = \lvert V \rvert - \lvert M \rvert$ が成立する。
実戦的にまとめると
以下の通りである。
- 一般の最大マッチングを求める問題は、多項式時間で解けるものの、実装が面倒である。多くの場合は二部グラフであるか、二部グラフに帰着できる。
- 一般の最大独立集合を求める問題は、 NP-hard である。
- $N \leq 40$ 程度なら、半分全列挙か枝刈りで解ける。
- 全ての頂点の次数が 2 以下のグラフは 2-SAT に帰着されるので多項式時間で解ける。
- 二部グラフの場合は系 5 で解ける。
- 最小辺カバー、最小点カバーを求める問題は、定理 2 があるから上記に帰着される。
私の今の目標は 1000 点までの問題を解けるようにすることだと思うので、多分これで足りる。
あとは解くだけ
欠けがあるとはいえ、グリッドグラフは二部グラフなので、この問題は系 5 より、二部グラフの最大マッチング問題を解くことに帰着される。容量 $1$ の辺の集まりとみなして普通に最大流を求めてもよろしいし、もっと単純なプログラムで解くこともできる。
両方ともプログラミングコンテストチャレンジブックに載っているのを拝借した1。
ポイント
この問題、色々な人の解説を読んだけど、やっぱり数学的な証明が一番納得がいく。
D - 建物
ポイント
E - カッコ列
ポイント
Others
付録 (定理 2.1 の証明の途中まで)
$M$ に辺を追加して最小辺被覆 $F$ を得ることを考える。すると、マッチングの最大性より、任意の $e \in E \setminus M$ の片方の端点は $W$ の点である。
増加道の定義をこのスライドで押さえる。 $M$ は最大マッチングだから $M$ には増加道が存在しない。
$M$ でマッチングされた点集合を $W$ とする。このとき、以下の性質を充す $A, B \subset W$ が存在する： $A \cup B = W$, $A \cap B = \emptyset$, $A’ \subset A$ である。任意の $e \in M$ に対し $u \in A$, $v \in B$ が存在し $e = (u, v)$ である。要するにマッチングを左側・右側に分けて、左側の点集合を $A$ とし、右側を $B$ とした。
$V \setminus W$ の点は、 $W$ の点に辺で接続されているのだが、どのようにつながっているか考察する。この時、 $V \setminus W$ の点と両端でつながっているような $e \in M$ は存在しない。もし存在すると、そこで長さ $3$ の増加路ができていることになる。よって、全ての $V \setminus W$ の点は $A$ の点につながっていると仮定して良い。
$V \setminus W$ のある点とつながっている $A$ の点の集合を $A’$ とし、 $A’$ と $M$ でマッチングされている $B$ の点の集合を $B’$ とする。ここで、 $B’$ の点同士を繋げる辺 $e \in E$ は存在しない。なぜなら、存在したと仮定すると、長さ $5$ の増加路ができているからである。
さて、以上の準備の元に、このグラフの最小辺被覆 $F$ を構築する。まず $V \setminus W$ の点は $A’$ の点のみと辺で接続している。だから、各 $V \setminus W$ の点に対し、 $A’$ の点とつながったある $1$ つの辺を、最小辺被覆を構築する際に使用する必要がある。これをまず $F_1$ に入れる。念のためにまとめると、ここまでで $V \setminus W$ の点と $A’$ を被覆しており、特に $V \setminus W$ の被覆に必要な最小限の数に抑えられていることに注意する。
だから問題は、 $A’ \cup (B \setminus B’)$ の最小辺被覆を求めることに帰着される。以下、この問題を考える。上からの評価が手に入っている。それは $M$ である。 $M$ は $A \cup B$ の最小辺被覆であるから、 $A’ \cup (B \setminus B’)$ の辺被覆である。もしもこれより $1$ 個小さい辺被覆 $F’$ があると仮定して、矛盾を導く。
まず、 $F’$ の辺で、 $B’$ と $(A \setminus A’) \cup (B \setminus B’)$ を繋ぐようなものがないと仮定する。すると $(A \setminus A’) \cup (B \setminus B’)$ の辺は最低でも $m = \sharp (A \setminus A’)$ 個必要である。 $B’$ 同士を繋ぐ辺は存在しないので、 $B’$ を辺を繋ぐために全部で結局 $\sharp M$ 個の辺が必要である。だからこれはありえない。
ゆえに、$F’$ の辺で、 $B’$ と $(A \setminus A’) \cup (B \setminus B’)$ を繋ぐようなものがある。 1 つだけあっても $\sharp M - 1$ 個にならないのはわかるので、少なくとも 2 個ある。
以下、そのような状況で $\sharp M - 1$ 個の辺カバーが作れたと仮定すると、元のマッチング $M$ で増加列があるようだ。 ここがどうしてもわからなかった。誰か教えてください！ ゆえに $A’ \cup (B \setminus B’)$ の最小辺被覆の個数は $\sharp M$ である。要するに、 $M$ に $V \setminus W$ とつながっている辺を追加したものが最小辺被覆を与えている。
うーんちょっと悔しいけども、これ以上考えても多分解決できないと思う。誰かに教えてもらえれば…。
-
厳密に言うと著作権の問題になると思うけど、この本の性質上、プログラムを写経しても著者たちは著作権侵害の申し立てはしないと思われるし、しっかり勉強させていただければと思っている。今後も同じようなことをすると思う。 ↩