AtCoderのABC    次のABCの問題へ    前のABCの問題へ

ABC214-C Distribution


問題へのリンク


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");
            WillReturn.Add("4 1 5");
            WillReturn.Add("3 10 100");
            //3
            //7
            //8
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4");
            WillReturn.Add("100 100 100 100");
            WillReturn.Add("1 1 1 1");
            //1
            //1
            //1
            //1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("4");
            WillReturn.Add("1 2 3 4");
            WillReturn.Add("1 2 4 7");
            //1
            //2
            //4
            //7
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("8");
            WillReturn.Add("84 87 78 16 94 36 87 93");
            WillReturn.Add("50 22 63 28 91 60 64 27");
            //50
            //22
            //63
            //28
            //44
            //60
            //64
            //27
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] SArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        long[] TArr = InputList[2].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        long UB = TArr.GetUpperBound(0);

        // 添字のList[値]
        var TListDict = new Dictionary<long, List<long>>();
        for (int I = 0; I <= UB; I++) {
            long TVal = TArr[I];
            if (TListDict.ContainsKey(TVal) == false) {
                TListDict[TVal] = new List<long>();
            }
            TListDict[TVal].Add(I);
        }

        foreach (var EachPair in TListDict.OrderBy(pX => pX.Key)) {
            foreach (int EachStaInd in EachPair.Value) {
                int CurrInd = EachStaInd;
                while (true) {
                    int NextInd = CurrInd + 1;
                    if (NextInd > UB) NextInd = 0;

                    long Kouho = TArr[CurrInd] + SArr[CurrInd];
                    if (TArr[NextInd] > Kouho) {
                        TArr[NextInd] = Kouho;
                    }
                    else {
                        break;
                    }

                    CurrInd++;
                    if (CurrInd > UB) CurrInd = 0;
                }
            }
        }

        Array.ForEach(TArr, pX => Console.WriteLine(pX));
    }
}


解説

高橋君が宝石を配る時間を、仮の最小値として、
それより小さい値にできるかを、時系列で調べてます。