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;
}