結果

問題 No.761 平均値ゲーム
コンテスト
ユーザー lam6er
提出日時 2025-03-26 15:59:08
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,241 bytes
コンパイル時間 332 ms
コンパイル使用メモリ 82,512 KB
実行使用メモリ 92,160 KB
最終ジャッジ日時 2025-03-26 16:00:03
合計ジャッジ時間 10,587 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 96 WA * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import bisect

def main():
    import sys
    sys.setrecursionlimit(1 << 25)
    N = int(sys.stdin.readline())
    A = list(map(int, sys.stdin.readline().split()))
    S = [0] * (N + 1)
    for i in range(1, N + 1):
        S[i] = S[i-1] + A[i-1]
    memo = {}
    
    def can_win(l, r):
        if l > r:
            return False
        if (l, r) in memo:
            return memo[(l, r)]
        sum_total = S[r] - S[l-1]
        k = r - l + 1
        ceil_avg = (sum_total + k - 1) // k
        floor_avg = sum_total // k
        
        # Operation (i): Remove elements >= ceil_avg
        m0 = bisect.bisect_left(A, ceil_avg, l-1, r)
        if m0 <= r - 1:
            new_l, new_r = l, m0
            if not can_win(new_l, new_r):
                memo[(l, r)] = True
                return True
        
        # Operation (ii): Remove elements <= floor_avg
        x = floor_avg
        m0 = bisect.bisect_right(A, x, l-1, r)
        if m0 >= l:
            new_l, new_r = m0 + 1, r
            if not can_win(new_l, new_r):
                memo[(l, r)] = True
                return True
        
        memo[(l, r)] = False
        return False
    
    result = can_win(1, N)
    print('First' if result else 'Second')

main()
0