結果

問題 No.1267 Stop and Coin Game
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:31:07
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,553 bytes
コンパイル時間 173 ms
コンパイル使用メモリ 82,244 KB
実行使用メモリ 86,772 KB
最終ジャッジ日時 2025-03-20 20:32:13
合計ジャッジ時間 5,438 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 6 TLE * 1 -- * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx +=1
    V = int(input[idx])
    idx +=1
    A = list(map(int, input[idx:idx+N]))
    
    max_mask = 1 << N
    sum_mask = [0] * max_mask
    for mask in range(max_mask):
        s = 0
        for i in range(N):
            if mask & (1 << i):
                s += A[i]
        sum_mask[mask] = s
    
    # Generate mask_order sorted by number of set bits in descending order
    mask_order = []
    for bit_count in range(N, -1, -1):
        for mask in range(max_mask):
            if bin(mask).count('1') == bit_count:
                mask_order.append(mask)
    
    memo = {}
    full_mask = (1 << N) -1
    
    for mask in mask_order:
        current_sum = sum_mask[mask]
        if current_sum > V:
            continue  # Skip invalid states
        if mask == full_mask:
            if current_sum <= V:
                memo[mask] = 'draw'
            else:
                continue  # This state is not possible
        else:
            is_win = False
            can_draw = False
            any_move = False
            for i in range(N):
                if not (mask & (1 << i)):
                    new_sum = current_sum + A[i]
                    if new_sum > V:
                        continue
                    any_move = True
                    next_mask = mask | (1 << i)
                    if next_mask == full_mask:
                        if new_sum <= V:
                            can_draw = True
                    else:
                        # Check memo for the next state
                        next_outcome = memo.get(next_mask, 'lose')
                        if next_outcome == 'lose':
                            is_win = True
                        elif next_outcome == 'draw':
                            can_draw = True
            # Determine the outcome for the current mask
            if is_win:
                memo[mask] = 'win'
            else:
                if can_draw:
                    memo[mask] = 'draw'
                else:
                    if any_move:
                        memo[mask] = 'lose'
                    else:
                        # No valid moves, player has to choose and lose
                        memo[mask] = 'lose'
    
    initial_outcome = memo.get(0, 'draw')
    if initial_outcome == 'win':
        print("First")
    elif initial_outcome == 'lose':
        print("Second")
    else:
        print("Draw")

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