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;
}