yukicoder : No.294 SuperFizzBuzz

だいぶ遠回りしたけど終わってみれば想定解だった。
http://yukicoder.me/problems/743

問題

SuperFizzBuzz数とは、各桁3か5で構成され、かつ3の倍数で5の倍数である正の整数である。
小さい方からN番目のSuperFizzBuzz数を求めよ。

解法

サンプルがヒントになっている。
まずd桁ちょうどのSuperFizzBuzz数の個数f(d)を計算していくことで、N番目のSuperFizzBuzz数が何桁か求めよう。

d桁の整数がSuperFizzBuzz数であるには

• 1の位が5、その他の桁は3か5で
• 5の登場回数は3の倍数

を満たせばよいので、となる。

桁数が決まったら、1の位が5で、他の桁は3か5である整数を333...3335から555...5555まで順に総当たりして、N番目のSuperFizzBuzz数を求める。
各桁は3か5の2値なので、総当たりするのは最大でも2^d通りですむ。
サンプルから桁数dの上限は25なので十分間に合う。

const int CN=1001;
ll C[CN][CN];
int N;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,CN) for(j=0;j<=i;j++) C[i][j]=(j==0||j==i)?1:(C[i-1][j-1]+C[i-1][j]);
	
	cin>>N;
	int n5;
	
	for(int d=2;d<=30;d++) {
		ll p=0;
		FOR(n5,d) if(((n5+1)*2)%3==0) p+=C[d-1][n5];
		
		if(p>=N) {
			for(int mask=1;;mask+=2) if(__builtin_popcount(mask)*2%3==0) {
				if(--N==0) {
					FOR(x,d) s+='3'+((mask&(1<<x))!=0)*2;
					reverse(ALL(s));
					cout<<s<<endl;
					return;
				}
			}
		}
		else N-=p;
	}
}

まとめ

最初は桁DPとかDFSをやろうとしてだいぶタイムロスしました。