AtCoder ABC #154 : E - Almost Everywhere Zero

ゴリ押しが通じちゃうんだよなぁ。
https://atcoder.jp/contests/abc154/tasks/abc154_e

問題

D桁の正整数Nと、正整数Kが与えられる。
N以下の正整数で、0ではない桁がちょうどK個あるものは何通りか。

解法

順当に解くなら、桁DPで上の桁から順にN未満が確定しているかどうかと、0ではない桁の数を更新していく。
ただ、この問題はKが高々3なので、3重ループで非0桁を総当たりし、しかも実際に整数を構築しても間に合う。

string N;
int K;

void solve() {
	int i,j,k,l,r,x,y,z; string s;
	
	cin>>N>>K;
	while(N.size()<100) N="0"+N;
	string S(100,'0');
	
	ll ret=0;
	FOR(x,100) {
		for(S[x]='1';S[x]<='9';S[x]++) {
			if(K==1 && S<=N) ret++;
			FOR(y,x) {
				for(S[y]='1';S[y]<='9';S[y]++) {
					if(K==2 && S<=N) ret++;
					FOR(z,y) {
						for(S[z]='1';S[z]<='9';S[z]++) {
							if(K==3 && S<=N) ret++;
						}
						S[z]='0';
					}
				}
				S[y]='0';
			}
		}
		S[x]='0';
	}
	cout<<ret<<endl;
}

まとめ

このゴリ押しは想定内なのかなぁ…？