0.はじめに

今回も、プログラミング言語はC#を使用しています。

1.問題文

すぬけ君は 1 〜 N の整数が等確率で出る N 面サイコロと表と裏が等確率で出るコインを持っています。すぬけ君は、このサイコロとコインを使って今から次のようなゲームをします。

まず、サイコロを 1 回振り、出た目を現在の得点とする。

得点が 1 以上 K − 1 以下である限り、すぬけ君はコインを振り続ける。表が出たら得点は 2 倍になり、裏が出たら得点は 0 になる。

得点が 0 になった、もしくは K 以上になった時点でゲームが終了する。このとき、得点が K 以上である場合すぬけ君の勝ち、 0 である場合すぬけ君の負けである。

N と K が与えられるので、このゲームですぬけ君が勝つ確率を求めてください。

2.制約

1 ≤ N ≤ 10⁵
1 ≤ K ≤ 10⁵
入力はすべて整数

3.入力例

入力

100000 5

出力

0.999973749998

4.初見の感想

毎回確率の係数を計算したくない
最初の数字がK以上なら無条件クリアとなる
確率の係数0.5をM回掛けるかは「Kを2で少なくともM回割れば最初の初期値以下になる」という条件で求められる(最初の初期値をどんどん2倍にするゲームなので…)

5.学びポイント

0.5を掛け算する回数は初期値が大きいほど少ないのでfor文をNから下に回します
Nの値がKよりとても小さい場合、最初の0.5を何回掛けるかを出すのにループを回してしまう→ループを回さない工夫が必要
Nで割る処理は値を非常に小さくしてしまうため、最後に行う(誤差を防止するため)

6.コードと簡単な解説

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
//入力
        string[] input = Console.ReadLine().Split(' ');
        double N = double.Parse(input[0]);
        double K = double.Parse(input[1]);
        double ans = 0;
        double num = 1;
//計算回数の少ないNからループを行う
        for(double i=N;i>0; i--)
        {
            if (i < K) {
　　　　  //係数は順番に*0.5ずつ小さくなる性質がある
                num *= 0.5;
                K = K / 2;
            }
            if(i>=K){
                ans += num;
            }
            //ループを止める処理
            if (ans == 0) { i = N + 1; }
        }
        //Nで割る処理は最後に行う
        ans = ans / N;
        Console.WriteLine(ans);
    }
}

7.最後に

解けましたが1時間ほどかかってしまったので、鍛錬が必要です(^-^;

ねむーの日記~AtCoderな日々~

福岡に住むプログラミング好きのブログです！

AtCoder Beginner Contest 126 C - Dice and Coin