ABC258-E Packing Potatoes

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

class Program
{
    static string InputPattern = "InputX";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("3 2 5");
            WillReturn.Add("3 4 1");
            WillReturn.Add("1");
            WillReturn.Add("2");
            //2
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10 5 20");
            WillReturn.Add("5 8 5 9 8 7 4 4 8 2");
            WillReturn.Add("1");
            WillReturn.Add("1000");
            WillReturn.Add("1000000");
            WillReturn.Add("1000000000");
            WillReturn.Add("1000000000000");
            //4
            //5
            //5
            //5
            //5
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long mX;
    static long[] mWArr;
    static long mAllWSum;

    static long[] mWArrTwin;
    static long[] mWArrTwinRunSum;

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

        mWArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        mAllWSum = mWArr.Sum();

        mWArrTwin = mWArr.Concat(mWArr).ToArray();

        mWArrTwinRunSum = (long[])mWArrTwin.Clone();
        for (long I = 1; I <= mWArrTwinRunSum.GetUpperBound(0); I++) {
            mWArrTwinRunSum[I] += mWArrTwinRunSum[I - 1];
        }

        var AppearList = new List<string>();
        var AppearSet = new HashSet<string>();

        string[] PreCycleArr;
        string[] CycleArr;

        long CurrInd = 0;
        string CurrRangeInfo = DeriveRangeInfo(ref CurrInd);
        while (true) {
            if (AppearSet.Contains(CurrRangeInfo)) {
                PreCycleArr = AppearList.TakeWhile(pX => pX != CurrRangeInfo).ToArray();
                CycleArr = AppearList.SkipWhile(pX => pX != CurrRangeInfo).ToArray();
                break;
            }
            AppearList.Add(CurrRangeInfo);
            AppearSet.Add(CurrRangeInfo);

            CurrRangeInfo = DeriveRangeInfo(ref CurrInd);
        }

        var sb = new System.Text.StringBuilder();
        foreach (string EachStr in InputList.Skip(2)) {
            long K = long.Parse(EachStr) - 1;

            if (K <= PreCycleArr.GetUpperBound(0)) {
                string Match1 = Regex.Match(PreCycleArr[K], "[0-9]+$").Value;
                sb.AppendLine(Match1);
                continue;
            }
            K -= PreCycleArr.Length;
            K %= CycleArr.Length;
            string Match2 = Regex.Match(CycleArr[K], "[0-9]+$").Value;
            sb.AppendLine(Match2);
        }
        Console.Write(sb.ToString());
    }

    // 開始添字を引数として、(開始添字,個数)を返す
    static string DeriveRangeInfo(ref long pCurrInd)
    {
        long StaInd = pCurrInd;

        // 何週するか
        long SyuuCnt = mX / mAllWSum;

        if (mX % mAllWSum == 0) {
            return string.Format("{0},{1}", pCurrInd, SyuuCnt * mWArr.Length);
        }

        long RestX = mX % mAllWSum;

        long L = pCurrInd;
        long R = mWArrTwinRunSum.GetUpperBound(0);
        long MinusVal = 0;
        if (0 < pCurrInd) {
            MinusVal += mWArrTwinRunSum[pCurrInd - 1];
        }

        // 最初の要素がRestX以上の特殊ケース
        if (RestX <= mWArrTwinRunSum[L] - MinusVal) {
            pCurrInd++;
            pCurrInd %= mWArr.Length;
            return string.Format("{0},{1}", L, SyuuCnt * mWArr.Length + 1);
        }

        while (L + 1 < R) {
            long Mid = (L + R) / 2;

            if (RestX <= mWArrTwinRunSum[Mid] - MinusVal) {
                R = Mid;
            }
            else {
                L = Mid;
            }
        }

        pCurrInd = R + 1;
        pCurrInd %= mWArr.Length;

        return string.Format("{0},{1}", StaInd, SyuuCnt * mWArr.Length + (R - StaInd + 1));
    }
}

解説

考察すると
途中からサイクルになると分かるので
(開始添字,個数)を順に求めます。

(開始添字,個数)をナイーブに求めるとTLEするので、
累積和と二分法を使ってます。