日々drdrする人のメモ

今日もdrdr、明日もdrdr

AGC024 - D問題: Isomorphism Freak

問題: D: Isomorphism Freak - AtCoder Grand Contest 024 | AtCoder

1100点だけど、実質700, 800点問題な感じ。
コンテスト中に解けないといけなかった問題。猛省。

問題

 {G}を何色かで彩色したものの内、ある色で彩色された頂点 {v}を根とした根付き木は全て同型となるものを良い彩色と呼ぶ。また、木 {G}良い彩色の中の色の種類が最小値をカラフルさと呼ぶ。

この木 {G}のある頂点と新たな1つの頂点を繋ぐ操作を何回か繰り返すことで達成できるカラフルさの最小値はいくらか?
そして、カラフルさが最小となる時の木 {T}の内、葉の数が最小となる時の葉の数はいくらか?

制約

 {2 \le N \le 100}
 {1 \le a_i, b_i \le N}
グラフは木で与えられる

コンテスト中の思考

木の中心の頂点で木 {G}を分割すると彩色が最小になることと、分割後の各部分木を同じにしないといけないところまでは気づいた。
ただ、分割後の部分木自体を根から対照にすることを見落として、各部分木を部分木として持つ、葉の数が最小な木を生成すればよいという思考をして、木を符号化して計算しようとしてた。(実装が間に合わなかったし、出せてもWA)

解説

公式の解説: https://img.atcoder.jp/agc024/editorial.pdf

まず、最小の彩色は木 {G}の直径を {D}とした時の {\displaystyle \lceil \frac{D}{2} \rceil}になる。

また、頂点を何回か足しあわせることで、以下のように木の中心から対照的な木にでき、これが良い彩色の条件を満たす。そのため、色の種類が {\displaystyle \lceil \frac{D}{2} \rceil}の時の対照的な木を構築し、そのうち葉が最小になるときの木 {T}を求める。

(1) 中心の頂点が1個の時の例
f:id:smijake3:20180521231837p:plain
(2) 中心の頂点が2個の時の例
f:id:smijake3:20180521231851p:plain

対照的な木において、1個(もしくは2個)の中心の頂点から同じ距離の全ての頂点の次数は同じになる。例えば、上図(1)は中心から次数3-次数3-次数3-次数1になっている。
そのため、頂点の中心を決めて、その頂点から同じ距離の頂点の中から最大の次数を求め、その次数(から親頂点への辺を除いたもの、葉は掛けない)を掛けあわせることで葉の数が計算できる。上図(1)では、 {3 \times (3-1) \times (3-1) = 6}と計算できる。

直径 {D}が奇数の時は中心の頂点が2個に一意に定まり、上図(2)のようになる。
直径 {D}が偶数の時、直径における頂点の中心は1個になるが、隣接する頂点とその頂点2個を中心にしても彩色数は最小にできるため、上図(1)もしくは(2)のいずれかの最小値を求める。

実装

計算量は {O(N^2)}

提出コード(Python3): Submission #2542412 - AtCoder Grand Contest 024 | AtCoder

N = int(input())
G = [[] for i in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
 
# 直径計算
from collections import deque
def bfs(v):
    que = deque([v])
    dist = {v: 0}
    prev = {v: v}
    while que:
        u = que.popleft()
        d = dist[u]
        for w in G[u]:
            if w in dist:
                continue
            dist[w] = d + 1
            prev[w] = u
            que.append(w)
    # vから最遠点(の1つ)uまでのパスを計算
    w = u
    D = []
    while w != v:
        D.append(w)
        w = prev[w]
    D.append(v)
    return u, D
 
from collections import deque
# 各距離の最大次数を求めて、その積を計算して解を計算
def solve(u, v = -1):
    que = deque([u])
    if v != -1:
        que.append(v)
    used = set([u, v])
    D = {v: 0, u: 0}
    E = {}
    if v != -1:
        E[0] = max(len(G[v]), len(G[u]))-1
    else:
        E[0] = len(G[u])
    x = v
    while que:
        v = que.popleft()
        d = D[v]
        for w in G[v]:
            if w in used:
                continue
            D[w] = d + 1
            que.append(w)
            used.add(w)
            E[d+1] = max(E.get(d+1, 0), len(G[w])-1)
    res = 2 if x != -1 else 1
    for v in E.values():
        if v: res *= v
    return res
 
D = bfs(bfs(0)[0])[1]
L = len(D)
 
col = (L + 1) // 2
 
if L % 2 == 1:
    ans = 10**18
    v = D[L//2]
    for w in G[v]:
        ans = min(ans, solve(v, w))
    ans = min(ans, solve(v))
else:
    v = D[L//2-1]; w = D[L//2]
    ans = solve(v, w)
print(col, ans)