UnKoder #01 A FT Robot
問題
sugim さんのコンテスト。名前は汚いですが問題はとても面白かった。
方針
- $ dp(i,j,0) = $ $i$ 番目の命令の後に位置 $j$ に前を向いていれる
- $ dp(i,j,1) = $ $i$ 番目の命令の後に位置 $j$ に後ろを向いていれる
で更新していった。DP ではない頭がいい方法もあります。
実装
int main(){
string s;
while(cin >> s){
bool dp[120][2] = {};
// 0 : -->, 1 : <--
dp[60][0] = true;
for(char c:s){
bool dp2[130][2] = {};
rep(i,129){
if(c=='?' || c=='F') dp2[i+1][0] |= dp[i][0];
if(c=='?' || c=='T') dp2[i][1] |= dp[i][0];
if(c=='?' || c=='F') if(i-1 >= 0) dp2[i-1][1] |= dp[i][1];
if(c=='?' || c=='T') dp2[i][0] |= dp[i][1];
}
rep(i,120)rep(j,2) dp[i][j] = dp2[i][j];
}
int ans = -100;
loop(i,-60,60)rep(j,2) if(dp[i+60][j]) ans = max<int>(ans, i);
cout << ans << endl;
}
}