結果
| 問題 | No.3483 A Forbidden Fruit |
| コンテスト | |
| ユーザー |
 graph11463
|
| 提出日時 | 2026-03-27 21:59:03 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 8,851 bytes |
| 記録 | |
| コンパイル時間 | 5,355 ms |
| コンパイル使用メモリ | 395,240 KB |
| 実行使用メモリ | 631,808 KB |
| 最終ジャッジ日時 | 2026-03-27 21:59:36 |
| 合計ジャッジ時間 | 9,816 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge2_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | MLE * 1 -- * 15 |
ソースコード
#include <bits/stdc++.h>
#include <atcoder/all>
#include <ranges>
using namespace std;
using namespace atcoder;
//loop
#define REP(i, n) for (ll i = 0; i < (ll)(n); i++)
//vector
#define ALL(A) A.begin(), A.end()
#define RV(A) reverse(ALL(A))
#define RALL(A) A.rbegin(), A.rend()
#define SORT(A) sort(ALL(A))
#define RSORT(A) sort(RALL(A))
//input
template<class T> inline void input(T& a) { cin >> a; }
template<class T> inline void input_li(T& a) {for(auto &ob:a) cin >> ob;}
template<class... T> inline void input(T&... a) { ((cin >> a), ...); }
//output
#define Yes(bo) cout << ((bo) ? "Yes":"No") << endl
#define YES(bo) cout << ((bo) ? "YES":"NO") << endl
#define yes(bo) cout << ((bo) ? "yes":"no") << endl
#define Taka(bo) cout << ((bo) ? "Takahashi":"Aoki") << endl
//other
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define sz size
#define is insert
#define ps push
#define tp top
#define ft front
#define pp pop
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0;}
//const
#define I_MAX 2147483647
#define I_MIN -2147483647
#define UI_MAX 4294967295
#define LL_MAX 9223372036854775807
#define LL_MIN -9223372036854775808
#define ULL_MAX 18446744073709551615
//type
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using Pair = pair<ll,ll>;
using vll = vector<ll>;
using mint = modint998244353;
using mint1 = modint1000000007;
const ll Inf = 1LL << 60;
//debug
#ifdef _DEBUG
#define debug(x) cerr << "dbg_var : " << #x << ": " << x << endl
#define debug2(x,y) cerr << "dbg_var : " << #x << ": " << x << " "<< #y << ": " << y << endl
#define debug3(x,y,z) cerr << "dbg_var : " << #x << ": " << x << " "<< #y << ": " << y << " " << #z << ": " << z <<endl
#define debug_v(x) cerr << "dbg_vect: " << #x << ": "; for(auto v:x) cerr << v << " "; cerr << endl
#define debug_s(x) cerr << "dbg_set : " << #x << ": {"; for(auto v:x) cerr << v << ","; cerr << "}" << endl
#define debug_p(x) cerr << "dbg_pair: " << #x << "Fir: " << x.first << " Sec: " << x.second << endl
#define debug_m(x) cerr << "dbg_map : " << #x << ": "; for(auto Ite1:x)cerr << "key: " << Ite1.first << " : " << Ite1.second << ", "; cerr<< endl
#define debug_l() cerr << "======================================" << endl
#else
#define debug(x)
#define debug2(x,y)
#define debug3(x,y,z)
#define debug_v(x)
#define debug_s(x)
#define debug_p(x)
#define debug_m(x)
#define debug_l()
#endif
ll getSum(vector<ll> b) {ll res=0;for(auto v:b){res+=v;}return res;}
ll GCD(ll a, ll b) {if (b == 0) return a;else return GCD(b, a % b);}
ll LCM(ll a, ll b) {ll d=GCD(a,b);return (a/d)*(b/d)*d;}
/*zahyou to ka*/
bool poich(ll P,ll Q){return(0<=P&&P<Q);}
bool poich2(ll i,ll j,ll H,ll W){return(poich(j,W)&&poich(i,H));}
vector<Pair> dxy{{1,0},{-1,0},{0,1},{0,-1}};
//https://algo-logic.info/calc-pow/
ll dpow(ll x, ll n,ll mod) {
ll ret = 1;
while (n > 0) {
if (n & 1) ret = ret * x % mod;
x = x * x % mod;
n >>= 1;
}
return ret;
}
ll chd21(ll N,ll i,ll j){
return N*i+j;
}
Pair chd12(ll N,ll X){
return {X/N,X%N};
}
//input
template <class T>
void input_v(vector<T> &vec){
for(auto &v:vec)cin >> v;
}
vector<ll> MakePrime(long long MAX_N){
vector<long long> Isprime,Prime;
Isprime.resize(MAX_N+2,true);
Isprime[0]=false;
Isprime[1]=false;
for(long long i=2;i*i<=MAX_N;i++){
if(Isprime[i]){
for(long long j=i*i;j<=MAX_N;j+=i)Isprime[j]=false;
}
}
for(long long i=0;i<MAX_N;i++)if(Isprime[i])Prime.push_back(i);
return Prime;
}
template<class T>
struct comb{
public:
comb():comb(10000000){}
comb(ll N):A(N,1),B(N,1){
for(ll i=0;i<N;i++){
A[i+1]=A[i]*(i+1);
B[i+1]=1/A[i+1];
}
}
T nCk1(ll n,ll k){
if(n<0||k<0||n-k<0)return (T)0;
return A[n]*B[k]*B[n-k];
}
T nPk1(ll n,ll k){
if(n<0||k<0||n-k<0)return (T)0;
return A[n]*B[k];
}
T nCk2(ll n,ll k){
T res=1;
for(ll i=k+1;i<=n;i++){
res*=i;
}
for(ll i=0;i<=n-k;i++){
res/=i;
}
return res;
}
vector<T> A;
vector<T> B;
};
vector<array<ll,2>> totu_cover(vector<array<ll,2>> points){
vector<array<ll,2>> p=points;
sort(p.begin(),p.end());
ll N=p.size();
auto func=[&](bool bo){
stack<array<ll,2>> st;
queue<array<ll,2>> que;
ll k=2*bo-1;
for(ll i=N-1;i>=0;i--){
que.push(p[i]);
}
while(!que.empty()){
auto v=que.front();
if(st.size()<2){
st.push(v);
que.pop();
}else{
auto o=st.top();st.pop();
auto t=st.top();
auto[a,b]=t;
auto[c,d]=o;
auto[e,f]=v;
if((f-b)*(a-c)*k>(d-b)*(a-e)*k){
continue;
}else{
st.push(o);
st.push(v);
que.pop();
}
}
}
vector<array<ll,2>> res;
while(!st.empty()){
res.push_back(st.top());
st.pop();
}
return res;
};
auto v=func(1);
auto u=func(0);
ll vn=v.size(),un=u.size();
vector<array<ll,2>> ans;
set<array<ll,2>> cot;
for(ll i=vn-1;i>=0;i--){
ans.push_back(v[i]);
cot.insert(v[i]);
}
for(ll i=0;i<un;i++){
if(!cot.count(u[i])){
ans.push_back(u[i]);
}
cot.insert(u[i]);
}
return ans;
}struct Edge {
long long to;
};
using Graph = vector<vector<Edge>>;
/* LCA(G, root): 木 G に対する根を root として Lowest Common Ancestor を求める構造体
query(u,v): u と v の LCA を求める。計算量 O(logn)
前処理: O(nlogn)時間, O(nlogn)空間
*/
struct LCA {
vector<vector<int>> parent; // parent[k][u]:= u の 2^k 先の親
vector<int> dist; // root からの距離
LCA(const Graph &G, int root = 0) { init(G, root); }
// 初期化
void init(const Graph &G, int root = 0) {
int V = G.size();
int K = 1;
while ((1 << K) < V) K++;
parent.assign(K, vector<int>(V, -1));
dist.assign(V, -1);
dfs(G, root, -1, 0);
for (int k = 0; k + 1 < K; k++) {
for (int v = 0; v < V; v++) {
if (parent[k][v] < 0) {
parent[k + 1][v] = -1;
} else {
parent[k + 1][v] = parent[k][parent[k][v]];
}
}
}
}
// 根からの距離と1つ先の頂点を求める
void dfs(const Graph &G, int v, int p, int d) {
parent[0][v] = p;
dist[v] = d;
for (auto e : G[v]) {
if (e.to != p) dfs(G, e.to, v, d + 1);
}
}
int query(int u, int v) {
if (dist[u] < dist[v]) swap(u, v); // u の方が深いとする
int K = parent.size();
// LCA までの距離を同じにする
for (int k = 0; k < K; k++) {
if ((dist[u] - dist[v]) >> k & 1) {
u = parent[k][u];
}
}
// 二分探索で LCA を求める
if (u == v) return u;
for (int k = K - 1; k >= 0; k--) {
if (parent[k][u] != parent[k][v]) {
u = parent[k][u];
v = parent[k][v];
}
}
return parent[0][u];
}
ll getdist(int u,int v){
return dist[u]+dist[v]-2*dist[query(u,v)];
}
};
map<array<ll,3>,ld> mp;
ld ans(ll N,ll M,ll K){
if(mp.count({N,M,K})){
return mp[{N,M,K}];
}
//例外をうまいこと処理してこう。
//N==1の時、M個からK個選んで特定のやつを含まない確率は？
//M個からK個選んだ時分のM-1個からK個選んだ時=(M-1)!*(M-K)!/(M!*(M-K-1)!)
if(N==1){
return max((M-K)/(ld)(M),(ld)0.0);
}
ld res=0;
//甘味があった時
ll eaten=1;
eaten+=M*(N-1);
if(eaten<K){
res+=(M-1)/(ld)(N*M)*ans(1,M-1,K-eaten);
}else{
res+=(M-1)/(ld)(N*M);
}
//甘味がなかった時
eaten=M;
if(eaten<K){
res+=(N-1)/(ld)(N)*ans(N-1,M,K-eaten);
}else{
res+=(N-1)/(ld)(N);
}
mp[{N,M,K}]=res;
return res;
}
void solve(){
ll N,M,K;cin >> N >> M >> K;
cout << fixed << setprecision(15) << ans(N,M,K) << endl;
}
int main(){
ll T=1;cin >> T;
while(T--){
solve();
}
return 0;
}