kmjp's blog

競技プログラミング参加記です

TopCoder SRM 741 Div1 Easy DigitStringDiv1

なんか参加人数がさみしいことに。
http://community.topcoder.com/stat?c=problem_statement&pm=15142

問題


数字で構成された文字列Sと、整数Xが与えられる。
文字列Sの部分文字列を整数とみなしたとき、Xより大きな整数になるような部分列の選び方は何通りか。
部分列の抜き出し方は連続でなくてもよい。

解法

DPで解く。
f(n,k,flag) := Sのprefix n文字からk文字を部分文字列として抽出した場合で、かつflagがそのk文字がXの先頭k桁に比べ大きい・一致・小さいを表すとき、そのようなk文字の選び方

上記をnの小さい順にDPで埋めていけば、Xの桁数より大きな文字を抽出するか、Xの桁数と等しくかつより大きな整数を抽出した場合の組み合わせを計算できる。

ll dp[50][3];

class DigitStringDiv1 {
	public:
	long long count(string S, int X) {
		string T=to_string(X);
		ZERO(dp);
		dp[0][1]=1;
		int i;
		
		FORR(c,S) {
			
			for(i=48;i>=0;i--) {
				if(i==0 && c=='0') continue;
				if(i>=T.size()) {
					dp[i+1][2]+=dp[i][0]+dp[i][1]+dp[i][2];
				}
				else {
					dp[i+1][0]+=dp[i][0];
					dp[i+1][2]+=dp[i][2];
					if(T[i]==c) dp[i+1][1]+=dp[i][1];
					if(T[i]<c) dp[i+1][2]+=dp[i][1];
					if(T[i]>c) dp[i+1][0]+=dp[i][1];
				}
			}
		}
		
		ll ret=0;
		for(i=T.size();i<=49;i++) ret+=dp[i][2];
		return ret;
		
	}
}

まとめ

これ計算量O(|S|logX)なので、Sがもっと大きくてもよかったのにね。