結果

問題 No.1208 anti primenumber game
コンテスト
ユーザー persimmon-persimmon
提出日時 2021-06-23 16:32:52
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,235 ms / 2,000 ms
コード長 1,321 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 295 ms
コンパイル使用メモリ 82,240 KB
実行使用メモリ 388,216 KB
最終ジャッジ日時 2024-06-24 16:19:52
合計ジャッジ時間 20,900 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 44
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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)
      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")

"""
山が最後の一つになったら、ai-1個取るのが最適。素数かどうかはあまり考えなくてもいい？
順手は常に、ai-1個取るか、ai個取るか、1個取るかのいずれかを選ぶ。->DP
最左がa[i]とする。
最後の一個を取るのが現在の順手とすると。順手の最大取得点はa[i]-m
最後の一個を取るのが現在の逆手とすると。順手の最大取得点はa[i]-1

"""
0