AtCoderのPAST
次のPASTの問題へ
前のPASTの問題へ
第7回PAST O コンピュータ
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("5 1");
WillReturn.Add("2 4");
WillReturn.Add("4 6");
//4
}
else if (InputPattern == "Input2") {
WillReturn.Add("3");
WillReturn.Add("3 2");
WillReturn.Add("1 2");
WillReturn.Add("3 6");
//-1
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static void Main()
{
List<string> InputList = GetInputList();
long Answer = Solve(InputList);
Console.WriteLine(Answer);
}
class ABInfoDef
{
internal bool IsMorning; // 朝か?
internal long Val;
}
static List<ABInfoDef> mABInfoList1 = new List<ABInfoDef>();
static List<ABInfoDef> mABInfoList2 = new List<ABInfoDef>();
static long Solve(List<string> pInputList)
{
long[] wkArr = { };
Action<string> SplitAct = pStr =>
wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();
foreach (string EachStr in pInputList.Skip(1)) {
SplitAct(EachStr);
var WillAdd1 = new ABInfoDef();
WillAdd1.IsMorning = true;
WillAdd1.Val = wkArr[0];
mABInfoList1.Add(WillAdd1);
var WillAdd2 = new ABInfoDef();
WillAdd2.IsMorning = false;
WillAdd2.Val = wkArr[1];
mABInfoList1.Add(WillAdd2);
}
// コンピュータの価値の累積Maxを更新したら、コンピュータを購入可能
long RunMax = long.MinValue;
for (int I = 0; I <= mABInfoList1.Count - 1; I++) {
if (mABInfoList1[I].IsMorning) {
mABInfoList2.Add(mABInfoList1[I]);
continue;
}
if (RunMax < mABInfoList1[I].Val) {
RunMax = mABInfoList1[I].Val;
mABInfoList2.Add(mABInfoList1[I]);
}
}
// 連続したMはまとめる
for (int I = mABInfoList2.Count - 1; 0 <= I; I--) {
if (I > 0) {
if (mABInfoList2[I].IsMorning && mABInfoList2[I - 1].IsMorning) {
mABInfoList2[I - 1].Val += mABInfoList2[I].Val;
mABInfoList2.RemoveAt(I);
}
}
}
// 稼いだ金額の累積和
long[] RunSum = new long[mABInfoList2.Count];
for (int I = 0; I <= mABInfoList2.Count - 1; I++) {
if (mABInfoList2[I].IsMorning) {
RunSum[I] = mABInfoList2[I].Val;
}
else {
RunSum[I] = 0;
}
if (I > 0) {
RunSum[I] += RunSum[I - 1];
}
}
// これより安いコンピュターに使った総額[最後に買ったコンピュータ]なDict
var AnswerDict = new Dictionary<long, long>();
// コンピュータの添字のキュー
var ComputerIndQue = new Queue<int>();
for (int I = 0; I <= mABInfoList2.Count - 1; I++) {
if (mABInfoList2[I].IsMorning == false) {
ComputerIndQue.Enqueue(I);
}
}
for (int I = 0; I <= mABInfoList2.Count - 1; I++) {
// 最初の朝のコンピュータ購入
if (I == 0) {
long CurrMoney = mABInfoList2[0].Val;
while (true) {
if (ComputerIndQue.Count > 0) {
int Peeked = ComputerIndQue.Peek();
long CurrComputer = mABInfoList2[Peeked].Val;
if (CurrComputer <= CurrMoney) {
AnswerDict[CurrComputer] = 0;
ComputerIndQue.Dequeue();
continue;
}
}
break;
}
}
else if (mABInfoList2[I].IsMorning == false) {
long CurrComputer = mABInfoList2[I].Val;
if (AnswerDict.ContainsKey(CurrComputer) == false) {
return -1;
}
// 次のコンピュータの購入
int UB = mABInfoList2.Count - 1;
if (I < UB) {
long CanUseMoney = RunSum[I + 1] - AnswerDict[CurrComputer] - CurrComputer;
while (true) {
if (ComputerIndQue.Count > 0) {
int Peeked = ComputerIndQue.Peek();
long BuyComputer = mABInfoList2[Peeked].Val;
if (BuyComputer <= CanUseMoney) {
AnswerDict[BuyComputer] = AnswerDict[CurrComputer] + CurrComputer;
ComputerIndQue.Dequeue();
continue;
}
}
break;
}
}
}
}
if (ComputerIndQue.Count > 0) {
return -1;
}
long MoneySum = mABInfoList2.Where(pX => pX.IsMorning).Sum(pX => pX.Val);
long LastComputer = AnswerDict.Keys.Max();
long Answer = MoneySum - AnswerDict[LastComputer] - LastComputer;
return Answer;
}
}
解説
まず、コンピュータの価値を単調増加とし
連続したモーニングは、
1つのモーニングにまとめます。
それから
これより安いコンピュターに使った総額[最後に買ったコンピュータ]なDictをDPで更新してます。