結果

問題 No.973 余興
コンテスト
ユーザー lam6er
提出日時 2025-04-15 23:17:43
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 5,172 bytes
コンパイル時間 192 ms
コンパイル使用メモリ 81,616 KB
実行使用メモリ 485,596 KB
最終ジャッジ日時 2025-04-15 23:19:13
合計ジャッジ時間 10,816 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other TLE * 1 -- * 53
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    N, X = map(int, sys.stdin.readline().split())
    a = list(map(int, sys.stdin.readline().split()))
    a = [0] + a  # 1-based index

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

    S_right = [0] * (N + 2)  # S_right[i] is sum from a[i] to a[N]
    for i in range(N, 0, -1):
        S_right[i] = S_right[i+1] + a[i]

    # DP_A[l][r]: A's turn, can win?
    DP_A = [[False]*(N+2) for _ in range(N+2)]
    DP_B = [[False]*(N+2) for _ in range(N+2)]

    for len_ in range(0, N+1):
        for l in range(1, N+1):
            r = l + len_ - 1
            if r > N:
                continue
            if l > r:
                # No creampuffs left, current player wins
                DP_A[l][r] = True
                DP_B[l][r] = True
                continue

            # Compute for A's turn
            can_win_A = False

            # Check left
            max_left = 0
            low, high = 1, len_
            while low <= high:
                mid = (low + high) // 2
                if l + mid - 1 > N:
                    high = mid - 1
                    continue
                s = S_left[l + mid - 1] - S_left[l-1]
                if s <= X:
                    max_left = mid
                    low = mid + 1
                else:
                    high = mid - 1
            if max_left >= 1:
                # Check k=1 and k=max_left
                for k in [1, max_left]:
                    if k > max_left:
                        continue
                    new_l = l + k
                    new_r = r
                    if new_l > new_r:
                        # A takes all, loses
                        continue
                    if not DP_B[new_l][new_r]:
                        can_win_A = True
                        break
            if not can_win_A:
                # Check right
                max_right = 0
                low, high = 1, len_
                while low <= high:
                    mid = (low + high) // 2
                    start = r - mid + 1
                    if start < 1:
                        high = mid - 1
                        continue
                    s = S_right[start] - S_right[r+1]
                    if s <= X:
                        max_right = mid
                        low = mid + 1
                    else:
                        high = mid - 1
                if max_right >= 1:
                    for k in [1, max_right]:
                        if k > max_right:
                            continue
                        new_l = l
                        new_r = r - k
                        if new_l > new_r:
                            # A takes all, loses
                            continue
                        if not DP_B[new_l][new_r]:
                            can_win_A = True
                            break
            DP_A[l][r] = can_win_A

            # Compute for B's turn
            can_win_B = False

            # Check left
            max_left = 0
            low, high = 1, len_
            while low <= high:
                mid = (low + high) // 2
                if l + mid - 1 > N:
                    high = mid - 1
                    continue
                s = S_left[l + mid - 1] - S_left[l-1]
                if s <= X:
                    max_left = mid
                    low = mid + 1
                else:
                    high = mid - 1
            if max_left >= 1:
                for k in [1, max_left]:
                    if k > max_left:
                        continue
                    new_l = l + k
                    new_r = r
                    if new_l > new_r:
                        # B takes all, loses
                        continue
                    if not DP_A[new_l][new_r]:
                        can_win_B = True
                        break
            if not can_win_B:
                # Check right
                max_right = 0
                low, high = 1, len_
                while low <= high:
                    mid = (low + high) // 2
                    start = r - mid + 1
                    if start < 1:
                        high = mid - 1
                        continue
                    s = S_right[start] - S_right[r+1]
                    if s <= X:
                        max_right = mid
                        low = mid + 1
                    else:
                        high = mid - 1
                if max_right >= 1:
                    for k in [1, max_right]:
                        if k > max_right:
                            continue
                        new_l = l
                        new_r = r - k
                        if new_l > new_r:
                            # B takes all, loses
                            continue
                        if not DP_A[new_l][new_r]:
                            can_win_B = True
                            break
            DP_B[l][r] = can_win_B

    if DP_A[1][N]:
        print("A")
    else:
        print("B")

if __name__ == "__main__":
    main()
0