ABC003-C AtCoderプログラミング講座

問題へのリンク

C#のソース

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

class Program
{
    static string InputPattern = "InputX";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("2 2");
            WillReturn.Add("1000 1500");
            //1000.000000
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2 1");
            WillReturn.Add("1000 1500");
            //750
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10 5");
            WillReturn.Add("2604 2281 3204 2264 2200 2650 2229 2461 2439 2211");
            //2820.031250000
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] wkArr = InputList[0].Split(' ').Select(pX => int.Parse(pX)).ToArray();
        int K = wkArr[1];

        decimal[] RArr = InputList[1].Split(' ').Select(pX => decimal.Parse(pX)).ToArray();

        decimal Answer = 0;

        var TakeList = RArr.OrderByDescending(pX => pX).Take(K).ToList();
        var Query = TakeList.OrderBy(pX => pX);
        foreach (decimal EachItem in Query) {
            Answer = (Answer + EachItem) / 2;
        }
        Console.WriteLine(Answer);
    }
}

解説

見るK個の動画は、直感で、レートの降順のK個が最適だと分かります。

A B C という動画をこの順に見る場合
Aを見ると、レートは A/2 になります。
次のBを見ると、レートは (A/2 + B ) / 2 = A/4 + B/2 になります。
次のCを見ると、レートは (A/4 + B/2 + C ) / 2 = A/8 + B/4 + C/2 になります。

よって、動画は、レートの昇順に見るのが最適と分かります。