UVa11863 Prime Game

問題
http://uva.onlinejudge.org/external/118/11863.html

解法
区間DP（メモ化再帰）左右から区間を狭めていくだけ。
自分がパスしたら相手もパスするので、パス可能最大回数 K という情報に意味は無い。
数列に42が含まれる場合、ワイルドカードなので、はじめから全部の数列を一度に消すように数字をあてがうことが出来るため Soha が必ず勝利する。

反省
誤読してた。「消せなくなったら終わり」を「数列を最後まで取られたら...」みたいな意味と勘違いしてた。これだと問題の意図がわからなくなってしまうので常識的に考えて気づくべきだった。

#include <bits/stdc++.h>
  
using namespace std;
  
#define MAX (1100000)
  
bool isp[MAX];
  
void Sieve() {
    
  fill(isp, isp+MAX, 1);
  isp[0] = isp[1] = 0;
  for(int i=2; i*i<=MAX; i++)
    if(isp[i]) {
      for(int j=i*i; j<=MAX; j+=i)
        isp[j] = 0;
    }
}
  
int memo[110][110];
int input[110];
  
int rec(int l, int r) {
   
  if(l == r) return 0;
   
  int& ret = memo[l][r];
  if(ret != -1) { return ret; }
    
  ret = 0;
  int s = 0;
  for(int i=l; i<r; i++) {
    s += input[i];
    if(s > 0 && isp[s]) { ret = ret || !rec(i+1, r); }
  }
    
  s = 0;
  for(int i=r-1; i>=l; i--) {
    s += input[i];
    if(s > 0 && isp[s]) { ret = ret || !rec(l, i); }
  }
    
  return ret;
}
  
int main() {
    
  Sieve();
  int Tc; cin >> Tc;
  for(int Tcnt=1; Tcnt<=Tc; Tcnt++) {
    cout << "Case " << Tcnt << ": ";
    int N, K; cin >> N >> K;
    memset(memo, -1, sizeof memo);
    bool soha42 = false;
    for(int i=0; i<N; i++) {
      cin >> input[i];
      soha42 = soha42 || (input[i] == 42);
    }
    if(soha42) { puts("Soha"); goto EXIT; }
     
    // Soha = 1
    cout << ( rec(0, N) ? "Soha" : "Tara" ) << endl;
      
  EXIT:;
  }
    
  return 0;
}