結果

問題 No.1208 anti primenumber game
ユーザー persimmon-persimmon
提出日時 2021-06-23 16:26:06
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 876 bytes
コンパイル時間 366 ms
コンパイル使用メモリ 82,372 KB
実行使用メモリ 322,024 KB
最終ジャッジ日時 2024-06-24 16:06:57
合計ジャッジ時間 18,699 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36 WA * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(10**7)
def main1(n,m,a):
  if all(x>1 for x in a):return True
  memo={}
  def dp(a,i):
    # a[i:]以降だけ考えたとき、互いが最適に行動したときの、（順手の獲得点、逆手の獲得点）
    if i==n:return 0,0
    if (a[i],i) in memo:return memo[(a[i],i)]
    if a[i]==1:
      # 石一個取るしかない。
      x,y=dp(a,i+1)
      ret=[y+a[i]-m,x]
    else:
      # 石ai個取る
      x,y=dp(a,i+1)
      ret=[y+a[i]-m,x]
      # 石ai-1個取る
      tmp=a[i]
      a[i]=1
      x,y=dp(a,i+1)
      a[i]=tmp
      if ret[0]<y+a[i]-1:
        ret=[y+a[i]-1,x]
    memo[(a[i],i)]=ret
    return ret
  ret=dp(a,0)
  return ret[0]>ret[1]

if __name__=='__main__':
  n,m=map(int,input().split())
  a=list(map(int,input().split()))
  ret1=main1(n,m,a)
  if ret1:
    print("First")
  else:
    print("Second")
0