AOJ 1056 Ben Toh

■■■問題■■■

午後8時のスーパーマーケットには、今日も狼と呼ばれる者共が集っていた。
彼らの求めるものはただ一つ、半額のラベルが貼られた弁当である。
数少ないそれを奪い合って、彼らは毎日激しい戦いを繰り広げるのだ。

佐藤も、そんな狼の一人である。
彼は何としても半額弁当を手に入れて、小遣いを浮かせなければならない。

佐藤は優秀な狼なので、最初の日は100%の確率で半額弁当を手に入れることができる。
しかしその翌日は、他の多くの狼たちが結託して佐藤の邪魔をしようとするので、
半額弁当の入手確率は50%に低下する。
それでも手に入れることができたならば、その翌日はさらに激しい妨害を受け、入手確率は25%になる。
以降も同様に、半額弁当を手に入れると、翌日の入手確率はその日の半分になっていく。
一度半額弁当の入手に失敗すると、その翌日の入手確率はまた100%に戻る。 

佐藤はn日の間スーパーマーケットに通いつづけ、半額弁当を得ようとしている。
消費計画を立てたい佐藤のために、
彼が半額弁当を得られる回数の期待値を求めるプログラムを作成してほしい。 

■■■入力■■■

入力は複数のデータセットから構成される。
1つのデータセットに対する入力は、1つの整数nで与えられる。
n=0のとき入力の終了を示す。

1 <= n <= 10万

■■■出力■■■

各データセットごとに、期待値を含む1行を出力せよ。
小数点以下何桁でも表示して構わない。表示する答えは、10の-2乗未満の誤差を含んでいてもよい。

C#のソース

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

class Program
{
    static string InputPattern = "Input1";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("1");
            WillReturn.Add("2");
            WillReturn.Add("3");
            WillReturn.Add("0");
            //1.00000000
            //1.50000000
            //2.12500000
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    //連続して半額弁当を取得できる限界数
    const int LimitSeqCnt = 14;

    static void Main()
    {
        var sw = System.Diagnostics.Stopwatch.StartNew();

        List<string> InputList = GetInputList();
        int[] NArr = InputList.Select(X => int.Parse(X)).TakeWhile(X => X > 0).ToArray();

        Dictionary<int, Decimal> KakurituDict = DeriveKakurituDict();
        foreach (var EachPair in KakurituDict) {
            Console.WriteLine("連続取得個数が{0}個の確率={1}",
                EachPair.Key, EachPair.Value);
        }

        //Nの最大値までの期待値を求める
        int DayCnt = NArr.Max();
        decimal[] KitaitiArr = new decimal[DayCnt + 1];
        for (int I = 1; I <= DayCnt; I++) {
            foreach (var EachPair in KakurituDict) {
                int BentouCnt = EachPair.Key;
                if (BentouCnt > I)
                    BentouCnt = I;
                KitaitiArr[I] += BentouCnt * EachPair.Value;

                int RestDayCnt = I - EachPair.Key - 1;
                if (RestDayCnt > 0)
                    KitaitiArr[I] += KitaitiArr[RestDayCnt] * EachPair.Value;
            }
        }

        for (int I = 1; I <= DayCnt; I++) {
            Console.WriteLine("{0}日での期待値={1}", I, KitaitiArr[I]);
        }

        Array.ForEach(NArr, X => Console.WriteLine(KitaitiArr[X]));
        Console.WriteLine("経過時間={0}", sw.Elapsed);
    }

    //最初の取得個数を添字とし、値が確率の配列
    static Dictionary<int, Decimal> DeriveKakurituDict()
    {
        var WillReturn = new Dictionary<int, decimal>();

        decimal[] BaseArr = new decimal[LimitSeqCnt + 2];
        BaseArr[1] = 1M;
        for (int I = 2; I <= BaseArr.GetUpperBound(0); I++) {
            BaseArr[I] = BaseArr[I - 1] * 0.5M;
        }

        //確率の乗法定理を使う
        for (int I = 1; I <= LimitSeqCnt; I++) {
            decimal wkDec = 1;
            for (int J = 1; J <= I; J++) {
                wkDec *= BaseArr[J];
            }
            //次で弁当を取れない確率(余事象の確率)を掛ける
            wkDec *= (1M - BaseArr[I + 1]);
            WillReturn.Add(I, wkDec);
        }
        return WillReturn;
    }
}

デバッグ情報付の実行結果

連続取得個数が1個の確率=0.5
連続取得個数が2個の確率=0.375
連続取得個数が3個の確率=0.109375
連続取得個数が4個の確率=0.0146484375
連続取得個数が5個の確率=0.000946044921875
連続取得個数が6個の確率=0.000030040740966796875
連続取得個数が7個の確率=0.0000004731118679046630859375
連続取得個数が8個の確率=0.0000000037107383832335472107
連続取得個数が9個の確率=0.0000000000145234935189364478
連続取得個数が10個の確率=0.0000000000000283939538547884
連続取得個数が11個の確率=0.0000000000000000277420230884
連続取得個数が12個の確率=0.0000000000000000000135492185
連続取得個数が13個の確率=0.0000000000000000000000033083
連続取得個数が14個の確率=0.0000000000000000000000000004
1日での期待値=1.0000000000000000000000000000
2日での期待値=1.5000000000000000000000000000
3日での期待値=2.1250000000000000000000000000
1.0000000000000000000000000000
1.5000000000000000000000000000
2.1250000000000000000000000000
経過時間=00:00:00.5133797

解説

1日目からの連続取得個数ごとの確率を使って、
1日目から順に期待値を求めてます。