halcの競プロ精進ブログ

はるくが競プロしたことを書き留めるなにか

【今日の精進】ARC062E - Building Cubes with AtCoDeer / AtCoDeerくんと立方体づくり

競プロ 今日の精進 ARC 橙Diff

毎日格上の問題を倒すやつの61日目です。

問題リンク

atcoder.jp

問題概要

四隅に色がついたタイルが N 枚あるよ。

これを組み合わせて隅に集まる色が同じ立方体を作りたいよ。

どのタイルにも向きがあるとき、作れる立方体が何通りか答えてね。

解法

上のタイル(向きは1方向)、下のタイルとその向きを固定します。

そうすると8頂点の色が確定するので、事前にタイルをdictで分類したうえで、組み合わせを適切に掛け算すればよいです。

この場合、各立方体は6回数えられます。

提出コード

def swap(tile,num):
    num%=4
    return tile[num:]+tile[:num]

def type(tile):
    if tile[0]==tile[1]==tile[2]==tile[3]:
        return 4
    elif tile[0]==tile[2] and tile[1]==tile[3]:
        return 2
    return 1

def tile_sr(tile):
    mini=pow(2,61)-1
    ret=tile
    for i in range(4):
        now=swap(tile,i)
        num=0
        for j in range(4):
            num*=10000
            num+=now[j]
        if mini>num:
            mini=num
            ret=now
    return ret

N=int(input())
col=[tuple(map(int,input().split())) for i in range(N)]
ser={}
for i in range(N):
    for j in range(4):
        if swap(col[i],j) in ser:
            ser[swap(col[i],j)].add(i)
        else:
            ser[swap(col[i],j)]={i}
ans=0
for i in range(N):
    for j in range(N):
        if i==j:
            continue
        for k in range(4):
            tiles=[]
            ng=0
            for l in range(4):
                tiles.append(swap(col[i],l)[2:][::-1]+swap(col[j],k-l)[2:][::-1])
                tiles[-1]=tile_sr(tiles[-1])
                if tiles[-1] not in ser:
                    ng=1
                    break
            if ng==1:
                continue
            now=1
            dic={}
            for l in tiles:
                if l not in dic:
                    dic[l]=len(ser[l])
                    if i in ser[l]:
                        dic[l]-=1
                    if j in ser[l]:
                        dic[l]-=1
                now*=dic[l]*type(l)
                dic[l]-=1
            ans+=now
print(ans//6)

Submission #47773971 - AtCoder Regular Contest 062

感想

もうちょっと実行時間を早くだな…

空いた日にやってたこと

59日目

60日目