ABC126C Dice and Coin - urashima0429

考えたこと

愚直に各 $N$ の確率を求めればよい。以下のコードだと $O(min(N, M))$ だが、テストケースの 14.txt だけどうしても通らず…。なにか間違っているのか、それとも精度が足りないのか…。

#include <iostream>
#include <math.h>
#include <iomanip>
#include <algorithm>
using namespace std;
 
int main(){
    double N, K;
    cin >> N >> K;
    double ans = max( 0.0, 1.0-(K/N) );
    for (long long i = 1; i <= min(K, N); ++i){
        ans += 1.0 / ( N * pow(2.0, ceil( ( log(K) - log(i) ) / log(2) )));
    }
    cout << setprecision(15) << ans << endl;
}

そこで、制約を確認すると
$1 \leq N \leq 10^ 5, 1 \leq K \leq 10^ 5$
であるので計算量のはなし - Hello Wor.log 等を参考にすると $O(NlogK)$ か $O(Nlog^ 2K)$ 程度であることが予想できる。各Nに対して、何回2をかければKを超えるかは $O(log_ 2K)$ で求まるので、結局以下のコードで $O(NlogK)$ で求められてAC。

#include <iostream>
#include <iomanip>
using namespace std;

int main(){
    int N, K;
    cin >> N >> K;
    double ans = 0;
    for (int i = 1; i <= N; ++i){
        int num = i;
        int counter = 0;
        while (num < K){
            num*=2;
            counter++;
        }
        ans += 1/(double)(1<<counter);
    }

    cout << setprecision(15) << ans/(double)N << endl;
    return 0;
}

ついでに

入出力ストリームで浮動小数点型の桁数を指定しないと、勝手に丸められるので注意。デフォルトは6桁

#include <iomanip>
...
// 少数点以下2桁に固定
cout << fixed << setprecision(2) << 3.1415 << endl; // "3.14"