AtCoderのABC
次のABCの問題へ
前のABCの問題へ
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();
}
}
}
}
解説
開始添字ごとにサイクルを求め、
サイクルの和がプラスかマイナスかで場合分けしてます。