結果

問題 No.3318 客に卵をかける
コンテスト
ユーザー のらら
提出日時 2025-10-19 13:13:01
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,521 bytes
コンパイル時間 3,386 ms
コンパイル使用メモリ 190,288 KB
実行使用メモリ 11,296 KB
最終ジャッジ日時 2025-10-26 11:40:25
合計ジャッジ時間 6,776 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other TLE * 1 -- * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

//long doubleは遅いのか？
#include <algorithm>
#include <atcoder/all>
#include <iomanip>
#include <iostream>
using namespace std;
using namespace atcoder;
using ll = long long;
// #define endl "\n";
ll T, N, X, Y, P, Q, R;

// 行列積
using classMat = double;
vector<vector<classMat>> mat_mul(vector<vector<classMat>> a, vector<vector<classMat>> b) {
    int n = a.size();
    vector<vector<classMat>> res(n, vector<classMat>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                res[i][j] += a[i][k] * b[k][j];
            }
        }
    }
    return res;
}
// 行列累乗
vector<vector<classMat>> mat_pow(vector<vector<classMat>> a, ll b) {
    int n = a.size();
    vector<vector<classMat>> res(n, vector<classMat>(n));
    for (int i = 0; i < n; i++) res[i][i] = 1.0;
    while (b) {
        if (b & 1) res = mat_mul(res, a);
        a = mat_mul(a, a);
        b = (b >> 1);
    }
    return res;
}

int main() {
    cin >> T;
    while (T--) {
        cin >> N;
        cin >> X >> Y;
        cin >> P >> Q >> R;
        auto ff = [&](ll y) -> classMat {
            ll takoyaki = X + Y * y;
            ll l = 1, r = N - y;
            vector<vector<classMat>> a = {{1.0 - 1.0 / takoyaki, 1.0}, {0.0, 1.0}};
            vector<vector<classMat>> b = {{(classMat)0, 0}, {(classMat)Q, 0}};
            auto f = [&](ll x) -> classMat {
                vector<vector<classMat>> c = mat_pow(a, x);
                vector<vector<classMat>> chk = mat_mul(c, b);
                return (classMat)P * y + ((classMat)Q - (classMat)R / takoyaki) * (N - y - x) + chk[0][0];
            };
            while (r - l > 2) {
                ll m1 = (l * 2 + r) / 3;
                ll m2 = (l + r * 2) / 3;
                if (f(m1) < f(m2))
                    l = m1;
                else
                    r = m2;
            }
            classMat ret = 0.0;
            for (ll j = l; j <= r; j++) {
                ret = max(ret, f(j));
            }
            return ret;
        };
        ll l2 = 0, r2 = N - 1;
        while (r2 - l2 > 2) {
            ll mm1 = (l2 * 2 + r2) / 3;
            ll mm2 = (l2 + r2 * 2) / 3;
            if (ff(mm1) < ff(mm2))
                l2 = mm1;
            else
                r2 = mm2;
        }
        classMat ans = 0.0;
        for (ll i = l2; i <= r2; i++) {
            ans = max(ans, ff(i));
        }
        cout << fixed << setprecision(15) << ans << endl;
    }
    return 0;
}
0