日立コン2020 C - ThREE
問題原文
問題要旨
頂点の木がある。以下の条件を満たすよう、各頂点に１から
までの数を当てはめよ。
距離が３である頂点のペアに書かれている数の和もしくは積が３の倍数
解法
超絶怒涛の神良問（解けなかったけど） 。
3, 6, 9などはどれとでもペアになれる便利な数。
1, 4, 7... などの3で割って１余るものは、2, 5, 8... などの３で割って２余るものとペアになる必要がある。逆もしかり。
というわけで、「木を二分グラフに見立てて、赤色と青色の二色に塗り分ける」。
すると、赤色に1, 4, 7...、青色に2, 5, 8...、足りない部分に2, 6, 9...を当てはめればだいたいうまくいく。
うまくいかないパターンとして、ウニグラフのような、「ピンポイントに３をおく必要があるもの」が考えられる。
実は、普通に考えれば、赤色で塗った頂点の数 or 青色で塗った頂点の数が3, 6, 9...の数より少ないならば、3, 6, 9...をそのような色にまとめて当てはめてしまえることがわかる。
大きくパターンは２種類（赤と青の入れ替えを考えれば３種類）で、
- 「1, 4, 7...」と「2, 5, 8...」で分けて塗り、足りない部分に「3, 6, 9...」を当てはめる
- 「3, 6, 9...」と「1, 4, 7, 2, 5, 8...」 に分けて塗る（積を３の倍数にしていく）
がある。
実装
N = int(input()) T = [[] for _ in range(N)] for _ in range(N - 1): a, b = map(int, input().split()) a, b = a - 1, b - 1 T[a].append(b) T[b].append(a) colors = [-1] * N stack = [(0, 0)] while stack: n, color = stack.pop() colors[n] = color for to in T[n]: if colors[to] != -1: continue stack.append((to, color ^ 1)) # あまり１、あまり２、あまり０になるように並び替え X = [[] for _ in range(3)] for n in range(1, N + 1): X[n % 3].append(n) X.append(X[0]) del X[0] ans = [] x12, x3 = X[0] + X[1], X[2] if colors.count(0) <= N // 3: for color in colors: if color == 0: ans.append(x3.pop()) elif x12: ans.append(x12.pop()) else: ans.append(x3.pop()) elif colors.count(1) <= N // 3: for color in colors: if color == 1: ans.append(x3.pop()) elif x12: ans.append(x12.pop()) else: ans.append(x3.pop()) else: for color in colors: if X[color]: ans.append(X[color].pop()) else: ans.append(X[2].pop()) print(' '.join(map(str, ans)))
