問題概要

りんごさんは1秒で1枚クッキーを焼ける
りんごさんはA秒かけて今あるクッキーT枚を全て食べることができ、それによって1秒でT枚クッキーを焼けるようになる
N枚以上のクッキーを最短何秒で焼けるか

部分点解法

N <= 10⁶なので、O(N)かO(N log N)ならOK。
以下のようなDPテーブルを考える。

dp[i]:=i枚のクッキーを丁度焼き終わる、最短の時間。

この際、dp[i]は最大でもiであることがわかる (クッキーを食べずに黙々と焼けばいいので) ため、DPテーブルをdp[i]=iで初期化する。
※公式の解説ではdp[0]=0, それ以外は∞とあったけどそれだと永遠にDPテーブルが更新されないので注意。
クッキーを焼くスピードをj枚/sにして (j枚の時にクッキーを食べて) i枚までクッキーを焼く時、i枚焼くにはdp[j]+A+i/j秒かかる。
従って、DPテーブルは以下のように更新できる。

dp[i] = min(dp[i],dp[j]+i/j)

これを0<=i<=2N (j刻み) , 1<=j<=Nの範囲で回してdp[N]~dp[2N]の最小値を出力すればいい。

オーダーについて自分があとで、見直すようにかなり雑に説明する。
j刻みで回すループ1回の中で、N/j回更新処理が行われている。
それを何度か回すということはN×Σ1/jになるんだけど、 ∫1/x = log x でΣ(1/j)は大体log(N)なのでオーダーはN log N。

満点解法

N <= 10¹²なのでO(N)でもNG。
log(10^12)≒40なので決め打ちして探索っぽい雰囲気がある。

では何を決め打ちするか。クッキーを何枚食べるか、では調べるのにO(N)かかるし、そもそも食べるのは1回ではないので決め打てない。
クッキーを何回食べるか、ではどうか。
どう考えても、スピードが速くなる場合以外にクッキーを食べることはないし、スピードが速くなる時に必ずクッキーを食べていけば、スピードは以下のように遷移する。

1枚→2枚→4枚→8枚......

つまりクッキーはlog(10^12)回以上食べることはない。クッキーを食べる回数を決め打ちすることにする。

決め打ちする値が決まった後に考えることは、クッキーを食べる枚数が決まっているときの最適な戦略である。
k回クッキーを食べる時、時間の流れは以下のようになる。

s0秒→A秒 (食べる) →s1秒→ A秒(食べる)→...→sk秒

そうすると、かかる時間はA*k+Σs, 焼きあがる枚数はΠsとなる。 Σsをできるだけ小さくしながらΠsをN以上にしたい。
これに関する最適な解はできるだけsを均等にすること、すなわち、sをNのk乗根にすることである。
僕は直感的に納得できたので証明をしてないけど、相加平均>=相乗平均とか使って証明できると思う。 (完全に適当)
k乗根は整数にならないので天井関数で調整する。この値をmとし、全てのsをmすると、Πsはk乗根がぴったり整数だった場合を除き、確実にNより大きくなる。
これをΠsがNを下回らない範囲で、m-1に置き換えていき調整する。

k乗根の導出にlog N
mとm-1の置き換えにlog N

出力は、各ステップ (食べる回数) で求めた答えの最小値となる。

ソースコード

部分点

#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for(ll i=0; i<(ll)(n); i++)
#define FOR(i,n,m) for (ll i=n; i<(ll)(m); i++)
#define pb push_back
#define INF 1000000007LL
#define all(a) (a).begin(),(a).end()

typedef long long ll;
typedef pair<int,int> p;

int dy[4]={-1,1,0,0};
int dx[4]={0,0,1,-1};

#define MAX_N 2000100

ll N , A;
ll dp[MAX_N];
int main(){
    ios::sync_with_stdio(false);
    cin >> N >> A;
    if (N>=1000000+1) return 0;
    REP(i,2*N) {
        dp[i]=i;
    }
    FOR(i,1,N) {
        for( ll j = i; j <= 2*N; j+=i) {
            dp[j] = min(dp[j], dp[i]+A+j/i);
        }
    }

    ll ans = INF * INF;

    FOR(i,N,2*N) ans = min(ans, dp[i]);

    cout << ans << endl;

    return 0;
}

満点

#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for(ll i=0; i<(ll)(n); i++)
#define FOR(i,n,m) for (ll i=n; i<(ll)(m); i++)
#define pb push_back
#define INF 1000000007LL
#define all(a) (a).begin(),(a).end()

typedef long long ll;
typedef pair<int,int> p;

int dy[4]={-1,1,0,0};
int dx[4]={0,0,1,-1};

ll N, A;

ll check (ll m, ll eat){

    ll cnt = 0;
    ll num = 1;
    REP(i,eat) {
        num*=m;
    }
    REP(i,eat) {
        // *mを*(m-1)に
        num/=m;
        num*=m-1;
        if (num>=N) {
            cnt+=1;
        } else {
            break;
        }
    }

    return cnt;
}

int main(){
    ios::sync_with_stdio(false);
    cin >> N >> A;

    ll ans = N;
    FOR(eat,1,50) {
        // double lt = 0; double bt=INF*INF;
        double m = pow(N,1/(double)(eat+1));
        ll mi = m;
        if (m>=mi) mi+=1;
        ll dec = check(mi, eat+1);
        //cout << A*eat+mi*(eat+1-dec)+(mi-1)*dec << endl;
        ans = min(ans, A*eat+mi*(eat+1-dec)+(mi-1)*dec);
    }

    cout << ans << endl;
    return 0;
}

tkw’s diary

CODE FESTIVAL 2016 Final E - Cookies

問題概要

部分点解法

満点解法

ソースコード