公式解説

imoscon_m 解説

小課題1

冷蔵庫のレベルを $P$ より大きくした時は，物体を必ず $1$ 時間で冷やしきることができるので，レベルを $P$ より大きくする必要はありません．
したがって，冷蔵庫のレベルを $1$ にしたとき，$2$ にしたとき，…，$P$ にしたときについてそれぞれ考え，それらの時の答えの最小値を出力することでこの問題を $O(P)$ で解くことができます．

小課題2

三分探索を行うことでこの問題を $O(logP)$ で解くこともできますが，ここでは異なる解法を示します．
まず，冷蔵庫のレベルを $X$ にしたときの所要時間は $XT+\cfrac{P}{X}$ 時間です．
したがって，相加相乗平均を用いることにより，これの最小値は $2\sqrt{TP}$ で，この時の $X$ は $\sqrt{\cfrac{P}{T}}$ です．
ただし，$X$ は必ず整数なので，$\sqrt{\cfrac{P}{T}}$ をはさむ2つの整数それぞれについて，これが $X$ だったときを考える事でこの問題を $O(1)$ で解くことができます．

回答例(C++)

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

int main() {
	long long t, p;
	cin >> t >> p;
	long long about_ans = sqrt(p / t);
	long long ans = about_ans;
	long long score = (1LL << 60) * 3;
	for (long long i = about_ans - 5; i <= about_ans + 5; i++) {
		if (i <= 0) continue;
		if (score > (i * t) + (p / i) + (p % i == 0 ? 0 : 1)) {
			ans = i;
			score = (i * t) + (p / i) + (p % i == 0 ? 0 : 1);
		}
	}
	cout << score << endl;
	return 0;
}
Copy

回答例(Python)

import math
import bisect
import collections
import heapq

def isqrt(n):
    if (n == 0):
        return 0
    rinzi = int(math.sqrt(n))-1
    return (rinzi + 1  if rinzi * (rinzi + 2) < n else rinzi)

def main():
    t,p = map(int,input().split())
    about_ans = isqrt(p // t)
    ans = about_ans
    score = (1 << 60) * 3
    for i in range(about_ans - 5, (about_ans+5) + 1):
        if i <= 0:
            continue
        if score > (i*t) + (p//i) + (0 if p % i == 0 else 1):
            ans = i
            score = (i*t) + (p//i) + (0 if p % i == 0 else 1)
    print(score)
    return

main()
Copy