ABC175-D Moving Piece

問題へのリンク

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("5 2");
            WillReturn.Add("2 4 5 1 3");
            WillReturn.Add("3 4 -10 -8 8");
            //8
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2 3");
            WillReturn.Add("2 1");
            WillReturn.Add("10 -7");
            //13
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("3 3");
            WillReturn.Add("3 1 2");
            WillReturn.Add("-1000 -2000 -3000");
            //-1000
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("10 58");
            WillReturn.Add("9 1 6 7 8 4 3 2 10 5");
            WillReturn.Add("695279662 988782657 -119067776 382975538 -151885171 -177220596 -169777795 37619092 389386780 980092719");
            //29507023469
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static int mK;
    static int[] mPArr;
    static int[] mCArr;
    static int UB;

    static void Main()
    {
        List<string> InputList = GetInputList();

        int[] wkArr = InputList[0].Split(' ').Select(pX => int.Parse(pX)).ToArray();
        mK = wkArr[1];

        mPArr = InputList[1].Split(' ').Select(pX => int.Parse(pX)).ToArray();
        mCArr = InputList[2].Split(' ').Select(pX => int.Parse(pX)).ToArray();
        UB = mCArr.GetUpperBound(0);

        // 0オリジンに変更しておく
        for (int I = 0; I <= UB; I++) {
            mPArr[I]--;
        }

        long Answer = long.MinValue;
        for (int I = 0; I <= UB; I++) {
            long MaxScore = DeriveMaxScore(I);
            Answer = Math.Max(Answer, MaxScore);
        }
        Console.WriteLine(Answer);
    }

    // 開始地点の添字ごとの、最大得点を返す
    static long DeriveMaxScore(int pStaInd)
    {
        var IndList = new List<int>();
        var IndSet = new HashSet<int>();
        int CurrInd = mPArr[pStaInd];
        while (true) {
            IndList.Add(CurrInd);
            IndSet.Add(CurrInd);
            CurrInd = mPArr[CurrInd];
            if (IndSet.Contains(CurrInd)) {
                break;
            }
        }
        int CycleCnt = IndList.Count;

        // サイクルの累積和のList (2周分持たせておく)
        var RunSumList = new List<long>();
        RunSumList.Add(mCArr[IndList[0]]);
        for (int I = 1; I <= IndList.Count - 1; I++) {
            long WillAdd = RunSumList[I - 1];
            WillAdd += mCArr[IndList[I]];
            RunSumList.Add(WillAdd);
        }
        for (int I = 0; I <= IndList.Count - 1; I++) {
            int LastInd = RunSumList.Count - 1;
            long LastVal = RunSumList[LastInd];
            LastVal += mCArr[IndList[I]];
            RunSumList.Add(LastVal);
        }

        if (mK < CycleCnt) {
            return RunSumList.Take(mK).Max();
        }
        else {
            // サイクルの総和
            long CycleSum = 0;
            IndList.ForEach(pX => CycleSum += mCArr[pX]);

            if (CycleSum > 0) { // サイクルの総和がプラスの場合
                long WillReturn = 0;
                long RestCnt = mK;
                if (CycleCnt * 2 <= RestCnt) {
                    // RestCntを2つに分けて考える
                    long RestCnt1 = CycleCnt;
                    long RestCnt2 = RestCnt - CycleCnt;
                    long Syou = RestCnt2 / CycleCnt;
                    WillReturn += Syou * CycleSum;
                    RestCnt2 %= CycleCnt;
                    RestCnt = RestCnt1 + RestCnt2;
                }
                WillReturn += RunSumList.Take((int)RestCnt).Max();
                return WillReturn;
            }
            else { // サイクルの総和がマイナスの場合
                return RunSumList.Take(CycleCnt).Max();
            }
        }
    }
}

解説

開始添字ごとにサイクルを求め、
サイクルの和がプラスかマイナスかで場合分けしてます。