Yukicoder No.68 よくある棒を切る問題 (2)

No.68 よくある棒を切る問題 (2)

解法

$O(K \log N + Q)$。editorialが詳しい。

感想

$O(K \log N + Q)$だろうなあとは思っていて、最適に$k$個に分割してその長さが$l$ならある棒$i$があって$l \mid L_i$というのも気付いていた。

しかしa[i]からa[i+1]を直接求める、あるいはその逆、といった方向を考えていた。 2日前にも似たような失敗をしている。 実数や有理数に対する直接的なdpの方針は疑った方がよさそう。

実装

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstdio>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
typedef long long ll;
using namespace std;
struct rational_t { int p, q; };
bool operator < (rational_t a, rational_t b) { return a.p *(ll) b.q < b.p *(ll) a.q; }
int main() {
    int n; cin >> n;
    vector<int> ls(n); repeat (i,n) cin >> ls[i];
    int q; cin >> q;
    vector<int> k(q); repeat (i,q) cin >> k[i];
    int max_k = *max_element(k.begin(), k.end());
    vector<double> a(max_k+1);
    priority_queue<rational_t> que;
    for (int l : ls) que.push((rational_t) { l, 1 });
    repeat (i,max_k) {
        rational_t r = que.top(); que.pop();
        a[i+1] = r.p /(double) r.q;
        ++ r.q;
        que.push(r);
    }
    repeat (i,q) printf("%.14lf\n", a[k[i]]);
    return 0;
}