TCO11 Qual2 Medium(500) KindAndCruel

KindAndCruel

動的計画法。それぞれの位置に到達可能かどうかを覚えておく。同じ位置にK*C秒後に居ても意味は無いので、K*Cで少なくとも１マスは進むはず。K*C*n秒後にも右端に到達できなければ到達不可。

#include <string>
#include <vector>
using namespace std;

class KindAndCruel{public:
int crossTheField( string field, int K, int C )
{
    int n = (int)field.size();

    vector<bool> T( n, false );
    T[0] = true;

    for ( int t=1; t<=K*C*n; t++ )
    {
        vector<bool> P = T;
        T.clear();
        for ( int i=0; i<n; i++ )
            T.push_back(
                ( field[i]!='K' || t%K!=0 )  &&
                ( field[i]!='C' || t%C==0 )  &&
                ( 0<i && P[i-1] || P[i] || i<n-1 && P[i+1] ) );

        if ( T[n-1] )
            return t;
    }

    return -1;
}};