yukicoder : No.456 Millions of Submits!

454に続きまたもゴリ押し。
http://yukicoder.me/problems/no/456

問題

以下のクエリを計10^6回答えよ。

0～10の範囲の整数A,B、および0.1～10の実数Tに対しとなる最大のnを求めよ。

解法

実は愚直に解けば意外と行けてしまう。
B＞0の場合f(1)が0になり以後単調増加、B=0の場合nが正で常に単調増加となるので、あとはその範囲で二分探索すればよい。
A,Bは整数なので、pow関数を使わずそれぞれA,B回nやlog(n)を掛け合えば間に合う。
また、式変形をすることで二分探索時にpowやlogの計算回数を減らすこともできる(Editorial参照)

二分探索ではなく解析解を求める方法もあるようだが、自分が理解していないので割愛。

ところで。
この問題は最初「最大」の条件がついていなかった。
そのため最初何も考えない二分探索解でWAを出した後、最小値を求める解法を書いてしまった。

Bが正の偶数の場合、log^B(n)の部分がnが1未満の時0に近いほど大きくなるため、単調増加とならない。
実際f(n)の微分を考えると、f'(n)=0となるのはlog(n)=-B/Aの時であり、nが0からexp(-B/A)までの範囲では単調増加である。
よって、Tがf(exp(-B/A))以下か超えるかによって二分探索を行う範囲が異なる。
こちらの問題の方がひっかけとしては面白いかなーと思った。

const int prime_max = 20000;
int NP,prime[100000],divp[prime_max];
map<int,int> M;

void cprime() {
	for(int i=2;i<20000;i++) if(divp[i]==0) {
		prime[NP++]=i;
		for(ll j=1LL*i*i;j>i&&j<prime_max;j+=i) divp[j]=i;
	}
}
int N;
int ma[20202];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cprime();
	MINUS(ma);
	ma[0]=0;
	FOR(i,NP) {
		x=prime[i];
		for(j=20000-x;j>=0;j--) if(ma[j]>=0) ma[j+x]=max(ma[j+x],ma[j]+1);
	}
	
	cin>>N;
	cout<<ma[N]<<endl;
	
	
}

まとめ

なんか今回のAdvent Calendar Contest 2016、数学的に自分が知らない話が多い。