Problem I : Linear Ether Geometry 問題作成・英訳：三廻部担当: 福澤菅原野田解説: 福澤野田問題書斎1 書斎2 インターネット・コネクタ書斎3 書斎4 書斎5 各書斎へのコネクタ • 廊下の端にあるインターネットコネクタと各書斎のコネクタをハブとケーブルを使って接続したい． • ハブをできる限り少なく，ケーブルのたるみの合計をできる限り小さくしたい． • 書斎数 ≦ 5, ケーブル数 ≦ 10, 廊下の長さ ≦ 20 • 使うハブの最小数と，ハブが最小数のときのケーブルのたるみの合計の最小値を出力せよ．注意 • 間違ってもナイーブな探索はしてはいけない O(2^L * M!) ≒ 3,805,072,588,800 解法(1-1) • シュタイナー木のDPの応用＋初期化による枝刈り • シュタイナー木：グラフGとGの頂点部分集合Tが与えられたとき， Gの部分グラフでTを全て張る木など – シュタイナー木問題：最小のシュタイナー木を求める問題．NP困難 – シュタイナー木問題の解法 • Dreyfus-Wagner • Robins-Zelikovsky 解法(1-2) • シュタイナー木のDPの応用 – ある座標にハブを置いたとして，そのハブ以下に，あるケーブルの組合せだけで，ある書斎の組合せを，接続する際に使うケーブルの最小数と，そのときのたるみの合計の最小値を探索で求める – ケーブルを一本選んで，そのケーブルを使ってインターネットコネクタと接続可能な全ての座標にハブを置いてみて探索開始 – ケーブルの最小数 – 書斎の数 = ハブの最小数解法(1-3) • 各状態は，以下の二通りの探索で最小値を求める – 書斎の組合せを二つに分け，それに合わせてケーブルの組合せも二つに分ける – ケーブルを一本選んで，そのケーブルを使っておける場所に一つハブを設置し，書斎と残りのケーブルをまるごと移動解法(1-4) • 初期化による枝刈り – 書斎数 > ケーブルの数ならImpossible – 書斎数 == 1 • ケーブルを全部使っても無理なら Impossible • ↑以外なら，もっともケーブルを使わずにもっともたるみの合計が少ない長さを計算 – 書斎数 ≦ ケーブルの数 • ケーブルから短い順に書斎数 - 1本を抜いたケーブルの長さの合計 < ハブから一番遠い書斎までの距離なら Impossible • 現在のハブと各部屋それぞれ一本のケーブルで直接接続できるとき，即計算可能 • 初期化で決定しなかった部分をmemoizeで探索解法(1-5) • 注意点 – ハブの数が0の場合もある – やってはダメな枝刈り • ハブの座標が単調増加など – ナイーブに書くと，TLEになる可能性大 • ソースコード：200行（6,105バイト） • 製作期間：合計3週間くらい • ジャッジ入力実行時間： C++ 15.0sec, Java 37.3sec 解法(2-1) • HUBの設置位置の組合せを探索 • 設置位置の各組合せについて、どの接続にどのケーブルを用いるか、二部グラフを作成して最小費用流を用いて割り当てる解法(2-2) • 最小費用流が分からない方はインターネットで検索して下さい – アジア地区予選では滅多に出ないので心配する必要ありません解法(2-3) • 前提 – HUB同士の接続は木構造である – 部屋からHUBへつなぐとき、どのHUBにつなげても良い – インターネットコネクタからHUBにつなぐとき、どの HUBにつなげても良い解法(2-4) • 最小費用流のグラフを作成する – Src→ケーブル – ケーブル→コネクタ-HUB間 – ケーブル→HUB間 – ケーブル→HUB-部屋間 – ***→sink 解法(2-5) • 左側(source側)にケーブルを配置する – 各ケーブルの種類についてノードを作成する – Srcからコスト0、流量がケーブルの本数である辺を追加する解法(2-6) • コネクタ-HUB間の接続に使用するケーブルの候補を表す辺を追加する – HUB同士は木構造で接続されているので、どれにつないでも良い – 各ケーブルについて最もたるみが少なく接続できるHUBを選び、コストをたるみ、流量を1とした辺を追加する解法(2-7) • HUB間の接続に使用するケーブルの候補を表す辺を追加する – 各HUBに番号をつける – 自分の番号より小さい番号のHUBにつなげれば、自然と最適な木構造になるはず • 反例がある • これについては後述する解法(2-8) • 各ケーブルについて最もたるみが少なく接続できるHUBを探し、ケーブルからHUBのノードへ、コストがたるみ、流量が1となる辺を追加する解法(2-9) • HUB-部屋間の接続に使用するケーブルの候補を表す辺を追加する – 各部屋からはどのHUBにつないでも良い – 各ケーブルと部屋の組について、最もたるみなくつなげるHUBについて、コストをたるみ、流量を1 とした辺を追加する解法(2-10) • コネクタ-HUB間、HUB間、HUB-部屋間を表すノードからsinkにコスト0、流量1の辺を追加する解法(2-11) • HUB数+部屋数のフローが流れれば、そのコストが、そのHUBの配置でのたるみの最小となる解法(2-12) • 一部のHUBの木構造を再現できない – 最小費用流の実行後に木構造を再構築することで、一応最適解を求めることができる • あくまで撃墜困難というだけ • 証明はしていない – 例) 解法(2-13) • 木構造の再構築 – グラフの連結を維持したままたるみをより少なくできか各枝について調べていき、枝をつなぎかえる解法(2-14) • HUBの位置の探索を行う – HUBの数が小さいほうから全ての組合せを試す – ただし枝狩りをがんばる解法(2-15) • 枝狩り条件 – 現在のHUBの配置では最後の部屋までケーブルが届かない場合 – 一番長いケーブルを使っても一つ前に配置した HUBに接続できない場合 – 探索中のHUBの配置で部分マッチンググラフを作成し、フローが流れなかった場合 – マッチングの直前、フローが流れないことが明らかな場合解法(2-16) • ソースコード : 587行 18kバイト • 製作期間 : 約2週間 • ジャッジ入力実行時間 – 32.7sec – 特定の入力に対し劇的に遅い • ランダム入力は一瞬で終わる注意 • HUBがインターネットコネクタと同じ場所に配置される場合がある • HUBを必要としない場合がある結果 • • • • Submit数 : 1 Accepted数 : 0 First Submit : 243分(iromono) ? First Accepted : なし iromonoのソースコード #include <iostream> int main() { oflakjds;flajsf;lsajdf;lj; } なにやってんの？宿題 • 解法2を撃墜せよ