yukicoder : No.220 世界のなんとか2

とりあえずこちらから。
http://yukicoder.me/problems/577

問題

整数Pが与えられる。
1から10^Pの整数のうち、3の倍数またはどこかの桁に3を含む数がいくつあるか答えよ。

解法

10^Pは条件を満たさない。
残り1～(10^P-1)のうち、条件を満たすものを数え上げよう。

以下解法は2つある。自分は本番前者で解いたが、後者の解を見て力が抜けてしまった。

桁DP解

下D桁の値が未確定で、上の桁の和(の３の剰余)がRの場合、全体が条件を満たすような下D桁の組みわせの数を桁DPで求めよう。

未確定の下D桁のうち、最上位桁iを0～9で総当たりしていく。
最上位桁iが3の場合、残り(D-1)桁はなんでもよいので10^(D-1)を解に計上する。
それ以外の場合、残り(D-1)桁について、上の桁の和が(R+i)%3になると考えて再帰的に処理していけばよい。

なお、この解法の値は0も含むので最後に1引くのを忘れないように。

計算解

条件を満たさないものを取り除くことを考える。
条件を満たさないものは、各桁がどれも3ではなく、かつ全体が3の倍数ではないものである。

各桁がどれも3でないものは9^P通り。
そのうち、3の倍数でないものは2/3あると考えられる。
よって解は。

int N;
ll p10[19];
map<int,ll> M[3];

ll hoge(int v,int mo) {
	if(v==0) return mo==0;
	if(M[mo].count(v)) return M[mo][v];
	
	ll ret=0;
	for(int i=0;i<=9;i++) {
		if(i==3) ret += p10[v-1];
		else ret += hoge(v-1,(i+mo)%3);
	}
	
	return M[mo][v]=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>>N;
	cout<<hoge(N,0)-1<<endl;
}

まとめ

直感で計算解で行けそうと思っても、直感を信じきれないんだよなぁ。