I : 首都 原案 : 岸本 解法の提示 : 森田 正当性の証明 : 岸本 テスター : 岸本, 森田 解説 : 岸本 概要 • DAGな有向グラフが与えられる • グラフの辺に対しては反転操作が可能 • ある頂点sからすべての頂点に到達可能にした い • T(s)を頂点sに対して必要最小限な反転操作回 数とする • T(s)の最小値およびそれを達成する頂点をすべ て求めよ 制約 • 頂点数 N <=10,000 • 辺数 M <= 100,000 • グラフはDAG • 入次数0の頂点数は50以下 原案 • まずは原案を考える • 問題設定は同じ • 制約のみ異なる 原案の制約 • 頂点数N <= 300 • 辺数 M <= 500 くらい 原案の解法 • 有向辺(i, j)に対して i->jにはコスト0の辺 を張り, j->i にはコスト1の辺を張ることに する • 考えたい問題のコストの最小値は, 実はい くつか有向辺を選んでsから到達可能であ るようにすればよい • つまり…? 最小全域有向木！ 最小全域有向木 • 何それ • 重み付き有向グラフに対して根 r が与えられた とき, rを根とする最小重みの全域有向木を求め る • どうするの • Chu-Liu/Edmonds のアルゴリズムが知られて いる Chu-Liu/Edmonds のアルゴ リズム • 1. 根以外の頂点vに対して頂点vに入る辺として重みが最小の 辺min(v)を選択する • 2. これらの辺を使って有向木になっていたら終了 • 3. そうでない場合, どこかにループが存在する • 4. ループ中の頂点vに対して, vに入る辺の重みをそれぞれ(元 の辺の重み) – (min(v)の重み)と変更する • 5. 1つのループに含まれる頂点で縮約して1つの頂点にする • 6. 1に戻る • 細かいことは以下のページ • http://en.wikipedia.org/wiki/Edmonds'_algorithm 評価 • Chu-Liu/Edmondsのアルゴリズムは時間 計算量O(VE)で動作する • 各頂点に対してT(v)の値を求めたいのでV 回動かす • 全体でO(V^2 E) • これで間に合う • やったぜ 現実 • 頂点数 N <=10,000 • 辺数 M <= 100,000 • グラフはDAG • 入次数0の頂点数は50以下 • とてもじゃないけど間に合わない 変な制約は無いか • 競プロでは妙な制約をみかけることがある • 無いかな？ • 「入次数0の頂点数は50以下」 • どういうことだろう？ 首都になりうる頂点 • 元のグラフで頂点vから頂点uに到達可能 とする • このときvからuは到達可能であり, uからv へ到達可能にするために余計にコストが必 要 • ということは入次数0の頂点だけが首都に なりうる！ さっそく評価 • Sを入次数0の頂点からなる集合とする • 候補が減ったのでChu-Liu/Edmondsのア ルゴリズムの適用回数は|S|回まで減った • O(|S|NM) • まだまだつらい じゃあどうすればいいの？ • Sに含まれる頂点をv, uとする • v -> u に到達可能にしないとどうしようもない • 逆に, Sに含まれる頂点を到達可能にするだけ でよさそう • v -> uを到達可能にするために必要なコストだ けを考えてS上でsから到達可能にするルート の選び方を考えればよい？ 本当？ • v -> u, v->w のパスがあったときに途中ま で同じものをひっくり返す場合がありそう。 うまくいかないんじゃない？ • 実は大丈夫 • がんばって証明しました • アウトラインはスライドの付録へ • つまり…？ やっぱり 最小全域有向木！ 辺のコスト • あとは v->uのコストをどう求めるか • 辺を順向きにたどれば0, 逆向きにたどれば 1のコストがかかるとする • これでv->uの最短経路を求める。 評価 • コスト決定パート • Dijkstra : O(|S| E log V) • コストが01なのでqueueに突っ込むと O(|S| E) • 最小全域有向木パート • 頂点数O(|S|), 辺数 O(|S|^2), 試す回数 O(|S|) • O(|S|^4) • あわせて O(|S|^4 + |S|E) • めでたしめでたし ジャッジ解 • 岸本(C++) : 236行 5348Byte • 森田(C++) : 232行 6147Byte 正解者 • 1AC / 2 Trying teams • Operasan (221:31)(中身はsemiexp+japlj) • 198行 3982Byte • ジャッジ解より短い • ジャッジの実装へたくそなのでは • ライブラリ無しだったらしい！ • もう1つのチームはO(|S|NM)解法を提出し ているように見えました 最小全域有向木について • 「アルゴリズムデザイン」に書いてあります • Spaghetti Source • http://www.prefield.com/algorithm/graph/chu-liuedmonds.html • ジャッジ • http://judge.uaizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_B&l ang=jp 余談(1) • 最初は原案通りの問題だったが、森田さんがもう ちょっと制約きつくできそうと言った • 自分もそれっぽいコストを考えて証明のような物 を書いたが撃墜されてしまった • 森田解が正しそうなので証明した。これは複数人 から同意を得たので合っているはず • 正直今も撃墜されないかビクビクしている 余談(2) • そもそも思いついたきっかけについてです • 何か問題を作ろうと思っていた時期がありました • 以下の二つをそれぞれ考えていました • 1. 典型アルゴリズムを使わない問題 • 2. グラフであまり見かけない操作を使った問題 • 1を出したくなったのは、Asia Danang(Vietnum) 2013 では知っててもコンテストであまり見かけな いアルゴリズムがたくさん出てたからです 余談(3) • とりあえず2の方をうんうん考えていると辺の反転とい うのが思い浮かんだのでそれで何か問題を作れないか 考えていました • そうしたら1として最小全域有向木が思いついたので非 常に嬉しかった、という具合です • 当時は周囲でこのアルゴリズムが登場していなかった ため出題を楽しみにしていました • が、会津大が先に出してしまった( http://judge.uaizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp14 Day2&pid=L )ので悔しかったです 証明について • 付録の証明です • 非自明なので大変 • 5時間コンテスト中に行うのは困難 証明のアウトライン(1) • ひっくり返す辺を共有する場合を考える • S上の頂点u,v,wがあるとしてS上にない頂点a,bが あるとする。ただしa->bは元のグラフで辺が張ら れている • v->…->b->a->…u , a->…wの経路上で逆方向の辺 をひっくり返してうまくいくこと(a->u, a->wの経 路の辺に重複は無い)にする • このとき、これ以下のコストで分岐がないような 経路に直せれば嬉しい 証明のアウトライン(2) • 頂点aはSに含まれないのでS中の頂点のどれかか ら到達可能である。これで場合分けをする • (1)uがaに到達可能であれば, v->…b->a->…->u, u>…->a->…->wのパスを考えると同じコストで済 む • (2)wがaに到達可能であれば同じこと • (3)残り : aがu,w以外のS中頂点xから到達可能とし たときはどうなるか 証明のアウトライン(3) • (3-a) :今回の解で u->…->xの経路が解として選択され ているとき • 次の経路でv->u->x->wとたどった場合と同じコストでOK • v->…->b->a->…->u->…->x->…->a->…->w • (3-b) : w->…->xの経路が解として選択されているとき • 同上 • (3-c) : (それ以外の頂点y)->…->x が解として選択されて いるとき • y->…->x->…->a->…->u, a->…->w とすればよりよい結果 となる
© Copyright 2024 ExpyDoc
