TopCoderOpen 2021 Round4 : Medium SecondLargestMultiple

解法は思いついても、細かいところでミスしがち。
https://community.topcoder.com/stat?c=problem_statement&pm=17105&rd=18770

問題

正整数NとBが与えられる。
Nの倍数のうち、B進数表記で各桁の表記が異なるもののうち、大きい順で2番目のものはなにか。

解法

B桁のB進数の値は高々B^B通りなので、Bが小さい(8以下)の時は愚直に全探索してよい。
そうでないときは半分全列挙しよう。
以下では、下6桁を総当たりして、使われた数字のbitmask表記と、そのmod Nの値を状態とし、上記2位までを覚えておく。
その後、上(B-6)桁以下を同様に総当たりする。

class SecondLargestMultiple {
	public:
	unordered_map<ll,pair<ll,ll>> memo[1<<12];
	ll ret[3]={};
	ll N;
	int B;
	ll p6;
	void add(ll v) {
		ret[0]=v;
		sort(ret,ret+3);
	}

	void small(ll N,int B) {
		ll cand=1;
		int i;
		FOR(i,B) cand*=B;
		add(0);
		for(ll a=N;a<cand;a+=N) {
			int mask=0;
			ll b=a;
			while(b) {
				int x=b%B;
				if(mask&(1<<x)) break;
				mask|=1<<x;
				b/=B;
			}
			if(b==0) add(a);
		}
	}
	
	void dfs1(ll v,int mask) {
		ll mo=v%N;
		if(__builtin_popcount(mask)==6) {
			if(memo[mask].count(mo)==0) {
				memo[mask][mo]={-1,v};
			}
			else {
				ll a[3]={memo[mask][mo].first,memo[mask][mo].second,v};
				sort(a,a+3);
				memo[mask][mo]={a[1],a[2]};
			}
			return;
		}
		if(mo==0) {
			int num=__builtin_popcount(mask);
			ll w=v;
			while(w) num--, w/=B;
			if(num==0) add(v);
		}
		int i;
		FOR(i,B) if((mask&(1<<i))==0) dfs1(v*B+i,mask|(1<<i));
		
		
	}
	void dfs2(ll v,int mask) {
		if(mask==1) return;
		if(v) {
			ll mo=(N-v*p6%N)%N;
			int rm=((1<<B)-1)^mask;
			for(int sm=rm;sm>=0;sm--) {
				sm&=rm;
				if(__builtin_popcount(sm)==6&&memo[sm].count(mo)) {
					auto a=memo[sm][mo];
					if(a.first!=-1) add(a.first+v*p6);
					if(a.second!=-1) add(a.second+v*p6);
				}
			}
			
		}
		
		
		if(__builtin_popcount(mask)==B-6) return;
		int i;
		FOR(i,B) if((mask&(1<<i))==0) dfs2(v*B+i,mask|(1<<i));
	}
	

	void large(ll N,int B) {
		int i,mask;
		FOR(mask,1<<B) memo[mask].clear();
		this->N=N;
		this->B=B;
		p6=1;
		FOR(i,6) p6*=B;
		dfs1(0,0);
		dfs2(0,0);
	}
	
	long long find(long long N, int B) {
		
		ret[0]=ret[1]=ret[2]=-1;
		if(B<=7) {
			small(N,B);
		}
		else {
			large(N,B);
		}
		return ret[1];
		
		
	}
}

まとめ

本番は半分全列挙思いついたのに、mod Nで状態が爆発すると思って避けちゃったなぁ、もったいない。
まぁ細かいミスもあってどのみち一発ACにはならなかったけど。