読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

SRM682 Div.1 Easy SmilesTheFriendshipUnicorn

競プロ グラフ

問題

https://community.topcoder.com/stat?c=problem_statement&pm=14104

グラフ上にfriendship chainが存在するか判定せよ。ただしfriendship chainとは、異なる点A, B, C, D, Eに対し、AとB, BとC, CとD, DとEがそれぞれ隣接するようなグラフのことである(つまり長さ4の単純路)。また、グラフは連結であることが保証されている。

制約

 5 \leq N \leq 2000

 1 \leq M \leq 2000 (辺の本数)

解法

kmjpさんの記事を参考にさせていただいた。

kmjp.hatenablog.jp

この問題、Mの大きさがNと同程度というのがポイント。

まず真ん中の点cを固定し、cに隣接する点からb, dを選ぶ。これだけで O(N^3)かかってしまうのでは?と思うかもしれないが、実際は各辺を2度ずつ調べるだけなので O(M^2)で済む。

b, dに隣接するa, eがあるかどうかはb, dの次数を用いて判定できる。bの次数が3以上ならaとなる点がb, c, d以外に存在する。また、bの次数が2のとき、bからdに辺がつながっていなければaが存在する。dの判定も同様である。

この判定だとa = eとなる可能性がある。つまりa-b-c-d-aという閉路ができる場合だ。しかしこの場合もfriendship chainを作ることができる。グラフは連結 かつ  N \leq 5 という制約から、a, b, c, dのいずれかに隣接する点がある。例えば点cに点zが隣接しているとすると、d-a-b-c-zなるfriendship chainが作れる。

from collections import defaultdict as ddict
import itertools as itr

class SmilesTheFriendshipUnicorn:
    def hasFriendshipChain(self, N, A, B):
        G = ddict(list)
        M = [[False] * N for i in range(N)]
        for a, b in zip(A, B):
            G[a].append(b)
            G[b].append(a)
            M[a][b] = True

        for c in range(N):
            for b, d in itr.combinations(G[c], 2):
                ok = 0
                if len(G[b]) > 2 or (len(G[b]) == 2 and not M[b][d]:
                    ok += 1
                if len(G[d]) > 2 or (len(G[d]) == 2 and not M[b][d]:
                    ok += 1
                if ok == 2:
                    return "Yay!"

        return ":("


所要時間: - (考察1時間でギブアップ)

解けそうで解けなかった。こういう問題は面白い。