WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM 557 Div2 Hard "FoxAndMountain"

問題(超意訳)

'U'と'D'を同じ数だけ使って長さNの文字列を作る。
つまり'U'と'D'をそれぞれN/2個ずつ使うのだが、
文字列を作っていく途中で、'D'の数が'U'の数を上回ってはならない。
例)
UUDDUD おk
UDDUUD だめ UDDまで作った時にDがUより多くなってる。

また、'U''D'から成るキーワードが与えられる。
このキーワードを部分文字列として含むような文字列が、
何個できるかを返せ。

制約

1 <= 作る文字列の長さ、キーワードの長さ <= 50

顛末

半日かけたけど結局できない・・
どうやって重複なくまた取りこぼしなく数え上げるのか、
全く分からんかった。

takapt0226さんのこの記事を参考にしました。(つーかほぼ丸写し)

カンニング(長時間ガン見)しつつのソースコード
const int MAX_N = 50;
const int MOD = 1000000009;

int dp[MAX_N+1][MAX_N+1][MAX_N+1];
int ne[MAX_N+1][2];

class FoxAndMountain {
public:

    void add( int& i, int j ){
        i += j;
        i %= MOD;
    }

    int count(int n, string history){
        int m = history.length();
        for( int i = 0; i < m; i++ ){
            int go = 0, ng = 1;
            char c = 'U';
            if( history[i] == 'U' ){
                go = 1; ng = 0; c ='D';
            }
            ne[i][go] = i+1;

            int t = 0;
            for( int j = i-1; j >= 0 && t == 0; j-- ){
                if( history[j] != c ) continue;
                bool ok = true;
                for( int k = 1; k <= j; k++ ){
                    if( history[j-k] != history[i-k] ){
                        ok = false; break;
                    }
                }
                if( ok ) t = j + 1;
            }
            ne[i][ng] = t;
        }
        ne[m][0] = ne[m][1] = m;

        memset( dp, 0, sizeof(dp) );
        dp[0][0][0] = 1;
        for( int i = 0; i < n; i++ ){
            for( int j = 0; j <= n; j++ ){
                for( int k = 0; k <= m; k++ ){
                    if( j - 1 >= 0 ) add( dp[i+1][j-1][ne[k][0]], dp[i][j][k] );
                    if( j + 1 <= n ) add( dp[i+1][j+1][ne[k][1]], dp[i][j][k] );
                }
            }
        }

        return dp[n][0][m];
    }
};