Beta Round #68-B: Train
解法
プレイヤーは二人かと思ったけど実際は一人。時刻と位置で探索するだけ。
#include <cstdio> #include <algorithm> #include <vector> #include <cstring> using namespace std; const int INF = 1<<29; int M, N, K, T; bool toHead; char buf[20]; char line[1000]; int win[300][70]; int where[300]; int rec(int t, int n){ if(win[t][n]) return win[t][n]; if(t == T){ return win[t][n] = T; } if(where[t] == n){ return win[t][n] = t; } if(line[t] == '0'){ int ma = -INF; ma = max(ma, rec(t+1, n)); if(n>0 && where[t] != n-1)ma = max(ma, rec(t+1, n-1)); if(n<N-1 && where[t] != n+1)ma = max(ma, rec(t+1, n+1)); return win[t][n] = ma; } else{ int ma = -INF; for(int i=0; i<N; i++){ ma = max(ma, rec(t+1, i)); } return win[t][n] = ma; } } void solve(){ bool ok = true; for(int i=0; i<T; i++){ if(line[i] == '0') ok = false; } if(ok){ puts("Stowaway"); return ; } int ans = rec(0, M); if(ans == T){ puts("Stowaway"); } else{ printf("Controller %d\n", ans); } } int main(){ scanf("%d%d%d ",&N,&M,&K); scanf("%s ", buf); scanf("%s ", buf); toHead = !strcmp(buf, "head"); scanf("%s ", line); T = strlen(line); for(int i=0; i<300; i++){ for(int j=0; j<70; j++){ win[i][j] = 0; } } M--; K--; int dir = toHead?-1:1; int cur = K; for(int t=0; t<T; t++){ where[t] = cur; cur += dir; if(cur==0 || cur == N-1) dir *= -1; } solve(); return 0; }