ARC062 - E問題: AtCoDeerくんと立方体づくり / Building Cubes with AtCoDeer

問題: E - AtCoDeerくんと立方体づくり / Building Cubes with AtCoDeer

4頂点に色を持つN個のタイルを組み合わせ、全ての接するタイルの頂点の色を同じにしながら構成できる立方体は何通り存在するか、を計算する問題。

とりあえず自分の解法。ほぼ想定解法。

各タイルの頂点の色を管理する際、回転させて辞書順最小になるようにしておく。

まず、立方体で向かい合う2面を固定する。
この時、一方のタイルのインデックスをを決め、次にもう一方のタイルのインデックスをと決める。
残りの4面についても、インデックスがより大きくなるようにすることで、重複する立方体を除去する。
またインデックスのタイルについて、インデックスのタイルとの相対的な向きを4方向考慮する。

インデックスとインデックスの相対的な向きを決めてしまえば、全ての頂点の色が固定されているため、これらの頂点色から残りの4面を決定する。
4面について配置可能なタイル数と、4面の中で重複する配色の数を計算し、ここから通り数を計算する。

計算が重いのでPyPy3で通した。計算量は。
提出コード: Submission #2114117 - AtCoder Regular Contest 062

from collections import deque
N = int(input())
C = []
M = {}
for i in range(N):
    *c, = map(int, input().split())
    # 頂点の配色の中で、辞書順最小になるように回転
    c = tuple(min(c[j:] + c[:j] for j in range(1, 5)))
    C.append(c)
    if c not in M:
        M[c] = deque([i])
    else:
        M[c].append(i)
# 回転して何通りの置き方が存在するか
# [1] [0]
# [0] [1] => 2通り
#
# [0] [0]
# [0] [0] => 4通り
def count(p, q, r, s):
    if p == q == r == s:
        return 4
    if p == r and q == s:
        return 2
    return 1
def solve(ci, cj, k):
    # R[c] = d => 4面の内、配色cがd個存在
    R = {}
    for l in range(4):
        #   [l]   [l-1]
        # [k-l-1] [k-l]
        c = ci[l], ci[l-1], cj[k-l], cj[k-l-1]
        c = tuple(min(c[j:] + c[:j] for j in range(1, 5)))
        # 配置できるタイルが存在しない場合は0通り
        if c not in M:
            return 0
        R[c] = R.get(c, 0) + 1
    res = 1
    for c in R:
        # cnt: インデックスi+1以降で配置可能なタイル数
        m = M[c]
        cnt = len(m)
        # 配色cとインデックスjのタイルの配色が同じ => M[c]の中にjが含まれるので-1
        if c == cj:
            cnt -= 1
        # 配置するタイルが足りない場合は0通り
        if cnt < R[c]:
            return 0
        # k: 1面を回転して配置できる通り数
        k = count(*c)
        # 配色cの配置の通り数は Perm(cnt, R[c]) * k^{R[c]}
        for p in range(cnt-R[c]+1, cnt+1):
            res *= p * k
    return res
 
ans = 0
# インデックスiのタイルを固定
for i in range(N):
    ci = C[i]
    # 使わないインデックスiの情報を排除して探索する手間を省く
    q = M[ci]; q.popleft()
    if not q:
        del M[ci]
    # i+1, ..., N-1 の中からインデックスjのタイルとして固定
    for j in range(i+1, N):
        cj = C[j]
        # 相対的な向き4方向
        for k in range(4):
            ans += solve(ci, cj, k)
print(ans)