soundhound2018-spring

README

SoundHound 2018 春 過去問感想

• C問題はグラフやら連結成分やらを考えたらうまく行けるのだろうかと考えたが、ダメだった。
  • もちろん、貪欲的なものもアウト。
  • 2部マッチング、最大独立集合問題あたりが関連するらしい。ちょっと長くなるので、詳しくは後述する。

---

学習用リンク集

実世界で超頻出！二部マッチングの解法を総整理

二部グラフの最小点被覆、最大安定集合、最小辺被覆を総整理！

tutuzさんの問題自体の解法

今回の問題を解くことを目的として上の記事を全部読むとパンクするので、 あまり一般化させすぎずに、今回必要な知識だけの修得を目的として学習すること。 （無理は良くない。）

二部グラフ

定義

頂点集合を2つの部分集合に分割して 各集合内の頂点同士の間には辺が無いようにできるグラフ のことである。

以下は用語などの補足事項。

• 独立集合
  • 辺が張られない点集合。2部グラフでいう2つに分けられたそれぞれの点集合のこと。
  • 独立集合 n 個からなるとき、n部グラフと呼ぶ。
• $K_{m, n}$
  • m頂点の頂点集合とn頂点の頂点集合に分割されるような完全二部グラフのことを、このように表記する。
• 完全2部グラフ
  • それぞれの頂点集合から任意の点を1つずつ選んだときに、必ずそのような2点間に辺が張られているような2部グラフのこと。
  • フランクにいうと、張れるだけ（m*n 本）辺が張られている二部グラフのこと。
• マッチング
  • 二部グラフの辺集合Mがマッチングであるとは、Mに属するどの2辺も隣接していないということである。
    • 辺の隣接: 辺と辺がある頂点を共有しているとき、その辺同士は隣接している、という。
      • 辺の隣接というは知らなかった（反省）。
  • グラフGの最大マッチング: GのマッチングMのうち、辺の数が最大のもの。
    • すべての頂点を含むマッチングのことを完全マッチングという。

独立集合（independent set）について

色々な言い換え（というか解釈）を知っていると定着しやすいと思うので、こちらもまとめておく。

• まず、 安定集合（stable set） という呼び方も知っておくこと。
• 1つのグラフ内で互いに隣接していない頂点の集合である。
  • 以下は言い換え2つ。
  • すなわち、頂点の集合Vで、Vの任意の2つの頂点をつなぐ辺が存在しない場合 をいう。
  • 等価的に、そのグラフの各辺の高々一方の端点のみがVの元である。
• 独立集合の大きさ: その中の頂点の個数。
• 極大独立集合（maximal independent set）: 任意の（Vの）他の頂点を追加すると、その集合に辺の両端点が含まれてしまうような独立集合。
• 最大独立集合（maximum independent set）: 与えられたグラフGの最も大きな独立集合。
  • このような集合を求める問題を 最大独立集合問題 と呼ぶ。
  • NP完全問題である。

実世界での例

• マッチングアプリでの「男」と「女」
  • グループ内で辺が結ばれない、という点を理解するにはこれが最も直感的に感じられる。
• インターネット広告分野で、ユーザの興味に合う広告を出す（「ユーザ」と「広告」）

他にも実にたくさんの例がある。

---

このあたりから、色々と調べ物が発散してしまい、今回のC問題のコードが一切書き始められないと思ってきたので、 一旦知識のインプットをストップし、C問題を通すことを目指す。

---

C問題

tutuzさんのブログ が丁寧であるため、 ベースはここで学ばせていただく。

まず、 グリッドグラフ の色々な見方が学べる。知識としていきたい。

• このグリッドグラフは、各頂点の上下左右の4マスにしか辺が存在しない。
  • 頂点 (i,j) について、 i+j が偶数の場合と奇数の場合に分けて市松模様のようになっているグラフ。
  • このグリッドグラフは2部グラフとなっている。
    • 白黒で彩色すると、それぞれの色の頂点集合が独立集合となっている。

そして今回の最大のポイントである、最大安定集合のサイズの求め方は、 頂点数 - 最大マッチングサイズ という部分。

正直、あまり自明ではない（こういうことかな？という推測はつくが、グラフに不慣れなのであまり自身が持てない）。

この部分の理解と、具体的なアルゴリズムについては、 けんちょんさんのこのQiita記事で頑張る。