TopCoder SRM 842 : Div1 Medium SmoothMultiples

実装は面倒だけど、難しくはないかな…。
https://community.topcoder.com/stat?c=problem_statement&pm=17923

問題

正整数がK-smoothであるとは、10進数表記で隣接する数字の差がK以下であることを意味する。
正整数K,A,B,Cが与えられる。
A以上B以下のCの倍数のうち、K-smoothであるものは何通りか。

解法

Cが大きいときは、A以上B以下の倍数を総当たりすればよい。
Cが小さいときは桁DPで解く。B以下のK-smooth値の個数から、(A-1)以下のK-smooth値の個数を引こう。

以下では、X以下のCの倍数のK-smooth値の個数を数えることを考える。

自分は以下をdの大きい順に決めて行った。

• f(d, z, l, p, m) := 以下の状態の組み合わせ
  • 上からd桁目までの値を定めたとき、
  • z: 0じゃない桁があるかないかの真偽値
  • l: X未満となることが確定しているかどうかの真偽値
  • p: d桁目の数字
  • m: d桁目以上をCで割った余り

(d-1)桁目を0～9総当たりし、最終的に1の位まで定めたときにm=0となるケースの和を取ればよい。

ll dp[13][2][2][10][10000];
ll p10[15];

class SmoothMultiples {
	public:
	int smooth(ll v,int k) {
		int pre=-1;
		while(v) {
			int cur=v%10;
			v/=10;
			if(pre!=-1&&abs(pre-cur)>k) return 0;
			pre=cur;
		}
		return 1;
		
	}
	
	ll hoge(int K,ll B,ll C) {
		ZERO(dp);
		dp[12][1][1][0][0]=1;
		int d,z,l,p,m,n;
		for(d=11;d>=0;d--) FOR(z,2) FOR(l,2) FOR(p,10) FOR(m,C) {
			ll v=dp[d+1][z][l][p][m];
			if(v==0) continue;
			FOR(n,10) {
				if(z==0&&abs(n-p)>K) continue;
				if(l==1&&n>B/p10[d]%10) continue;
				int nz=(z==1&&n==0);
				ll nl=l&&(n==B/p10[d]%10);
				int nm=(m*10+n)%C;
				dp[d][nz][nl][n][nm]+=v;
			}
		}
		ll ret=0;
		FOR(l,2) FOR(p,10) ret+=dp[0][0][l][p][0];
		return ret;
	}
	
	long long count(int K, long long A, long long B, long long C) {
		if(C>10000) {
			ll ret=0;
			for(ll a=0;a<=B;a+=C) if(a>=A) {
				if(smooth(a,K)) ret++;
			}
			return ret;
		}
		p10[0]=1;
		int i;
		FOR(i,14) p10[i+1]=p10[i]*10;
		
		ll ret=hoge(K,B,C);
		if(A>1) ret-=hoge(K,A-1,C);
		return ret;
	}
}

まとめ

こういう桁DPだいぶ飽きてきた…。