CODE FESTIVAL 2016 Final E - Cookies
問題
E: Cookies - CODE FESTIVAL 2016 Final (Parallel) | AtCoder
問題概要
はじめ、1秒に1枚のクッキーを焼くことが出来る。そして、クッキーを全て食べつくすという行動を取ることが出来る。枚数に関わらず、これには秒かかる(食べている間はクッキーを焼くことは出来ない)。しかし、直前にクッキーが枚溜まっていたら、食べた後は1秒に枚のクッキーを焼くことができるようになる。
枚のクッキーを用意したいと思う時、それに必要な時間の最小値を求めよ。
- は整数
アイデア
まず、クッキーを食べる間隔についてだが、クッキーを食べてから次にクッキーを食べるまでに最低でも2秒はクッキーを焼かないと最適にはなりえない。なぜなら、今の生産効率がだとして、1秒だけクッキーを焼いて食べてもその後の生産効率はのままであり、食べる時間だけ無駄になるからである。
そうすると、最短でクッキーを食べ続ける行動をとっても生産効率は2倍ずつ上がっていく。なので、生産効率がに到達するまでにクッキーを食べる回数は回ということになり、これ以上の回数クッキーを食べることに意味はない。
クッキーを食べる回数を回に決め打ちして、そのときに枚作るための時間の最小値を求めていく。回食べるときに、そのクッキーを焼く間隔を秒とすると、かかる時間はで、焼くことのできるクッキーの枚数は枚である。
焼けるクッキーの枚数についてなぜこうなるのかというと、順番にシミュレーションしていけばこうなることが分かる。はじめは枚/s焼けて、秒後に食べるので枚/s焼けるようになる。次は枚/s焼けて、秒後に食べるので枚/s焼けるようになる。... これを繰り返していくと、最終的な状態は上で述べたようになっている。
クッキーの枚数の条件を満たしつつ、かかる時間を最小化したい。初項は一定なので、実質を最小化したい問題になった。
この時、積をできるだけ大きくするにはそれぞれの項の差が1以下になるようにするのが最適になっている。としたときに、であるから、これが正しいことが分かった。
の最大値を二分探索し、それをとすると、のような形になるので、の項の個数を全探索して、最小値を更新していけば良い。オーバーフローには気をつける(以上になった瞬間に打ち切ってしまえば良い)。
実装(C++)
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr) #define all(x) (x).begin(),(x).end() #define pb push_back #define fi first #define se second int main() { ll n,a; cin >>n >>a; ll ans=n; for(int k=1; k<=40; ++k) { ll l=0, r=1000000; while(r-l>1) { ll m=(l+r)/2; bool ok=false; ll val=1; rep(i,k+1) { val*=m; if(val>=n) { ok=true; break; } } if(ok) r=m; else l=m; } rep(i,k+1) { ll val=1; bool ok=false; rep(j,i) { val*=r-1; if(val>=n) { ok=true; break; } } if(!ok) { rep(j,k+1-i) { val*=r; if(val>=n) { ok=true; break; } } } if(ok) { ll tmp = a*k + i*(r-1) + (k+1-i)*r; ans=min(ans,tmp); } } } cout << ans << endl; return 0; }