AtCoder Beginner Contest 154 D - Dice in Line

無事修論を出しまして一段落、ねむーです。

今回はAtCoder(https://atcoder.jp/contests/abc154/tasks/abc154_d)にて開催されました、AtCoder Beginner Contest 154 D問題「D - Dice in Line」の問題と僕との戦闘記です。

0.はじめに

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

1.問題文

N 個のサイコロが左から右に一列に並べてあります。左から i 番目のサイコロは 1 から p i までの p i 種類の目がそれぞれ等確率で出ます。

隣接する K 個のサイコロを選んでそれぞれ独立に振ったとき、出る目の合計の期待値の最大値を求めてください。

2.制約

• 1 ≤ K ≤ N ≤ 200000
• 1 ≤ p i ≤ 1000
• 入力で与えられる値は全て整数

3.入出力例

• 入力

5 3
1 2 2 4 5

• 出力

7.000000000000

4.初見の感想

• それぞれのサイコロの期待値は独立に求められる
• 計算量O(N)で解きたい

5.学びポイント

• 期待値和がK個になるまで期待値を前から足し合わせる
• K個を超えたら最初の期待値を減じて、新しい数字を足し合わせる
• 上の処理で連続するK個の期待値和を計算できる

6.コードと簡単な解説

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

class Program
{
    public static void Main()
    {
        string []input=Console.ReadLine().Split();
        int N = int.Parse(input[0]);
        int K = int.Parse(input[1]);
        input = Console.ReadLine().Split();
        int[] p = new int[N];
        double[] avg = new double[N];
        double max = 0;
        double temp = 0;
        for(int i=0; i < N; i++)
        {
            p[i] = int.Parse(input[i]);
            //期待値計算
            avg[i] = (p[i] - 1) * 0.5 + 1;
            if (i >= K) {
                //順に連続期待値和を計算
                temp = temp + avg[i] - avg[i - (K)];
            }
            else
            {
                temp += avg[i];
            }
            if (temp > max) { max = temp; }
        }
        Console.WriteLine(max);
    }
}

7.最後に

最初にKを見逃してて一回WAしました…