【AtCoder参加記録】AtCoder Beginner Contest 232【ABD3完】
C問題
https://atcoder.jp/contests/abc232/tasks/abc232_c
が解けずABD3完という結果でした。
コンテスト終了後数時間かけた結果、
数列Pとしてあり得るものを全探索して青木くんのおもちゃの隣接行列を数列Pごとに生成するようにしたところ解くことができました。
コンテスト中は問題文もまともに理解できず頭が混乱してしまったため冷静に考えられるようになりたいです。
from collections import defaultdict from itertools import permutations N, M = map(int, input().split()) # 高橋くんのおもちゃの隣接行列 t = [] for i in range(N): t.append([False]*N) for i in range(M): a, b = map(int, input().split()) a -= 1 b -= 1 t[a][b] = True t[b][a] = True # 青木くんのおもちゃの情報を持っておく ainfo = [] for i in range(M): c, d = map(int, input().split()) c -= 1 d -= 1 ainfo.append([c, d]) # 数列Pとしてあり得るもの P = permutations([i for i in range(N)]) for p in P: # 青木くんのおもちゃの情報を数列Pに合わせるために辞書を用意する di = defaultdict(int) for i in range(N): di[i] = p[i] # 青木くんのおもちゃの隣接行列を数列Pごとに生成 a = [] for i in range(N): a.append([False]*N) for i in range(M): c, d = ainfo[i] a[di[c]][di[d]] = True a[di[d]][di[c]] = True # 高橋くんのおもちゃの隣接行列と青木くんのおもちゃの隣接行列を比較 if t == a: print('Yes') exit() print('No')