https://cf16-final-open.contest.atcoder.jp/tasks/codefestival_2016_final_e
まずクッキーを食べる回数Tを固定します。これは40くらいまでやればいいです。
クッキーを食べるまでA+si秒待ったとすると、
クッキーの総和はΠ(1<=i<=T+1)si、かかった時間はΣ(1<=i<=T+1)si+ATと表されます。
Σsiを固定してΠsiを最大化するとき、siはなるべくまんべんなくするのが良いです。これはlogとって凸方程式とかでわかります。
なのでsiの要素がすべてaと等しいとして、Πsi=a^(T+1)<=Nを満たす最大のaを求めます。
それからsiの値を１つづつincrementして、初めてΠsiがN以上になった時が答えです。
siをT+1まで定義するのがポイントです。僕はここをTまでしか定義しなくて、
AT+Σsi+ceil(N/Πsi)を最小化しようという問題を考えて、だいたいグラフが凸になる(と思われる)から3分探索したんですが落ちました。
やっぱり実験で立てた予想にすがりすぎるとダメですね。
追記
グラフは確かに凸になるんですが、同じ値が生じすぎて谷にうまく落ちていきません。なので二分探索二回するとかで対応する必要がありますね。
まあ三分探索学べたので良しとしましょう。
ll pow(ll a, ll n) {
if(n == 0) return 1;
ll res = pow(a, n / 2);
if(n % 2 == 0) return res * res;
else return a * res * res;
}
ll root(ll a, ll n) {
if(n == 1) return a;
else if(n == 2) {
ll lv = -1, rv = 10000000;
while(rv - lv > 1) {
ll m = (lv + rv) / 2;
if(pow(m, n) <= a) lv = m;
else rv = m;
}
return lv;
}
else {
ll m = 1;
while(pow(m + 1, n) <= a) m++;
return m;
}
}
ll N, A;
void solve() {
cin >> N >> A;
ll ans = N;
rep(T, 1, 40 + 1) {
ll s = root(N, T + 1);
ll sum = s * (T + 1);
ll mul = pow(s, T + 1);
// debug(T, sum, mul);
rep(i, 0, T + 2) {
if(mul >= N) {
MIN(ans, A * T + sum);
break;
}
mul /= s;
mul *= (s + 1);
sum++;
}
}
cout << ans << "\n";
}
