五輪ピック / yukicoder-no-408

Transcript

1. yukicoder No. 408 五輪ピック 原案，解説: camypaper
2. 問題 • N 頂点 M 辺の単純グラフが与えられる • 以下の制約を満たす部分グラフは存在するか？ – 頂点 1 を含む – 長さ 5 の単純閉路グラフである ) 000 , 50 , 2 / ) 1 ( min( 1 000 , 20 1       N N M N N
3. 想定解法 • 想定したものは 2 つ – Meet in the middle algorithm – Color coding algorithm • 他にもあったら教えてください
4. 1 b d c a Meet in the middle
5. 基本的な方針 • 長さ 5 の単純閉路グラフを 2 つのパスに分解する • (a, b)と(c, d) を使って条件を満たす (a, b, c, d) が 存在するか判定する 1 b d c a
6. 長さ 2 のパスの列挙 • 1 – u – v となるような単純パスが存在する u, v の組を (u, v) とおく – 頂点 1 に隣接する頂点から辺を全探索して O(M) でできる 1 b d c a
7. 長さ 5 のサイクル検出 • 頂点 v を固定したときに (u, v) が存在するような u たちだけからなる集合 を S(v) と表すことにする • 辺について全探索して b, d を決め打ちして条件を 満たす a, c があるか以下のようにして判定する – S(b) から d を，S(d) から bを取り除いた集合を S′(b), S′(d) と して，以下の条件のどちらかを満たすか判定 • |S′(b)| = |S′(d)| = 1 かつ S′(b) ≠ S′(d) • 1 ≤ |S′(b)|, |S′(d)| かつ 2 ≤ max(|S′(b)|, |S′(d)|) – unordered_set などを用いると O(1) 1 c a b d
8. 判定の意味 • |S′(b)| = |S′(d)| = 1 かつ S′(b) ≠ S′(d) – 左図のようなグラフを弾いている • 1 ≤ |S′(b)|, |S′(d)| かつ 2 ≤ max(|S′(b)|, |S′(d)|) – 右図のような部分グラフがあるかの判定 1 a b d 1 b d c a 1 b d c a a′
9. まとめ • 頂点 1 を始点とする長さ 2 のパスを全探索 – unordered_set を使って管理すると O(N + M) – 時間，空間計算量 O(N + M) • 長さ 2 パスの終点どうしをつなぐ辺を全探索し 長さ 5 のサイクルの存在判定 – O(M) で辺について全探索可能 – 各辺について O(1) で判定が可能 • 計算量は O(N + M)
10. 1 Color coding
11. 基本的な方針 • 頂点 1 に隣接する頂点を始点，終点とする頂点 1 を 含まない長さ 4 の単純パスを探す • 単純パスを探す問題は難しい – 各頂点に 4 種類の色を割り振ったグラフ上で長さ 4 の カラフルパスを探すことを考えよう • カラフルパス: 各頂点の色がそれぞれ異なるパス 1 1
12. 部分問題: カラフルパスの存在判定 • K 種類の色が割り当てられたグラフが与えられる • 長さ K のカラフルパスは存在するか？ – これは簡単なbit DPで判定が可能 – dp (使った色の集合，現在の頂点) = そのようなパスの有無 – 計算量は O(2K (N + M)) 1
13. Random Coloring(1) • 各頂点に K 種類の色をランダムに割り当てる • 長さ K のカラフルパスが存在するか判定する • 見つかったならば YES，そうでないならば NO • 正解が YES のときに NO と返す確率は (1 – K! / KK) • K = 4 のときで WA となる確率は 9 割… 1
14. Random Coloring(2) • 以下を適当な回数 (例えば 200 回) 繰り返す – 各頂点に K 種類の色をランダムに割り当てる – 長さ K のカラフルパスが存在するか判定する • 途中で見つかったならば YES，そうでないならば NO • 正解が YES のときに NO と返す確率は (1 – K! / KK)200 • K = 4 のときで WA となる確率は 10 – 8 以下 1
15. まとめ • 以下を 200 回程度繰り返す – 各頂点に 4 色をランダムに割当てる – 頂点 1 を取り除いたグラフ上で頂点 1 に隣接していた頂点 を始点，終点とする長さ 4 のカラフルパスがあるか判定 • 途中で見つかったならば YES，そうでないならば NO • 計算量は O(N + M) – ステップ数は 200 × 24(N + M) 程度とやや多い
16. コメンタリー • color codingは SRM 682 Div1 Easy でりんごさんの提出 を見て知ったアルゴリズムです • とても面白いと思ったので紹介したかった • meet in the middle を使った解法は後から思いついた – 本番ではこっちで通す人の方が多そう • この問題は SRM 682 Div1 Easyをパクってに感銘を 受けて作りました