Codeforces #273 Div2 E. Wavy numbers

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個以下なので何とか終わる。
以下のコードでは、下７桁がwavyかどうか先に判定テーブルを持つことで高速化している。

N<10^7の場合、まず0000000～9999999のうちのwavyな数を(leading zero含め)全部列挙しておき、Nとのmodごとに分類しておく。
この際、最初上から２ケタの大小関係に応じて12*****のように２ケタ目が大きいものと85******のように２ケタ目が小さいものを別に管理する。

次に、まず1～9999999の範囲のNの倍数のwavy判定を先に行っておき、この範囲にK個以上wavy数があるならそれを答える。
そして、先ほどの7桁のwavy数判定の結果を用いて、1*10^7～9999999*10^7まで10^7区切りでwavy数をカウントする。

• 下から8桁目と9桁目が56*******のように８ケタ目の方が大きいなら、下７桁分は6000000未満で57*****のように上から２ケタ目の方が大きいwavy数をカウントする。
• 下から8桁目と9桁目が64*******のように９ケタ目の方が大きいなら、下７桁分は5000000以上で53*****のように上から２ケタ目の方が小さい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でよかったんじゃないかな…。