結果

問題 No.3041 非対称じゃんけん
コンテスト
ユーザー SourCreamOnion
提出日時 2025-03-01 16:36:21
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 1,464 bytes
コンパイル時間 308 ms
コンパイル使用メモリ 12,160 KB
実行使用メモリ 18,728 KB
最終ジャッジ日時 2025-03-01 16:36:29
合計ジャッジ時間 7,310 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 20 TLE * 1 -- * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

def solve(N, F, A, B, C):
    size = (F * N) // 64 + 1
    
    # masks[i] は i ビット分 1 が立っているマスク
    masks = [(1 << i) - 1 for i in range(65)]

    # dp 初期化
    dp = [0] * size
    nextdp = [0] * size
    
    # 初期位置の設定 (63 - A[0]の位置を立てる)
    dp[0] |= 1 << (63 - A[0])
    dp[0] |= 1 << (63 - B[0])
    dp[0] |= 1 << (63 - C[0])

    # 最初のpopcount
    print(bin(dp[0]).count('1'))

    for k in range(1, N):
        a, b, c = A[k], B[k], C[k]

        # A[i] による遷移
        nextdp[0] = dp[0] >> a
        for i in range(1, size):
            nextdp[i] = (dp[i] >> a) | ((dp[i-1] & masks[a]) << (64 - a))

        # B[i] による遷移
        nextdp[0] |= dp[0] >> b
        for i in range(1, size):
            nextdp[i] |= (dp[i] >> b) | ((dp[i-1] & masks[b]) << (64 - b))

        # C[i] による遷移
        nextdp[0] |= dp[0] >> c
        for i in range(1, size):
            nextdp[i] |= (dp[i] >> c) | ((dp[i-1] & masks[c]) << (64 - c))

        # popcount
        ans = sum(bin(x).count('1') for x in nextdp)
        print(ans)

        # dpを更新
        dp, nextdp = nextdp, [0] * size
LMI=lambda:list(map(int, input().split()))
LMS=lambda:list(map(str, input().split()))
MI=lambda:map(int, input().split())
MS=lambda:map(str, input().split())
II=lambda:int(input())
IS=lambda:input().split()
LI=lambda:list(input())
N,F=MI()
A=LMI()
B=LMI()
C=LMI()

solve(N, F, A, B, C)
0