Yukicoder No.67 よくある棒を切る問題 (1)

練習会で解いた。

No.67 よくある棒を切る問題 (1)

解法

二分探索する。$O(N \log K)$。

実装

入力$K \le 10^{10}$でありintだと一発でoverflowすることに注意。やらかした。

初めは終了条件をr - l > epsとしていたが、一般にこれはよろしくないことを指摘してもらった。 例えば今回であれば

絶対誤差、または、相対誤差が$10^{−9}$以下であれば正答とみなされる。

と指示されているが、r - l > epsで判定しているのは絶対誤差だけである。 よって答えとなる値が大きい場合、過剰な回数の計算をしてしまいTLEしうる。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
typedef long long ll;
using namespace std;
const long double eps = 1e-10;
int main() {
    int n; cin >> n;
    vector<int> ls(n); repeat (i,n) cin >> ls[i];
    ll k; cin >> k;
    long double l = 0, r = *max_element(ls.begin(), ls.end());
    repeat (iteration,100) {
        long double m = (l + r) / 2;
        ll cnt = 0;
        repeat (i,n) cnt += floorl(ls[i] / m);
        (k <= cnt ? l : r) = m;
    }
    printf("%.14Lf\n", l);
    return 0;
}