TopCoder SRM 526 Div2 Hard SumOfLuckiness

これも定番問題かな。
http://community.topcoder.com/stat?c=problem_statement&pm=11626

問題

ある整数の幸せ度は、桁中の4の登場回数と7の登場回数の差分の絶対値である。
２つの整数A、Bが与えられたとき、整数A～Bの幸せ度の総和を求めよ。

解法

0～x-1までの幸せ度の総和をf(x)とすると、f(B+1)-f(A)が解答。
ではf(x)をどう求めるか。

まず、leading zeroも含め、i桁の数において4と7の登場回数の差がdとなるような数をDPで求める。
これは桁を増やすたびに4,7,それ以外を追加していけば簡単に求まる。

数xの最大桁の値がyとすると、最大桁を0～(y-1)にしたときの幸せ度の和は、前期DPの結果を用いて、それ以下の桁の幸せ度の総和を求めることができる。

また、最大桁yの時の幸せ度は、xの最大桁からyを引く、すなわち最大桁を除いた残りの数における幸せ度を再帰的に求めていけばよい。
ただ、y=4,7の時は以下の桁の幸せ度の和を求めるとき、4,7の数が増減することに注意する。

class SumOfLuckiness {
	public:
	ll dp[11][22];
	ll sum(ll S, int keta, int dif) {
		int i,j;
		ll t=1,ret=0;
		
		if(keta<0) return 0;
		FOR(i,keta) t*=10;
		FOR(i,10) {
			if(S<(i+1)*t) return ret + sum(S-(i*t),keta-1,dif+(i==4)-(i==7));
			FOR(j,22) ret += abs((j-10)+dif+(i==4)-(i==7))*dp[keta][j];
		}
		return ret;
	}
	
	
	long long theSum(int A, int B) {
		int i,j;
		ZERO(dp);
		dp[0][10]=1;
		FOR(i,10) for(j=1;j<=19;j++) {
			dp[i+1][j+1]+=dp[i][j];
			dp[i+1][j-1]+=dp[i][j];
			dp[i+1][j]  +=8*dp[i][j];
		}
		
		return sum(B+1,9,0)-sum(A,9,0);
	}
};

まとめ

桁単位の処理と桁をまたぐ処理(繰り上がりや大小比較)では桁単位DPor再帰。
bit演算とbitをまたぐ処理(加算や大小比較)ではbit単位DPor再帰。
これはかなり鉄板パターンだね。