Beta Round #64-C: Lucky Tickets

keyword

BIT　C++

問題概要

a*b = rev(a)*rev(b)となる(a,b)をluckyな組と呼ぶ。このとき、[1,X]*[1,Y]内にluckyな組がW(<10^7)個以上表れるようにしたい。X*Yが最小になるようなX,Yを求めよ。ただし、X,Yの上限はMaxX, MaxY(<10^5)。

解法

肝はa/rev(a)=rev(b)/b。あとはxの小さい順にBITに値を加算しながら、二分探索でx*y>=Wを満たす最小のyを探す。計算量は大体O(MaxX*(log(MaxY))^2)。けどxが大きくなったらyは小さくなるとか使えばlogを1個落とせそう。

感想

コンテスト中はxに関して全探索+yに関して二分探索だろうなあとか、BIT使うんだろうなあとかは大体予想がついたけど肝心のa/rev(a)=rev(b)/bに気づかなかった(その代わり小さい数で実験してた。各桁で繰り上がりがないときにうんぬんかんぬんとか)。この手の変形も何度も見てきたつもりなんだけどなかなか自分で発想するに至らない。

#include <cstdio>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long int64;

int MX, MY, W;
const int N = 100007;
int BIT[N];
map<pair<int,int>, vector<int> > dict;

int sum(int n){int _R=0;for(;n;n-=n&-n)_R+=BIT[n];return _R;}
void add(int n, int x){for(;n<=N;n+=n&-n)BIT[n]+=x;}

inline int rev(int x){
	int ret = 0;
	for(;x;x/=10) ret = ret*10 + x%10;
	return ret;
}

bool check(int y){
	return sum(y) >= W;
}

void init(){
	for(int i=1; i<=MY; i++){
		int j = rev(i), d = __gcd(i,j);
		dict[make_pair(i/d, j/d)].push_back(i);
	}
}

void solve(){
	int tx = -1, ty = -1;
	int64 best = 1LL<<60;
	init();
	for(int x=1; x<=MX; x++){
		int rx = rev(x), d = __gcd(x, rx);
		for(typeof(dict[make_pair(rx/d, x/d)].begin()) itr = dict[make_pair(rx/d, x/d)].begin(); itr != dict[make_pair(rx/d, x/d)].end(); itr++){
			int v = *itr;
			add(v, 1);
		}
		int low = 0, high = MY+5;
		while(high - low > 1){
			int mid = (high + low) / 2;
			if(check(mid)) high = mid;
			else low = mid;
		}
		if(high < MY+5 && (int64)high * x < best){
			best = (int64)high * x;
			tx = x;
			ty = high;
		}
	}
	if(tx > 0){
		printf("%d %d\n", tx, ty);
	}
	else{
		puts("-1");
	}
}

int main(){
	scanf("%d%d%d",&MX,&MY,&W);
	solve();
	return 0;
}