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 では、にいる猫達とにいる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 \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)