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