結果
問題 | No.489 株に挑戦 |
ユーザー |
![]() |
提出日時 | 2022-12-29 20:18:21 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 450 ms / 1,000 ms |
コード長 | 6,865 bytes |
コンパイル時間 | 1,075 ms |
コンパイル使用メモリ | 110,848 KB |
実行使用メモリ | 55,540 KB |
最終ジャッジ日時 | 2024-11-24 20:20:45 |
合計ジャッジ時間 | 9,370 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;using System.Collections.Generic;using System.Linq;// https://yukicoder.me/problems/no/489class Program{static string InputPattern = "InputX";static List<string> GetInputList(){var WillReturn = new List<string>();if (InputPattern == "Input1") {WillReturn.Add("7 2 1000");WillReturn.Add("1");WillReturn.Add("3");WillReturn.Add("5");WillReturn.Add("1");WillReturn.Add("4");WillReturn.Add("4");WillReturn.Add("7");//4000//0 2}else if (InputPattern == "Input2") {WillReturn.Add("5 4 100");WillReturn.Add("1");WillReturn.Add("2");WillReturn.Add("1");WillReturn.Add("2");WillReturn.Add("1");//100//0 1}else if (InputPattern == "Input3") {WillReturn.Add("5 1 100");WillReturn.Add("5");WillReturn.Add("4");WillReturn.Add("3");WillReturn.Add("3");WillReturn.Add("1");//0}else if (InputPattern == "Input4") {return System.IO.File.ReadAllLines(@"D:\CSharp\TestConsole\test_in\system_test6.txt").ToList();}else {string wkStr;while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);}return WillReturn;}struct ProfitInfoDef{internal int BuyInd;internal int SellInd;internal long Profit;}static void Main(){List<string> InputList = GetInputList();int[] wkArr = InputList[0].Split(' ').Select(pX => int.Parse(pX)).ToArray();int N = wkArr[0];int D = wkArr[1];int K = wkArr[2];int[] XArr = InputList.Skip(1).Take(N).Select(pX => int.Parse(pX)).ToArray();int UB = XArr.GetUpperBound(0);var InsSparseTable = new SparseTable<int>(XArr, false);// IndのList[値]なDictvar IndListDict = new Dictionary<int, List<int>>();for (int I = 0; I <= UB; I++) {if (IndListDict.ContainsKey(XArr[I]) == false) {IndListDict[XArr[I]] = new List<int>();}IndListDict[XArr[I]].Add(I);}var AnswerKouho = new List<ProfitInfoDef>();for (int I = 0; I <= UB; I++) {int RangeSta = I;int RangeEnd = I + D;RangeEnd = Math.Min(UB, RangeEnd);int MaxVal = InsSparseTable.Query(RangeSta, RangeEnd);ProfitInfoDef WillAdd;WillAdd.BuyInd = I;int ResultNibunhou = ExecNibunhou_LowerBound(I, IndListDict[MaxVal]);WillAdd.SellInd = IndListDict[MaxVal][ResultNibunhou];WillAdd.Profit = (long)K * (XArr[WillAdd.SellInd] - XArr[WillAdd.BuyInd]);AnswerKouho.Add(WillAdd);}if (AnswerKouho.Exists(pX => pX.Profit > 0)) {ProfitInfoDef AnswerItem = AnswerKouho.OrderByDescending(pX => pX.Profit).First();Console.WriteLine(AnswerItem.Profit);Console.WriteLine("{0} {1}", AnswerItem.BuyInd, AnswerItem.SellInd);}else {Console.WriteLine(0);}}// 二分法で、Val以上で最小の値を持つ、添字を返すstatic int ExecNibunhou_LowerBound(int pVal, List<int> pList){// 最後の要素がVal未満の特殊ケースif (pVal > pList.Last()) {return -1;}// 最初の要素がVal以上の特殊ケースif (pVal <= pList[0]) {return 0;}int L = 0;int R = pList.Count - 1;while (L + 1 < R) {int Mid = (L + R) / 2;if (pList[Mid] >= pVal) {R = Mid;}else {L = Mid;}}return R;}}#region SparseTable// スパーステーブルinternal class SparseTable<Type>{private Type[] mInitArr;private int UB_0;private int UB_1;// 最小値か最大値[開始Ind,2の指数]なArrprivate Type[,] mMinOrMaxArr;// Log2の値[2べきな値] なDictstatic Dictionary<int, int> mLogDict = new Dictionary<int, int>();// 最小値を取得するか?private bool mIsMin = false;// コンストラクタinternal SparseTable(IEnumerable<Type> pInitEnum, bool pIsMin){mIsMin = pIsMin;mInitArr = pInitEnum.ToArray();UB_0 = mInitArr.GetUpperBound(0);int Sisuu = 0;int Beki2 = 1;while (true) {mLogDict[Beki2] = Sisuu;if (Beki2 > mInitArr.Length) {break;}Beki2 *= 2;Sisuu++;}UB_1 = Sisuu;mMinOrMaxArr = new Type[UB_0 + 1, UB_1 + 1];// 長さ1の分を初期化for (int I = 0; I <= UB_0; I++) {mMinOrMaxArr[I, 0] = mInitArr[I];}for (int LoopLength = 2; LoopLength < int.MaxValue; LoopLength *= 2) {bool WillBreak = true;int HalfRange = LoopLength / 2;for (int I = 0; I <= UB_0; I++) {int StaInd1 = I;int EndInd1 = I + HalfRange - 1;int StaInd2 = EndInd1 + 1;int EndInd2 = StaInd2 + HalfRange - 1;if (EndInd2 > UB_0) break;var KouhoList = new List<Type>();KouhoList.Add(mMinOrMaxArr[I, mLogDict[HalfRange]]);KouhoList.Add(mMinOrMaxArr[StaInd2, mLogDict[HalfRange]]);if (mIsMin) {mMinOrMaxArr[I, mLogDict[LoopLength]] = KouhoList.Min();}else {mMinOrMaxArr[I, mLogDict[LoopLength]] = KouhoList.Max();}WillBreak = false;}if (WillBreak) break;}}// 閉区間 [L,R]の最小値または最大値を求めるinternal Type Query(int pL, int pR){// 区間を内包する2べきを返すint Beki2 = 1;int Sisuu = 0;while (true) {int LeftRangeMax = pL + Beki2 - 1;int RightRangeMin = pR - Beki2 + 1;if (LeftRangeMax + 1 >= RightRangeMin) {break;}Beki2 *= 2;Sisuu++;}var KouhoList = new List<Type>();KouhoList.Add(mMinOrMaxArr[pL, Sisuu]);KouhoList.Add(mMinOrMaxArr[pR - Beki2 + 1, Sisuu]);if (mIsMin) {return KouhoList.Min();}return KouhoList.Max();}}#endregion