kmjp's blog

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

EEIC Programming Contest #0 : E. C0unt

これ系の桁DPは苦手。
https://www.hackerrank.com/contests/eeic-programming-contest-0/challenges/count-zero-1-1

問題

F(n) := nの10進数表記で、leading zero以外に0が現れる桁数
とする。整数N,Pが与えられる。Pの倍数でN以下の正整数vについて、F(v)の総和を求めよ。

解法

N/Pが10^7以下ぐらいなら、vを総当たりすればよい。
N/Pがそれよりも多い場合、桁DPを考えよう。

vの各桁について、

  • leading zero以外の0
  • leading zeroまたは正の数

のどちらが来るかをbitdpで2^10程度総当たりし、桁DPでそのようなN以下のPの倍数を求めよう。

N/Pが10^7以上ということはPは100以下なので、Pで割った余りの情報もDPの状態で持ち越すようにする。

ll N,P;
int mask;
ll p10[11];

ll dp[11][2][2][100];


ll hoge(int d,int le,int po,int m) {
	if(d==-1) {
		return m==0 && po;
	}
	if(dp[d][le][po][m]>=0) return dp[d][le][po][m];
	ll pat=0;
	int x=N/p10[d]%10;
	if(mask&(1<<d)) {
		if(po) pat=hoge(d-1,le | (x>0),po,m*10%P);
	}
	else {
		int i;
		for(i=1;i<=9;i++) {
			if(le==0 && i>x) continue;
			pat+=hoge(d-1,le | (i<x),1,(m*10+i)%P);
		}
		if(po==0) {
			pat+=hoge(d-1,le | (0<x),po,(m*10+0)%P);
		}
	}
	
	return dp[d][le][po][m]=pat;
}

int hoge(ll v) {
	int ret=0;
	while(v) {
		ret+=v%10==0;
		v/=10;
	}
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>P;
	
	p10[0]=1;
	FOR(i,10) p10[i+1]=p10[i]*10;
	ll ret=0;
	if(N/P<=100000000LL) {
		for(ll a=P;a<=N;a+=P) ret+=hoge(a);
	}
	else {
		for(mask=1;mask<1<<10;mask++) {
			MINUS(dp);
			ret+=__builtin_popcount(mask)*hoge(10,0,0,0);
		}
	}
	cout<<ret<<endl;
	
}

まとめ

手間ではあるけどCよりは気楽かな…。