yukicoder : No.1633 Sorting Integers (Multiple of 2^K)

色々考えるね。
https://yukicoder.me/problems/no/1633

問題

正整数nに対し、f(n)はnを2で割り切れる回数を意味する。

正整数の集合を考える。
この集合に含まれる整数は、1～9の各数字が含まれる回数が指定されたものに一致するもの全通りである。
この集合内の整数Mにおけるf(M)の最大値を求めよ。

解法

Editorialとは別の解法。
桁数がさほど大きくないので、DFSで枝刈り探索するとどうにか間に合う。

int N;
int C[10];
map<ll,int> memo[15];
ll p10[15];

int dfs(int d,ll v) {
	if(memo[d].count(v)) return memo[d][v];
	int ret=d;
	
	if(d==N) {
		ret=0;
		while(v%2==0) {
			ret++;
			v/=2;
		}
	}
	else {
		int i;
		int D[10]={};
		ll w=v;
		FOR(i,d) D[w%10]++, w/=10;
		FOR(i,10) if(D[i]<C[i]) {
			ll v2=v+p10[d]*i;
			if(v2%(1<<(d+1))) continue;
			ret=max(ret,dfs(d+1,v2));
		}
	}
	
	
	return memo[d][v]=ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	p10[0]=1;
	FOR(i,14) p10[i+1]=p10[i]*10;
	
	cin>>N;
	FOR(i,9) {
		cin>>C[i+1];
	}
	cout<<dfs(0,0)<<endl;
}

まとめ

もう1桁多いと間に合わなかったかも。