AtCoder ARC #052 : D - 9

こちらも反省。
http://arc052.contest.atcoder.jp/tasks/arc052_d

問題

整数K,Mが与えられる。
1～Mの整数Nのうち、N%Kと(Nの10進数表記の各桁の和)%Kが一致するものの数を求めよ。

解法

各桁の和の方は最大でも90にしかならないことを利用しよう。

Kが大きいとき、たとえば10^5以上なら1≦N=i*K+x≦M (0≦x≦90)を総当たりすればよい。
Kが小さい場合、上の桁から順に両方の種類のmodを取りつつ桁DPする。

なお、愚直に２種類のmodの値を覚えようとするとMLEする(した)。
無理やりどうにかメモリ配置を工夫して押し込むことも一応できる。
ただ、今回最終的に２種類のmodが一致すればいいので、両者の差だけを管理しておけば1種類の値だけ覚えるので済み、MLEを回避できる。

ll K,M;
ll p10[18];
ll dp[12][2][100000];
int sum[100000];

ll dfs(int d,int lead,int m) {
	if(d==-1) return m==0;
	ll& ret=dp[d][lead][m];
	if(ret!=-1) return ret;
	ret=0;
	int i;
	int dd=M/p10[d]%10;
	if(lead) {
		FOR(i,dd) ret += dfs(d-1,0,(m+p10[d]*i-i)%K);
		ret += dfs(d-1,1,(m+p10[d]*i-i)%K);
	}
	else {
		FOR(i,10) ret += dfs(d-1,0,(m+p10[d]*i-i)%K);
	}
	return ret;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>K>>M;
	
	p10[0]=1;
	FOR(i,17) p10[i+1]=p10[i]*10;
	FOR(i,100000) {
		x=i;
		while(x) sum[i] += x%10, x/=10;
	}
	
	ll ret=0;
	if(K>=100000) {
		for(i=0;i*K<=M;i++) {
			ll a=i*K;
			ll m=a%K;
			
			FOR(x,99) {
				a++;
				m++;
				if(m>=K) m-=K;
				if(a>M) break;
				if(a==0) continue;
				if(m == sum[a/100000]+sum[a%100000]) ret++;
			}
		}
	}
	else {
		MINUS(dp);
		ret=dfs(10,1,0)-1;
	}
	
	
	cout<<ret<<endl;
}

まとめ

ミスしたときに連続でミスするのひどい。