Submission #17514524


Source Code Expand

Copy
import sys
from functools import lru_cache
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@lru_cache(None)
def win(tpl):
    if not tpl:
        return False, -1
    while tpl[0] == 0:
        return win(tpl[1:])
    li = list(tpl)
    for k in range(tpl[0]):
        li[0] = k
        res = win(tuple(li[::-1]))
        if not res[0]:
            return True, k
    return False, -1

@njit((i8[:],), cache=True)
def solve(A):
    N = len(A)
    if N == 1:
        return True
    if N == 2:
        return A[0] > A[1]
    """
    a, b >= 1 に対して
    a + [L,R] + b が後手勝ちである条件は、ある p, q を用いて
    b >= p and b - a >= q と書ける。この p, q を dp で求めていく
    a が先手側の山
    """
    dp = np.zeros((N, N, 2), np.int64)
    dp_rev = np.zeros((N, N, 2), np.int64)
    A_rev = A[::-1]
    # 長さ 1 の区間
    for i in range(N):
        x = A[i]
        dp[i,i] = (x+1, 0)
        x = A_rev[i]
        dp_rev[i, i] = (x+1,0)
        
    for n in range(2, N+1):
        # 長さ n の区間
        for L in range(N - n + 1):
            for rev in range(2):
                """逆向きの dp の実装をまとめる!"""
                dp, dp_rev, A, A_rev = dp_rev, dp, A_rev, A
                
                R = L + n - 1
                if L == 0 or R == N - 1:
                    continue
                #p1, q1 = dp_rev[L+1,R]
                p1, q1 = dp_rev[N-1-R,N-L-2]
                # 先手は、山を消化した時点で後手が b_max 以下なら勝てる
                X = A[L]
                b_max = X - q1
                if X < p1:
                    b_max = 0
                # 後手は、山を消化した時点で先手が a_max 以下なら勝てる
                p2, q2 = dp[L,R-1]
                X = A_rev[N-1-R]
                a_max = X - q2
                if X < p2:
                    a_max = 0
                a_max = max(a_max, 0)
                b_max = max(b_max, 0)
                if a_max == b_max == 0:
                    # どちらにとっても、山を消化したくない場合
                    k, l = 0, 0
                    dp[L,R] = (k,l)
                elif a_max == 0 and b_max > 0:
                    # 先手は山消費で勝てる可能性がある。後手は山を消費したくない。
                    # 後手が勝つのは、ひとつずつ取っていって、a = 0 の瞬間に b > b_max である場合
                    # b - a + 1 > b_max のときに後手が勝ち
                    dp[L,R] = (0, b_max)
                    continue
                elif a_max > 0 and b_max == 0:
                    # 先手が勝てるのは、後手が必ず先に使い切って、そのときに a_max + 1 以上のこる場合
                    # a - b >= a_max + 1
                    # 後手が勝つのは、a - b < a_max + 1 の場合
                    dp[L,R] = (0, -a_max)
                else:
                    # どちらも山を使い切って勝つ可能性がある。
                    # 後手が勝つには、まず b > b_max が必要
                    # b > b_max である場合、b = b_max になる前に a < a_max になってることが勝利条件
                    # b >= b_max + 1 and a - b + b_max <= a_max
                    # b >= b_max + 1 and b - a >= b_max-a_max
                    dp[L,R] = (b_max+1, b_max - a_max)
    p, q = dp[1,-2]
    a, b = A[0], A[-1]
    sec_win = (b >= p) and (b - a >= q)
    return not sec_win

def main():
    T = int(readline())
    for _ in range(T):
        N = int(readline())
        A = np.array(readline().split(), np.int64)
        print('First' if solve(A) else 'Second')

main()

Submission Info

Submission Time
Task D - Pocky Game
User maspy
Language Python (3.8.2)
Score 900
Code Size 3964 Byte
Status AC
Exec Time 555 ms
Memory 106764 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 900 / 900
Status
AC × 1
AC × 25
Set Name Test Cases
Sample 00-sample-001.txt
All 00-sample-001.txt, 01-001.txt, 01-002.txt, 01-003.txt, 01-004.txt, 01-005.txt, 01-006.txt, 01-007.txt, 01-008.txt, 01-009.txt, 01-010.txt, 01-011.txt, 01-012.txt, 01-013.txt, 01-014.txt, 01-015.txt, 01-016.txt, 01-017.txt, 01-018.txt, 01-019.txt, 01-020.txt, 01-021.txt, 01-022.txt, 01-023.txt, 01-024.txt
Case Name Status Exec Time Memory
00-sample-001.txt AC 544 ms 105308 KB
01-001.txt AC 518 ms 105732 KB
01-002.txt AC 515 ms 105756 KB
01-003.txt AC 537 ms 105768 KB
01-004.txt AC 536 ms 106428 KB
01-005.txt AC 539 ms 105936 KB
01-006.txt AC 539 ms 105732 KB
01-007.txt AC 549 ms 105788 KB
01-008.txt AC 537 ms 106356 KB
01-009.txt AC 542 ms 105720 KB
01-010.txt AC 544 ms 105696 KB
01-011.txt AC 539 ms 106348 KB
01-012.txt AC 539 ms 105300 KB
01-013.txt AC 545 ms 106100 KB
01-014.txt AC 544 ms 106108 KB
01-015.txt AC 549 ms 106316 KB
01-016.txt AC 546 ms 106724 KB
01-017.txt AC 555 ms 106764 KB
01-018.txt AC 545 ms 106748 KB
01-019.txt AC 542 ms 105636 KB
01-020.txt AC 548 ms 105980 KB
01-021.txt AC 544 ms 105572 KB
01-022.txt AC 548 ms 106080 KB
01-023.txt AC 552 ms 106276 KB
01-024.txt AC 548 ms 106088 KB