結果

問題 No.234 めぐるはめぐる (4)
ユーザー maspymaspy
提出日時 2020-05-08 02:07:30
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 18 ms / 1,000 ms
コード長 2,418 bytes
コンパイル時間 95 ms
コンパイル使用メモリ 10,860 KB
実行使用メモリ 8,096 KB
最終ジャッジ日時 2023-09-16 08:16:23
合計ジャッジ時間 754 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 18 ms
8,092 KB
testcase_01 AC 16 ms
8,096 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# -1: 未使用
# -2：次数2
# それ以外：パスのもうひとつの端点を持つ

def solve(N):
    from collections import defaultdict
    N += 2

    def add_edge(A, u, v, k):
        # A[i] が i+k を指す
        # -1: 異常終了、0:正常終了、1:サイクルを見つけて正常終了
        if A[u - k] == -2 or A[v - k] == -2:
            return -1
        if A[u - k] == A[v - k] == -1:
            # 新しい成分
            A[u - k] = v
            A[v - k] = u
            return 0
        if A[v - k] == -1:
            u, v = v, u
        if A[u - k] == -1:
            w = A[v - k]
            A[w - k] = u
            A[u - k] = w
            A[v - k] = -2
            return 0
        w1, w2 = A[u - k], A[v - k]
        if w1 == v:
            A[u - k] = A[v - k] = -2
            return 1
        A[u - k] = A[v - k] = -2
        A[w1 - k] = w2
        A[w2 - k] = w1
        return 0

    def can_use(v):
        row, col = divmod(v, N)
        return 1 <= col <= row

    init = (-1, ) * (N + 2)
    dp = defaultdict(int)
    dp[init] = 1
    ret = 0
    for n in range(N + 1, N**2):
        omit = n - N - 1
        print(N - 2, n, ret, len(dp))
        row, col = divmod(n, N)
        for dx in [1, N, N + 1]:
            newdp = dp.copy()
            for A, cnt in dp.items():
                B = list(A)
                assert n + 1 - len(B) == omit
                if not (can_use(n) and can_use(n - dx)):
                    continue
                t = add_edge(B, n, n - dx, omit)
                if t == -1:
                    continue
                if t == 1:
                    cycle = True
                    if any(x >= 0 for x in B):
                        continue
                    ret += cnt
                    continue
                newdp[tuple(B)] += cnt
            dp = newdp
        newdp = defaultdict(int)
        for A, cnt in dp.items():
            # 今後回収できない端点
            if A[0] >= 0:
                continue
            newdp[A[1:] + (-1, )] += cnt
        dp = newdp
    return ret

A = [
    1, 1, 11, 110, 2402, 128967, 16767653, 5436906668, 4406952731948,
    8819634719356421, 43329348004927734247, 522235268182347360718818,
    15436131339319739257518081878
]

N = int(read())
print(A[N])
0