結果

問題 No.3483 A Forbidden Fruit
コンテスト
ユーザー 👑 loop0919
提出日時 2026-03-27 22:55:33
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
TLE  
実行時間 -
コード長 5,896 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 5,172 ms
コンパイル使用メモリ 376,028 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2026-03-27 22:56:17
合計ジャッジ時間 8,183 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other TLE * 1 -- * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

/**
 * author: loop0919
 */

#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;

/**
 * マクロやテンプレート用の自作ライブラリ
 */
namespace library {
    #pragma region types

    using ll = long long int;
    using i128 = __int128_t;
    using u128 = __uint128_t;
    using f128 = __float128;
    using mint = modint998244353;
    // using mint = modint1000000007;

    template<class T>
    using pq_max = priority_queue<T>;
    template<class T>
    using pq_min = priority_queue<T, vector<T>, greater<T>>;

    #pragma endregion

    #pragma region constants

    constexpr int INF32 = 1'000'000'000;
    constexpr ll INF64 = 2'000'000'000'000'000'000LL;

    constexpr int EMPTY = -1;
    constexpr int ALPHA = 26;

    #pragma endregion

    #pragma region macro

    #define __OVERLOAD_REP(_1, _2, _3, _4, _rep, ...) _rep
    #define __REP(n) for(int __i = 0; __i < (int)(n); __i++)
    #define __REP_1(i, n) for(int i = 0; i < (int)(n); i++)
    #define __REP_2(i, start, stop) for(int i = (int)(start); i < (int)(stop); i++)
    #define __REP_3(i, start, stop, step) for(int i = (int)(start); ((int)(step) >= 0) ? ((i) < (int)(stop)) : ((i) > (int)(stop)); (i) += (int)(step))

    #define rep(...) __OVERLOAD_REP(__VA_ARGS__, __REP_3, __REP_2, __REP_1, __REP)(__VA_ARGS__)
    #define rrep(i, n) rep(i, (int)(n) - 1, -1, -1)

    #define all(...) std::begin(__VA_ARGS__), std::end(__VA_ARGS__)
    #define rall(...) std::rbegin(__VA_ARGS__), std::rend(__VA_ARGS__)

    #pragma endregion

    #pragma region stdio
    void prepare_io() {
        ios_base::sync_with_stdio(false);
        cin.tie(0);
    }
    #pragma endregion

    #pragma region input
    void __input(int &v) {
        cin >> v;
    }

    void __input(ll &v) {
        cin >> v;
    }

    void __input(mint &v) {
        ll v_ll;
        __input(v_ll);
        v = mint(v_ll);
    }

    void __input(double &v) {
        cin >> v;
    }

    void __input(char &v) {
        cin >> v;
    }

    void __input(string &v) {
        cin >> v;
    }

    template<class T, class U>
    void __input(pair<T, U> &v) {
        __input(v.first);
        __input(v.second);
    }

    template<size_t N = 0, class T>
    void __input_tuple(T &t) {
        if constexpr (N < tuple_size<T>::value) {
            auto &x = std::get<N>(t);
            __input(x);
            __input_tuple<N + 1>(t);
        }
    }

    template<class... T>
    void __input(tuple<T...> &v) {
        __input_tuple(v);
    }

    template<size_t N, class T>
    void __input(array<T, N> &v) {
        for (T &d: v) __input(d);
    }

    template<class T>
    void __input(vector<T> &v) {
        for (T &d: v) __input(d);
    }

    void input() {}
    template <class H, class... T>
    void input(H &h, T &... t) {
        __input(h), input(t...);
    }
    #pragma endregion

    #pragma region output
    template<char sep = ' '>
    void __print(const char c) {
        cout << c;
    }

    template<char sep = ' '>
    void __print(const string s) {
        for (char c: s) __print<sep>(c);
    }

    template<char sep = ' '>
    void __print(const char *s) {
        int len = strlen(s);
        rep(i, len) __print<sep>(s[i]);
    }

    template<char sep = ' '>
    void __print(int v) {
        cout << v;
    }

    template<char sep = ' '>
    void __print(ll v) {
        cout << v;
    }

    template<char sep = ' '>
    void __print(double v) {
        cout << fixed << setprecision(12) << v;
    }

    template<char sep = ' ', class T, class U>
    void __print(const pair<T, U> v) {
        __print<sep>(v.first);
        __print(sep);
        __print<sep>(v.secomd);
    }

    template<char sep = ' ', size_t N = 0, class T>
    void __print_tuple(const T t) {
        if constexpr (N < std::tuple_size<T>::value) {
            if constexpr (N > 0) {
                __print(sep);
            }
            const auto x = std::get<N>(t);
            __print<sep>(x);
            __print_tuple<sep, N + 1>(t);
        }
    }

    template<char sep = ' ', class... T>
    void __print(const tuple<T...> v) {
        __print_tuple<sep>(v);
    }

    template<char sep = ' ', size_t N = 0, class T>
    void __print(const array<T, N> v) {
        int len = v.size();
        rep(i, len) {
            if (i > 0) __print(sep);
            __print<sep>(v[i]);
        }
    }

    template<char sep = ' ', class T>
    void __print(const vector<T> v) {
        int len = v.size();
        rep(i, len) {
            if (i > 0) __print(sep);
            __print<sep>(v[i]);
        }
    }

    template<char sep = ' ', char end = '\n'>
    void print(){
        __print(end);
    }
    template<char sep = ' ', char end = '\n', class H, class... T>
    void print(H &&head, T &&... tail) {
        __print<sep>(head);
        if (sizeof...(T) > 0) __print(sep);
        print<sep, end>(forward<T>(tail)...);
    }
    #pragma endregion
}
using namespace library;

constexpr double NONE = -1.0;

void solve() {
    ll N, M, K;
    cin >> N >> M >> K;

    ll remain = (N * M) - K;
    double P = remain < M - 1 ? remain / (M - 1): 1.0;

    vector<double> cache(N, NONE);

    auto dp = [&](this auto dp, ll n) {
        if (cache[n] != NONE) return cache[n];

        if ((N - n - 1) * M >= K) {
            cache[n] = 1.0;
            return cache[n];
        }

        if (n == 0) {
            cache[n] = P / M;
            return cache[n];
        }

        double p = (double)(M - 1) / (M * (n + 1)) * P;
        p += (double)n / (n + 1) * dp(n - 1);

        cache[n] = p;
        return p;
    };

    // rep(i, N) {
    //     cout << dp(i) << ' ';
    // }
    // cout << '\n';

    cout << dp(N - 1) << '\n';
}

int main(){
    cout << fixed << setprecision(12);
    prepare_io();
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}
0