日々drdrする人のメモ

今日もdrdr、明日もdrdr

CodeChef July Challenge 2018: Tom and Jerry

CodeChef July Challenge 2018の問題: Tom and Jerry (Code: JELLYTOM)
問題ページ: https://www.codechef.com/JULY18A/problems/JERRYTOM

問題概要

Jerryを捕まえるためにTomは {K}匹の猫を雇う。
そして、 {N}つの頂点と {M}本の辺を持つグラフ {G = (V, E)}上で {K}匹の猫達がJerryを捕まえようとする。

このグラフ {G}は以下の特徴を持つ

  • 4つ以上の頂点からなる単純閉路について、この中に含まれる頂点同士を結ぶ、閉路に含まれない辺が存在する

このグラフ {G}上では、各roundで以下の手順を行う

  • 最初のround 0では、猫達は最初にとどまる頂点集合 {X_0 \subseteq V, |X_0| \le K}となる {X_0}を選択し、Jerryはとどまる頂点 {v_0 \in V \setminus X_0}を選択する
  • 各round  {i (\ge 0)}では、 {X_i}にいる猫達と {v_i}にいるJerryが以下のように移動する
    • 猫達が次にとどまる頂点集合 {X_{i+1} \subseteq V, |X_{i+1}| \le K}を選択し移動する
    • その後にJerryは、 {X_i \cap X_{i+1}}に含まれる頂点を通らないパスで到達できる頂点 {v_{i+1} \in V \setminus X_{i+1}}に移動し、そのような頂点 {v_{i+1}}が存在しない場合はJerryは捕まる

グラフ {G}上でJerryを捕まえるために必要な最小の猫の数 {K}はいくらか?

制約

1つのテストケースに含まれるケース数:  {1 \le T \le 10} ( {N \le 10^5}の制約においては {1 \le T \le 5})
 {3 \le N \le 10^5}
 {1 \le M \le 2 \times 10^5}
 {1 \le u, v \le N, u \neq v}
多重辺は存在しない

解法

この問題は、グラフ {G}の最大クリークのサイズが解になる。
問題文中の特徴を持つグラフ {G}Chordal graphらしく、一般的なグラフに対してNP困難である最大クリーク問題が多項式時間で解ける(perfect elimination ordering等が利用できる)。

コンテスト中の思考

 {K}はグラフ {G}の最大クリークのサイズ以上でなければならないことは分かった。そうでなければ、グラフ {G}の最大クリーク上でJerryに逃げ続けられることになる。

例えば、下の図のグラフは最大クリークのサイズが5であるが、 {K}が4以下の場合は頂点3,4,5,6,7上でJerryが逃げ続けることができる。
f:id:smijake3:20180718000828p:plain

これより解が最大クリークのサイズ以上であることは分かるが、最大クリークのサイズが解になる根拠がなかったため、いくつか実験して正しそうだったので出したら通った。

解説メモ

Forumのdiscussionに説明が載ってたので、ここにメモ。
まず、今回の問題はvisible cops and robbers gameというGraph searching gameの形そのままらしい。(参考pdfに載ってる)
そして、このゲームでsearchers(問題分中の猫達)がfugitive(問題文中のJerry)を捕まえるためには((グラフのtreewitdh)+1)人が必要であることが示されており、Chordal graphにおけるtreewidthは(最大クリークのサイズ)-1と等しいことから解は最大クリークのサイズになる、ということらしい。

実装

Bron–Kerbosch algorithmで極大クリークを列挙しながら {K}を求めた。

提出コード (PyPy2): https://www.codechef.com/viewsolution/19209051

T = int(raw_input())
for _ in xrange(T):
    N, M = map(int, raw_input().split())
    G = [set() for i in xrange(N)]
    D = [0]*N
    for i in xrange(M):
        u, v = map(int, raw_input().split())
        G[u-1].add(v-1)
        G[v-1].add(u-1)
        D[u-1] += 1; D[v-1] += 1

    # Bron-Kerbosch algorithm
    def rec(V, P, X):
        if not P and not X:
            return V
        r = V; u = None
        if X:
            u = next(iter(X))
        else:
            u = next(iter(P))
        for v in P - G[u]:
            r0 = rec(V | {v}, P & G[v], X & G[v])
            if len(r) < len(r0):
                r = r0
            P.remove(v)
            X.add(v)
        return r
 
    I = range(N)
    I.sort(key=lambda x: -D[x])
 
    ans = 0
    P = set(range(N))
    X = set()
    for v in I:
        r = rec({v}, P & G[v], X & G[v])
        P.remove(v)
        X.add(v)
        ans = max(ans, len(r))
    print(ans)