ARC 041 D 辺彩色(2)

競技プログラミング

自分の中で、けものみちが熱いです。

qiita.com

続き。

atcoder.jp

難しいなぁと思いながら、解説は理解できたが、実装がわかんなかったので、実装例を見てみた。

kmjp.hatenablog.jp

お世話になってる kmjp さん！！！かっけー

pythonで書き直し。

from sys import exit, setrecursionlimit
setrecursionlimit(100000)
from collections import defaultdict
E = defaultdict(list)
# 辺の正しい色: C[i] == True なら C[i] は 'r'
C = [0 for i in range(2020)]

a = [0 for i in range(2020)]
b = [0 for i in range(2020)]
tar = [[0 for i in range(2020)] for j in range(2020)]
# vis は辺の番号
vis = [0 for i in range(2020)]
length = [0 for i in range(2020)]

# 辺
N, M = map(int, input().split())

for i in range(M):
    *tmp, s = input().split()
    a[i], b[i] = map(int, tmp)
    a[i] -= 1; b[i] -= 1
    # 辺の入力
    E[a[i]].append(b[i])
    E[b[i]].append(a[i])
    # tar には、その辺が、何番目の辺であるかを入れておく
    tar[a[i]][b[i]] = i
    tar[b[i]][a[i]] = i
    C[i] = s == 'r'

def dfs(pos, color, l):
    global vis, length
    # pos に訪れていないか 訪れていなかったら、
    if length[pos] < 0:
        length[pos] = l
    # すでに訪れたことがある、つまり、閉路であり、その長さが奇数だったら
    elif abs(l-length[pos])%2:
        print('Yes')
        exit()
    # 現在の頂点から伸びてる辺でイテレーション
    for to in E[pos]:
        # 辺の番号の取得
        num = tar[pos][to]
        if vis[num]:
            continue
        # 正しい辺の色と塗る色が同じだった場合のみ、続ける
        if C[num] == color:
            vis[num] += 1
            dfs(to, color^1, l+1)

# 始点と色で全探索
for i in range(N):
    for j in range(2):
        # vis の初期化
        for k in range(M):
            vis[k] = 0
        # length はすべて負にしておく
        for k in range(N):
            length[k] = -1
        # 始点 i, 色 j, 長さ 0 でスタート
        dfs(i, j, 0)
        if all([m != 0 for m in vis[:M]]):
            print('Yes')
            exit()
else:
    print('No')

TLEった... だけど、テストケース見てみると、TLE以外はACしてる。まぁ、一応実装は、理解できたということで...(自分に甘い)

自分的ポイントとしては、

  • 再帰関数内で、辺の番号を取得する || 辺の色にアクセスのために、入力の時に、あらかじめメモしておく。
  • 閉路の長さは、再帰の最初の部分で、判定する。また、その初期化処理。
  • 0, 1 反転(排他的論理和)
  • 辺彩色のやり方

わかんない問題ほど、勉強になりますね

今のpythonの書き方は、ほぼ自己流なので、ちゃんと競プロのために、速度的に早い書き方を調べないとなと思ったえぬわいでした。