yukicoder No.456 Millions of Submits!

yukicoder

問題URL : http://yukicoder.me/problems/no/456

{ \displaystyle }

問題概要

整数a,bと実数tがm回与えられる．
各a,b,tについて以下の式を満たす最大のnを計算せよ．
{ \displaystyle n^a\log ^b n = t }

解法

mが最大10^6と大きいため，単純に二分探索を行うとTLEしてしまう．
そこでaとbで場合分けを行う．

(1) a = 0 or b = 0 のとき

計算式は
{ \displaystyle n = \mathrm{e}^{t^{\frac{1}{b}}} } or { \displaystyle n = t^{\frac{1}{a}} }
と式変形できるため簡単に計算できる．

(2) それ以外(a > 0 and b > 0) のとき

nの取りうる値の範囲について考えてみると，
a=1, b=1, t=10 のとき n = 5.72 ... で最大となり，
a=10, b=10, t=0.1 のとき n = 1.62 ... で最小となる．
よって探索範囲は1 < n < 6 とすれば十分だと分かる．
許容誤差は10^-9なので log 5/10^-9 = 32.219 ... < 33 回以上探索を繰り返せば精度は足りる．
あとは，powの計算を繰り返し二乗法で計算することでTLEせずに計算することができる．
(std::powを使うとTLE)
(for文でpowを計算しても間に合うらしい...)

コード

double mypow(double x, int y) {
	double a = 1;
	while(y) {
		if(y & 1) a = a * x;
		x = x * x;
		y >>= 1;
	}
	return a;
}

inline double f(int a, int b, double x) {
	return mypow(x, a) * mypow(log(x), b);
}

void mainmain() {
	int m;
	scanf("%d", &m);
	rep(i, m) {
		int a, b;
		double t;
		scanf("%d%d%lf", &a, &b, &t);
		if(a == 0) {
			double ans = exp(pow(t, 1. / b));
			printf("%.10lf\n", ans);
			continue;
		}
		else if(b == 0) {
			double ans = pow(t, 1. / a);
			printf("%.10lf\n", ans);
			continue;
		}
		double l = 1;
		double r = 6;
		rep(j, 35) {
			double mid = (l + r) / 2;
			double val = f(a, b, mid);
			if(t <= val) r = mid;
			else l = mid;
		}
		printf("%.10lf\n", l);
	}
}

コメント

ごり押しでごめんなさい