AtCoderの企業コンテスト
次の企業コンテストの問題へ
前の企業コンテストの問題へ
エイシング プログラミング コンテスト 2020 E Camel Train
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("2");
WillReturn.Add("1 5 10");
WillReturn.Add("2 15 5");
WillReturn.Add("3");
WillReturn.Add("2 93 78");
WillReturn.Add("1 71 59");
WillReturn.Add("3 57 96");
WillReturn.Add("19");
WillReturn.Add("19 23 16");
WillReturn.Add("5 90 13");
WillReturn.Add("12 85 70");
WillReturn.Add("19 67 78");
WillReturn.Add("12 16 60");
WillReturn.Add("18 48 28");
WillReturn.Add("5 4 24");
WillReturn.Add("12 97 97");
WillReturn.Add("4 57 87");
WillReturn.Add("19 91 74");
WillReturn.Add("18 100 76");
WillReturn.Add("7 86 46");
WillReturn.Add("9 100 57");
WillReturn.Add("3 76 73");
WillReturn.Add("6 84 93");
WillReturn.Add("1 6 84");
WillReturn.Add("11 75 94");
WillReturn.Add("19 15 3");
WillReturn.Add("12 11 34");
//25
//221
//1354
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
class KLRInfoDef
{
internal long K;
internal long L;
internal long R;
}
static List<KLRInfoDef> mKLRList = new List<KLRInfoDef>();
static void Main()
{
List<string> InputList = GetInputList();
long[] wkArr = { };
Action<string> SplitAct = pStr =>
wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();
long RestCnt = long.Parse(InputList[1]);
for (long I = 2; I <= InputList.Count - 1; I++) {
if (RestCnt == 0) {
RestCnt = long.Parse(InputList[(int)I]);
continue;
}
SplitAct(InputList[(int)I]);
var WillAdd = new KLRInfoDef();
WillAdd.K = wkArr[0];
WillAdd.L = wkArr[1];
WillAdd.R = wkArr[2];
mKLRList.Add(WillAdd);
if (--RestCnt == 0) {
long Result = Solve();
Console.WriteLine(Result);
mKLRList.Clear();
}
}
}
static long Solve()
{
// 基準点を求める
long BaseScore = 0;
var ListLeft = new List<KLRInfoDef>();
var ListRight = new List<KLRInfoDef>();
for (int I = 0; I <= mKLRList.Count - 1; I++) {
long MinVal = Math.Min(mKLRList[I].L, mKLRList[I].R);
BaseScore += MinVal;
mKLRList[I].L -= MinVal;
mKLRList[I].R -= MinVal;
if (mKLRList[I].L <= mKLRList[I].R) {
ListRight.Add(mKLRList[I]);
}
else {
ListLeft.Add(mKLRList[I]);
}
}
// 左のほうが良いラクダの配置
// 得点のList[Kの値] なDict
var ScoreListDict = new Dictionary<long, List<long>>();
foreach (KLRInfoDef EachKLRInfo in ListLeft) {
long NewK = Math.Min(ListLeft.Count, EachKLRInfo.K);
if (ScoreListDict.ContainsKey(NewK) == false) {
ScoreListDict[NewK] = new List<long>();
}
ScoreListDict[NewK].Add(EachKLRInfo.L);
}
var InsPQueue = new PQueue();
long AddScoreLeft = 0;
for (long I = ListLeft.Count; 1 <= I; I--) {
if (ScoreListDict.ContainsKey(I)) {
foreach (long EachVal in ScoreListDict[I]) {
PQueue.PQueueJyoutaiDef WillEnqueue;
WillEnqueue.Val = EachVal;
InsPQueue.Enqueue(WillEnqueue);
}
}
if (InsPQueue.IsEmpty() == false) {
AddScoreLeft += InsPQueue.Dequeue().Val;
}
}
// 右のほうが良いラクダの配置
// 得点のList[Kの値] なDict
ScoreListDict.Clear();
foreach (KLRInfoDef EachKLRInfo in ListRight) {
long NewK = Math.Max(ListLeft.Count + 1, EachKLRInfo.K + 1);
if (ScoreListDict.ContainsKey(NewK) == false) {
ScoreListDict[NewK] = new List<long>();
}
ScoreListDict[NewK].Add(EachKLRInfo.R);
}
InsPQueue = new PQueue();
long AddScoreRight = 0;
for (long I = ListLeft.Count + 1; I <= mKLRList.Count; I++) {
if (ScoreListDict.ContainsKey(I)) {
foreach (long EachVal in ScoreListDict[I]) {
PQueue.PQueueJyoutaiDef WillEnqueue;
WillEnqueue.Val = EachVal;
InsPQueue.Enqueue(WillEnqueue);
}
}
if (InsPQueue.IsEmpty() == false) {
AddScoreRight += InsPQueue.Dequeue().Val;
}
}
return BaseScore + AddScoreLeft + AddScoreRight;
}
}
#region PQueue
// 優先度付きキュー (根のValが最大)
internal class PQueue
{
internal struct PQueueJyoutaiDef
{
internal long Val;
}
private Dictionary<long, PQueueJyoutaiDef> mHeapDict = new Dictionary<long, PQueueJyoutaiDef>();
internal bool IsEmpty()
{
return mHeapDict.Count == 0;
}
internal long Count()
{
return mHeapDict.Count;
}
internal long Peek()
{
return mHeapDict[1].Val;
}
// エンキュー処理
internal void Enqueue(PQueueJyoutaiDef pAddJyoutai)
{
long CurrNode = 1 + mHeapDict.Count;
mHeapDict[CurrNode] = pAddJyoutai;
while (1 < CurrNode && mHeapDict[CurrNode / 2].Val < mHeapDict[CurrNode].Val) {
PQueueJyoutaiDef Swap = mHeapDict[CurrNode];
mHeapDict[CurrNode] = mHeapDict[CurrNode / 2];
mHeapDict[CurrNode / 2] = Swap;
CurrNode /= 2;
}
}
// デキュー処理
internal PQueueJyoutaiDef Dequeue()
{
PQueueJyoutaiDef TopNode = mHeapDict[1];
long LastNode = mHeapDict.Count;
mHeapDict[1] = mHeapDict[LastNode];
mHeapDict.Remove(LastNode);
MinHeapify(1);
return TopNode;
}
// 根ノードを指定し、根から葉へヒープ構築
private void MinHeapify(long pRootNode)
{
if (mHeapDict.Count <= 1) {
return;
}
long Left = pRootNode * 2;
long Right = pRootNode * 2 + 1;
// 左の子、自分、右の子で値が最大のノードを選ぶ
long Smallest = mHeapDict[pRootNode].Val;
long SmallestNode = pRootNode;
if (mHeapDict.ContainsKey(Left) && mHeapDict[Left].Val > Smallest) {
Smallest = mHeapDict[Left].Val;
SmallestNode = Left;
}
if (mHeapDict.ContainsKey(Right) && mHeapDict[Right].Val > Smallest) {
Smallest = mHeapDict[Right].Val;
SmallestNode = Right;
}
// 子ノードのほうが大きい場合
if (SmallestNode != pRootNode) {
PQueueJyoutaiDef Swap = mHeapDict[SmallestNode];
mHeapDict[SmallestNode] = mHeapDict[pRootNode];
mHeapDict[pRootNode] = Swap;
// 再帰的に呼び出し
MinHeapify(SmallestNode);
}
}
}
#endregion
解説
左のほうが高得点なラクダをL
右のほうが高得点なラクダをR
とすると、最適解の1つは、
LLLLLRRRRR
のように、最初にLが連続して、次にRが連続した配置になります。
Lのグループと
Rのグループで
プライオリティキューで
配置して、加点されるラクダを管理しながら、
高得点のラクダから貪欲に配置すれば、解が分かります。