C - HSI

期待値 競プロ

はじめに

競技プログラミング、AtCoder Beginner Contest 078
C - HSI
言語はC#
何かあればTwitter→@pirorirori_n712まで

問題

問題文

高橋くんはプログラミングコンテストに出ていますが， YES か NO で答える問題でTLEしてしまいました。

提出の詳細を見ると，テストケースは全てで N ケースあり，そのうち M ケースでTLEしていました。

そこで高橋くんは, M ケースではそれぞれ実行に 1900 ms かかって 1/2 の確率で正解し，
残りの N−M ケースでそれぞれ実行に 100 ms かかって必ず正解するプログラムへ書き換えました。

そして，以下の操作を行います。

・このプログラムを提出する。
・全てのケースの実行が終わるまで待機する。
・もし M ケースのうちどれかで不正解だった場合，もう一度プログラムを提出する。
・これを，一度で全てのケースに正解するまで繰り返す。

この操作が終了するまでの，プログラムの実行時間の総和の期待値を X msとした時，X を出力してください。
なお，X は整数で出力してください。

制約

・入力は全て整数
・1≤N≤100
・1≤M≤min(N,5)

入力

入力は以下の形式で標準入力から与えられる。

N M

出力

実行時間の総和の期待値 X を整数で出力してください。 なお，X はこの問題の制約下で，10^9 以下の整数となることが証明できます。

解き方

以下を参考にしています。
https://img.atcoder.jp/arc085/editorial.pdf
AtCoder ARC 085 C - HSI (300 点) - けんちょんの競プロ精進記録
ARC085 / ABC078 C HSI - 足跡-sokuseki-
ABC078 C問題 : HSI - 忘れても大丈夫

解き方の流れ

問題文から

M ケースではそれぞれ実行に 1900 ms かかって 1/2 の確率で正解し，
残りの N−M ケースでそれぞれ実行に 100 ms かかって必ず正解するプログラム

を高橋君が書くことが分かるので
一回のプログラム提出の際にかかる時間は

1900×M+100×(N-M)

です。

これを全てのケースが正解するまで繰り返すので、
全体の時間は

(1900×M+100×(N-M))×(全てのテストケースが通るまでにかかる回数)

となります。

全てのテストケースが通るまでにかかる回数は
M問が全て正解するまでの回数の期待値です。

例えばMが1だとすると
正解する確率は1/2なので
2回が期待値になります。

これがMが2だとすると
正解する確率は1/2×1/2=1/4になり
4回が期待値になります。

つまり 全てのテストケースが通るまでにかかる回数は
それぞれの提出で正解する確率が(1/2)Mなので
2Mということになります。

証明は以下の記事でされていました。
AtCoder ARC 085 C - HSI (300 点) - けんちょんの競プロ精進記録

これを加えると
先程の式は以下のようになり
これで答えを出すことができます。

(1900×M+100×(N-M))×(2^M)

全体のコード

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

class Cmondai
{
    static void Main()
    {
        var nm = Console.ReadLine().Split(' ').Select(x => Int64.Parse(x)).ToArray(); ;
        var N = nm[0];
        var M = nm[1];
        //Mが全て正解するまでにかかる回数の期待値
        var count = Math.Pow(2, M);
        //一回のプログラム提出にかかる時間
        var time = 1900 * M + 100 * (N - M);
        //最終的にかかる時間は　(一回のプログラム提出にかかる時間)×(Mが全て正解するまでにかかる回数の期待値)
        Console.WriteLine(count * time);
    }
}