ABC480-C Self-Stopping Shower

問題へのリンク

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("3 4 20");
            WillReturn.Add("6 7 12");
            //4
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("9 37 480");
            WillReturn.Add("12 123 132 213 231 312 321 500 1000");
            //11
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("1 1 1000000000");
            WillReturn.Add("1");
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = GetSplitArr(InputList[0]);
        long K = wkArr[1];
        long T = wkArr[2];

        long[] AArr = GetSplitArr(InputList[1]);
        Array.Sort(AArr);
        var Que = new Queue<long>(AArr);

        long Answer = 0;
        long CurrPos = 0;
        while (true) {
            // ゴールしたら終了
            if (CurrPos >= T) break;

            if (Que.Count > 0) {
                long Peek = Que.Peek();
                long RangeSta = Peek;
                long RangeEnd = Peek + K;
                if (CurrPos >= RangeSta) {
                    // 青木君の辺で右に移動
                    CurrPos = Math.Max(CurrPos, RangeEnd);
                    Que.Dequeue();
                    continue;
                }
            }

            // 高橋君の辺で右に移動
            Answer++;
            CurrPos += K;
        }
        Console.WriteLine(Answer);
    }
}

解説

青木君の辺はコスト0
高橋君の辺はコスト1
「ノード0からノードTまでの移動コストを求める」という解法で、
解いてます。

Tが10億で、Kが1だと
10億回のインクリメント処理が必要となりますが、
ループ内の処理が軽いので、2秒で間に合います。