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 に戻る 細かいことは以下のページ

評価 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 edmonds.html edmonds.html ジャッジ aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_B&l ang=jp aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_B&l ang=jp

余談 (1) 最初は原案通りの問題だったが、森田さんがもう ちょっと制約きつくできそうと言った 自分もそれっぽいコストを考えて証明のような物 を書いたが撃墜されてしまった 森田解が正しそうなので証明した。これは複数人 から同意を得たので合っているはず 正直今も撃墜されないかビクビクしている

余談 (2) そもそも思いついたきっかけについてです 何か問題を作ろうと思っていた時期がありました 以下の二つをそれぞれ考えていました 1. 典型アルゴリズムを使わない問題 2. グラフであまり見かけない操作を使った問題 1 を出したくなったのは、 Asia Danang(Vietnum) 2013 では知っててもコンテストであまり見かけな いアルゴリズムがたくさん出てたからです

余談 (3) とりあえず 2 の方をうんうん考えていると辺の反転とい うのが思い浮かんだのでそれで何か問題を作れないか 考えていました そうしたら 1 として最小全域有向木が思いついたので非 常に嬉しかった、という具合です 当時は周囲でこのアルゴリズムが登場していなかった ため出題を楽しみにしていました が、会津大が先に出してしまった ( aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp14 Day2&pid=L ) ので悔しかったです aizu.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 とすればよりよい結果 となる