解法は思いついても、細かいところでミスしがち。
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にはならなかったけど。