Dとは打って変わって難易度の上がった問題。
http://codeforces.com/contest/478/problem/E
問題
整数がwavyであるとは、各桁は両隣の数値の両方より小さいか両隣より大きくなっており、桁毎の大小関係が波打つ整数であるものである。
数NとKが与えられるので、Nの倍数のうちK番目を答えよ。
ただし答えがM=10^14より大きいなら-1を答えよ。
解法
まずNの大小で分ける。
N>=10^7なら、Nの倍数を全部列挙すればよい。
M以下のNの倍数は10^7個以下なので何とか終わる。
以下のコードでは、下7桁がwavyかどうか先に判定テーブルを持つことで高速化している。
N<10^7の場合、まず0000000~9999999のうちのwavyな数を(leading zero含め)全部列挙しておき、Nとのmodごとに分類しておく。
この際、最初上から2ケタの大小関係に応じて12*****のように2ケタ目が大きいものと85******のように2ケタ目が小さいものを別に管理する。
次に、まず1~9999999の範囲のNの倍数のwavy判定を先に行っておき、この範囲にK個以上wavy数があるならそれを答える。
そして、先ほどの7桁のwavy数判定の結果を用いて、1*10^7~9999999*10^7まで10^7区切りでwavy数をカウントする。
- 下から8桁目と9桁目が56*******のように8ケタ目の方が大きいなら、下7桁分は6000000未満で57*****のように上から2ケタ目の方が大きいwavy数をカウントする。
- 下から8桁目と9桁目が64*******のように9ケタ目の方が大きいなら、下7桁分は5000000以上で53*****のように上から2ケタ目の方が小さいwavy数をカウントする。
上記*******未満/以上はlower_boundを使って検索すれば何とか間に合う。
ll N,K; int memo[10000001],memo2[10001]; map<int,vector<int> > M[2]; int wavy(ll v) { int num[15],d,i; while(v>=10000000) { if(memo[v%10000000]==0) return 0; v/=100000; } while(v>=10000) { if(memo2[v%10000]==0) return 0; v/=100; } if(v<10) return 1; if(v<100) return (v%10!=v/10); FOR(d,15) { if(v==0) break; num[d]=v%10; v/=10; } for(i=1;i<d-1;i++) { if(num[i-1]==num[i]||num[i+1]==num[i]) return 0; if(num[i-1]<num[i] != num[i+1]<num[i]) return 0; } return 1; } void dfs(int cur,int left) { int i; if(left==0) { memo[cur]=1+((cur%10)<(cur/10%10)); if(N<10000000) M[memo[cur]-1][cur%N].push_back(cur); return; } if(cur/10%10 < cur%10) { FOR(i,cur%10) dfs(cur*10+i,left-1); } else { for(i=cur%10+1;i<10;i++) dfs(cur*10+i,left-1); } } void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>K; FOR(i,100) if(i%10 != i/10) dfs(i,5); FOR(i,10000) memo2[i]|=i/100%10<i/10%10 && i%10<i/10%10 && i/1000>i/100%10; FOR(i,10000) memo2[i]|=i/100%10>i/10%10 && i%10>i/10%10 && i/1000<i/100%10; if(N>=10000000) { for(ll v=N;v<=10000000LL*10000000; v+=N) if(wavy(v) && --K==0) return _P("%lld\n",v); return _P("-1\n"); } for(i=N;i<10000000;i+=N) if(wavy(i) && --K==0) return _P("%d\n",i); for(ll v=1;v<=9999999; v++) { int mo=(N-(v*10000000%N)) % N; if(wavy(v)==0) continue; if((v<10 || (v%10>v/10%10)) && M[1].count(mo)) { x = lower_bound(M[1][mo].begin(),M[1][mo].end(),(int)(v%10)*1000000)-M[1][mo].begin(); if(K<=x) return _P("%lld\n",v*10000000+M[1][mo][K-1]); K-=x; } if((v<10 || (v%10<v/10%10)) && M[0].count(mo)) { x = lower_bound(M[0][mo].begin(),M[0][mo].end(),(int)(1+(v%10))*1000000)-M[0][mo].begin(); K-=M[0][mo].size()-x; if(K<=0) return _P("%lld\n",v*10000000+M[0][mo][M[0][mo].size()-1+K]); } } return _P("-1\n"); }
まとめ
地味にメモリ消費が大きく、TLE制限も結構きつい問題。
上限は10^14じゃなく10^12でよかったんじゃないかな…。