UnKoder #01 A FT Robot

2015/04/15 (Wed) hackerrank UnKoder DP 貪欲

問題

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