WARush

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

Codeforces #179 Div2 B "Yaroslav and Two Strings"

問題

http://codeforces.com/contest/296/problem/B

長さNで数字ばかりの2つ文字列s, wがあるとする。
この文字列で、s( i ) > w( i ), s( j ) < w( j ) となるような、
i, j ( 1 <= i, j <= N and i != j ) が存在した場合、
文字列s, wはnon-comparebleであるとする。
ちなみに、
s(i)とは文字列sのi番目の数字であり、w( j )とは文字列wのj番目の数字を表す。

数字と、' ? 'を含んだ長さnのテンプレと呼ばれる文字列が2つある。
このテンプレの' ? 'を数字に置き換えて、
non-comparebleな2つの文字列を作る時に、
その作り方が何パターンあるかを返せ。
その文字列は、' 0 'が先頭にあってもよい。

制約

1 <= n <= 10^5



考えた事

むず!
むずくないこれ?


・・・と思いつつも、
あるブログで
問題BはDPだ
と言う事をチラ見していた俺は
そんなにあせっていなかった・・


あれ!やっぱむずい!
どうしようこれ!


2つのテンプレをそれぞれs, wとすると、
今考えているindexまでに、

0. s( i ) < w( i )  s( j ) > w( j ) のどっちもまだ出来てない。
1. s( i ) < w( i ) だけ出来てる。
2. s( j ) > w( j ) だけ出来てる。
3. もうnon-comparebleになっちょる。

の4パターンにわけて、更新していこう。


ソースコード

typedef long long ll;

const int MOD = 1000000007;

int N;
char s[100050];
char w[100050];
ll dp[100050][4];

void add( ll& a, ll b ){
    a += b;
    a %= MOD;
}

int main() {
    // 入力
    cin >> N;
    for( int i = 0; i < N; i++ ){
        cin >> s[i];
    }
    for( int i = 0; i < N; i++ ){
        cin >> w[i];
    }

    // dp初期化
    memset( dp, 0, sizeof(dp) );
    dp[0][0] = 1;

    // dp更新
    for( int i = 0; i < N; i++ ){
        int ng=0, small=0, large=0;
        if( s[i] == '?' && w[i] == '?' ){
            ng = 10; small = 45; large = 45;
        }else if( s[i] == '?' ){
            int wd = w[i] - '0';
            ng = 1; small = wd; large = 9 - wd;
        }else if( w[i] == '?' ){
            int sd = s[i] - '0';
            ng = 1; small = 9 - sd; large = sd;
        }else{
            int sd = s[i] - '0';
            int wd = w[i] - '0';
            if( sd < wd ){
                small = 1;
            }else if( sd > wd ){
                large = 1;
            }else{
                ng = 1;
            }
        }

        // 0
        add( dp[i+1][0], dp[i][0] * ng );
        add( dp[i+1][1], dp[i][0] * small );
        add( dp[i+1][2], dp[i][0] * large );

        // 1
        add( dp[i+1][1], dp[i][1] * ng );
        add( dp[i+1][1], dp[i][1] * small );
        add( dp[i+1][3], dp[i][1] * large );

        // 2
        add( dp[i+1][2], dp[i][2] * ng );
        add( dp[i+1][3], dp[i][2] * small );
        add( dp[i+1][2], dp[i][2] * large );

        // 3
        add( dp[i+1][3], dp[i][3] * ng );
        add( dp[i+1][3], dp[i][3] * small );
        add( dp[i+1][3], dp[i][3] * large );
    }

    cout << dp[N][3] << endl;
}