このコンテストの回答の速度を上げようとしているときに、2 つの値を取り、出力を生成する関数がありn
ますk
。計算が繰り返されるのでメモしておきます。n
との制約k
が10^5
! だから私はマップを使用しています:
std::map<std::pair<int,int>,double> m;
double solve(int n, int k)
{
if(k==0) return n;
if(k==1) return (n-1)/2.0;
std::pair<int,int> p = std::make_pair(n,k);
std::map<std::pair<int,int>,double>::iterator it;
if( (it=m.find(p)) != m.end())
return it->second;
double ans = 0;
for(int i=1 ; i<=n-1 ; i++)
ans += solve(i,k-1);
ans = ans/n;
m[p] = ans;
return ans;
}
しかし、明らかに、このアプローチは遅すぎます。私のメモ化に何か問題がありますか?または、マップからの対数フェッチではなく、配列のような一定時間のフェッチを取得できますか?
この関数は、この繰り返しを解決します。
f(x,0) = x
とf(x,1) = (x-1)/2
これはより良い方法で解決できますか?よろしくお願いします。