結果

問題 No.973 余興
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 13:19:31
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,414 bytes
コンパイル時間 488 ms
コンパイル使用メモリ 82,212 KB
実行使用メモリ 488,116 KB
最終ジャッジ日時 2025-06-12 13:21:49
合計ジャッジ時間 10,875 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other TLE * 1 -- * 53
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

n, X = map(int, input().split())
a = list(map(int, input().split()))
N = n

# Precompute cumulative sums from left and right
sum_left = [0] * (N + 1)
for i in range(1, N + 1):
    sum_left[i] = sum_left[i - 1] + a[i - 1]

sum_right = [0] * (N + 1)
for i in range(1, N + 1):
    sum_right[i] = sum_right[i - 1] + a[N - i]

# Initialize DP tables for A and B
dpA = [[False] * (N + 1) for _ in range(N + 1)]
dpB = [[False] * (N + 1) for _ in range(N + 1)]

# Base case: empty interval, the current player wins
for l in range(N + 1):
    dpA[l][l] = True  # A's turn, no puffs left → A wins (last eaten by B)
    dpB[l][l] = True  # B's turn, no puffs left → B wins (last eaten by A)

# Fill DP tables for intervals of increasing length
for d in range(1, N + 1):
    for l in range(N - d + 1):
        r = l + d

        # Update dpA[l][r] for player A's turn
        # Check left end
        target_left = sum_left[l] + X
        k_left = bisect.bisect_right(sum_left, target_left) - l - 1
        k_left = max(0, min(k_left, d))
        if k_left > 0:
            new_l = l + k_left
            if not dpB[new_l][r]:
                dpA[l][r] = True
        if not dpA[l][r]:
            # Check right end
            pos = N - r
            base = sum_right[pos]
            target_right = base + X
            k_right = bisect.bisect_right(sum_right, target_right) - pos - 1
            k_right = max(0, min(k_right, d))
            if k_right > 0:
                new_r = r - k_right
                if not dpB[l][new_r]:
                    dpA[l][r] = True

        # Update dpB[l][r] for player B's turn
        # Check left end
        target_left = sum_left[l] + X
        k_left = bisect.bisect_right(sum_left, target_left) - l - 1
        k_left = max(0, min(k_left, d))
        if k_left > 0:
            new_l = l + k_left
            if not dpA[new_l][r]:
                dpB[l][r] = True
        if not dpB[l][r]:
            # Check right end
            pos = N - r
            base = sum_right[pos]
            target_right = base + X
            k_right = bisect.bisect_right(sum_right, target_right) - pos - 1
            k_right = max(0, min(k_right, d))
            if k_right > 0:
                new_r = r - k_right
                if not dpA[l][new_r]:
                    dpB[l][r] = True

# Determine the winner based on the initial state
print("A" if dpA[0][N] else "B")
0