yukicoder : No.319 happy b1rthday 2 me

妙にバグバグで手間取った。
http://yukicoder.me/problems/850

問題

2つの正整数A,Bが与えられる。
A,A+1,A+2,...,Bを文字列と見なして順に連結した文字列を作ったとき、その中に"12"となる連続部分文字列は何個あるか求めよ。

解法

定番テクとして、0～vを連結した場合の"12"の登場回数をf(v)とすると、一見(f(B)-f(A-1))が解となりそうである。
ただここは1つ罠があって、(A-1)の下一桁が1、Aの最上位桁が2の場合、f(B)にはその分の"12"が含まれているのに、f(A-1)には含まれないため、1つ余分に"12"が含まれてしまう。
よって(A-1)の下一桁が1、Aの最上位桁が2の場合は、f(B)-f(A-1)-1が解となる。

後は定番通りf(v)を求めよう。
f(v)は以下の2パターンの和として求めよう。

• 21,22のように連続した2値の境目に"12"が来るケース
• 3124のように、1つの整数の中に"12"を含むケース

まず前者を求める。
v=xyyyyyyz (最上位桁がx、最下位桁がz、残りがyyyyy)とする。

• z≧2なら、条件を満たす整数は0～xyyyyyyのうち最上位桁が2のものの数。
• z＜2なら、条件を満たす整数は0～(xyyyyyy-1)のうち最上位桁が2のものの数。

そこでw = xyyyyyyまたは(xyyyyyy-1)として、0～wのうち最上位桁が2のものの数を求めよう。
2,2*,2**,2*** …の形の数が条件を満た。そのような数はそれぞれ1, 10, 100, 1000...個ずつある。
ただしxyyyyyyと同じ桁数の2******の形の数はxの数によって異なり、

• x==1ならそのような2******は存在しない
• x==2ならそのような2******は(yyyyyy+1)個存在する
• x＞2ならそのような2******は10000..(xyyyyyyと同じ桁数)個存在する。

後者は良くある桁DPで
dp[上から何桁目か][この桁は任意の値が取れるか、もしくはvの値以下か][直前桁が1かどうか] := "12"の含まれる数
として状態を取り処理していけば良い。

string decdec(string A) {
	for(int i=A.size()-1;i>=0;i--) {
		if(A[i]--!='0') break;
		A[i]='9';
	}
	return A.substr(A[0]=='0');
}

string A,B;
ll p10[20];
ll memo[20][2][2];

ll inc(int d,string &s, int lead,int one) {
	if(d>=s.size()) return 0;
	if(memo[d][lead][one]>=0) return memo[d][lead][one];
	ll ret=0;
	int i,ma=lead?(s[d]-'0'):10;
	
	FOR(i,ma) {
		if(i==2 && one) ret += p10[s.size()-1-d];
		ret += inc(d+1,s,0,i==1);
	}
	if(lead) {
		if(s[d]=='2' && one) ret += atoll(s.substr(d+1).c_str())+1;
		ret += inc(d+1,s,1,(s[d]=='1'));
	}
	
	return memo[d][lead][one]=ret;
}


ll con(string a) {
	if(a.size()<2) return a[0]>='2';
	
	int low=(a.back()-'0');
	a.pop_back();
	if(low<2) a=decdec(a);
	
	ll ret=1;
	int i;
	FOR(i,a.size()) {
		if(i || a[0]>'2') ret += p10[a.size()-1-i];
		else if(a[i]=='2') ret += atoll(a.substr(1).c_str())+1;
	}
	return ret;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	p10[0]=1;
	FOR(i,18) p10[i+1]=p10[i]*10;
	
	cin>>A>>B;
	int c=(A.back()=='2' && A[0]=='2');
	
	MINUS(memo);
	ll ret=con(B)+inc(0,B,1,0);
	MINUS(memo);
	A=decdec(A);
	ret -= con(A)+inc(0,A,1,0);
	
	cout<<(ret-c)<<endl;
	
}

まとめ

(A-1)とAが連結して"12"を作るケース、幸い自分はデバッグ中に気づいたけど、本番どの位はまった人いたんだろう。