SRM 594 Div I (1)
SRM 594 Div I
http://community.topcoder.com/stat?c=round_overview&er=5&rd=15706
前回に引き続き250にはまりにはまり、45分で再提出。Room 17。レートは1308から1341へ。
今回のエントリではSRM後に復習として考察した550のみを記載することにする。
| Problem | Status | Points | |
|---|---|---|---|
| 250 | AstronomicalRecords | Passed System Test | 87.28 |
| 550 | FoxAndGo3 | Opened | 0.00 |
| 1000 | FoxAndAvatar | Unopened | 0.00 |
- 250に32分
- はまりにはまった
- 提出後、オーバーフローすることが発覚。45分で再提出
- システムテストをパス。87.28点
- 方針は合っているので非常にもったいない(2回連続)
- 550を復習
- 二部グラフによる解法を理解した後にイメージトレーニングを行った
FoxAndGo3
http://community.topcoder.com/stat?c=problem_statement&pm=12808&rd=15706
- SRM終了後のTLを見るに、大きく二種類の解法があるようだ
- 一つは最小カットを使った解法
- この解法に関しては是非上位コーダーのエントリを参照していただきたい
- また、@Komaki__さんのエントリが引用されていることが多かった
- 自分には最小カットによる解法は難しく、手が出せていない
- さて、もう一つの解法は二部グラフの最大安定集合を使った解法だ
- @torus711さんのエントリが大変秀逸であった
- エントリを読んだ
- 何やら二部グラフの最大マッチングを利用するらしい
- しかしグラフの用語に乏しく、さっぱり分からなかった
- (最大)安定集合とはなんだ...
- そのため、まずグラフの用語を記したエントリの拡充を試みた
- をを、なるほど
- 最大安定集合とは以下のようなものなのか...
- 要するに、お互いに隣接しない頂点の集合が安定集合
- その頂点数が最大である集合を最大安定集合と呼ぶらしい
- 蟻本によれば、二部グラフの最大安定集合の頂点数は最大マッチングのペア数から求めることができるようだ
- なるほど
- だが、この問題でどう最大安定集合に落とし込むかさっぱり分からん
- (2、3時間ごにょごにょする)
- なるほど...
- 理解したぞ...
- 理解した記念に以下のようにつぶやいた
同時に起こりえない事象同士を接続したグラフの安定集合は同時に起こりえる事象の集合である、ということか…
- これはとても正しい(はずだ)
- 正しいはずなのだが、実際にこの問題に適用する方法を思い浮かべる度に迷いが生じる
- きっとイメトレが足りないのだ
- よし、もっと考察しておこう
- まず以下のような盤の状態を考えてみよう(サンプル #0)
- この状態での空マスの数は4
- 空マスには黒玉を置くことができる
- 白玉は黒玉で挟むと取り除くことができる
- この状態での空マスの数は3
- 初期状態より少し成績が悪くなってしまった
- 黒玉を置き、白玉を消し、空マスの数を最大化する問題
- とても難しい
- そしてこの盤の大きさだと、自分にはすでに大き過ぎる...
- 問題を簡単にしてみよう
- ををを
- いいぞ
- 右上は元々空マスである
- この空マスで得点することを事象1とする
- 同様に、左下の元々の空マスで得点することを事象2とする
- さて、残る得点方法は黒玉を置き、左上の白玉を取ることだ。これを事象Aとする
- 事象Aは「左上のマスから白玉を取り除くことによってできる空マスによって得点を得る」事象であることを軽く意識する
- 違う言い方をすれば、事象Aを「右上と左下に黒玉を置く」事象等とは考えないことがコツだ
- 黒玉が事象1と2に被っている
- つまり、事象Aで得点をする場合は、事象1、2で得点することはできないということだ
- ここで、事象1、2、Aを頂点としてグラフを作る。このとき、同時に起こりえない事象を表す頂点同士を接続する
- これを事象グラフと名付ける
- この事象グラフの最大安定集合は以下だ。つまり、頂点1、2からなる集合だ
- では3x3の盤に戻って考えてみよう。元々の空マスで得点を取る事象を1、2、3、4とする
- 白玉を取り除くことで空マスを得る事象をA、B、C、D、Eとする
- これを事象グラフに落とし込む
- 事象Aが起きたときには事象1、2は起こりえない。そのため、頂点Aと頂点1、2を繋ぐ
- これを繰り返す...
- この事象グラフの最大安定集合は以下となる
- つまり、全ての空マスに黒玉を置いて全ての白玉を取り除くのが最適解となる、ということだ
- 図やグラフを注意深くみると、事象1、2、3、4はお互いに独立していることが分かる。そのため、頂点1、2、3、4の間には辺が張られることがない。事象A、B、C、D、Eに関しても同様であるので、このグラフは二部グラフであると言える
- 事象グラフの頂点を配置し直してみよう
- 最大安定集合は以下だ
- では実際に最大安定集合の頂点数を得るにはどうしたらよいだろうか?
- グラフの性質を利用してやればよい
- 以下は蟻本からの抜粋だ
a. 孤立点のないグラフに対し、|最大マッチング|+|最小辺カバー|=|V|
プログラミングコンテストチャレンジブック 第2版
b. |最大安定集合|+|最小点カバー|=|V|
c. |最大マッチング|=|最小点カバー|
- bとcより、
|最大安定集合|+|最大マッチング|=|V|
- そのため、最大安定集合の頂点数は以下のように求めることができる
|最大安定集合|=|V|-|最大マッチング|
- また、事象グラフは二部グラフだ。二部グラフでは最大マッチングが比較的簡単に得られることも利用できる
- 以下は最大マッチングを行った結果の一例だ
- 最大マッチングのペア数は4である。頂点数9からこれを引くと5。つまり、最大安定集合の数は5であると言える
- すごい
- すっきりし始めた
- もう一度実際の実装を見る。巧妙でクレバーな実装だ
- まず無条件に頂点を2n2個割り当ててみよう
- 起こりえない事象を赤く描画している
- この場合の頂点数はもちろん2n2だ
- よく観察すると、各マスで起こる事象は最大でも1種類であることが分かる。これを利用して事象をまとめてみよう
- 頂点数はn2で収まってしまった
- 二部グラフとその最大マッチングは以下のようになる
- では、元々黒玉が配置されている場合を見てみよう
- この場合2は無効な頂点であるが、どの頂点とも接続しない頂点として残してやるのがポイントだ
- この場合の二部グラフと最大マッチングを図示すると以下となる
- ただし、この場合は孤立点があるため、先の関係をそのまま用いることが出来ない
- しかし、二部グラフの最大マッチングで孤立点がマッチングとして判定されることはない
- そのため以下が成り立つ。実装ではこれを巧みに利用している
|V| - |孤立点| - |最大マッチング| = |最大安定集合|
- すっきり理解した
