結果

問題 No.489 株に挑戦
コンテスト
ユーザー aketijyuuzou
提出日時 2026-06-27 13:41:54
言語 C#(csc)
(csc 3.9.0)
コンパイル:
csc -langversion:latest -unsafe -warn:0 -o+ /r:System.Numerics.dll _filename_ -out:a.exe
実行:
/usr/bin/mono a.exe
結果
AC  
実行時間 209 ms / 1,000 ms
コード長 9,694 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 826 ms
コンパイル使用メモリ 113,152 KB
実行使用メモリ 54,396 KB
最終ジャッジ日時 2026-06-27 13:42:07
合計ジャッジ時間 5,659 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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.

ソースコード

diff #
raw source code 

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("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 {
            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[値]なDict
        var 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> where Type : IComparable<Type>
{
    // 最小値か最大値[2の指数][開始Ind]なArr
    private Type[][] mMinOrMaxJagArr;

    // Log2の値[2べき値] なDict
    private Dictionary<long, long> mLogDict = new Dictionary<long, long>();

    // 対応する2べき値[クエリの区間長]
    private long[] mBeki2Arr;

    // 最小値を取得するか？
    private bool mIsMin = false;

    // コンストラクタ1(配列が引数)
    internal SparseTable(Type[] pInitArr, bool pIsMin)
    {
        mIsMin = pIsMin;

        long Sisuu = 0;
        long Beki2 = 1;
        while (true) {
            mLogDict[Beki2] = Sisuu;
            Beki2 *= 2;

            if (Beki2 > pInitArr.Length) {
                break;
            }
            Sisuu++;
        }

        mMinOrMaxJagArr = new Type[Sisuu + 1][];
        foreach (var EachPair in mLogDict) {
            long CurrBeki2 = EachPair.Key;
            long CurrSisuu = EachPair.Value;
            long CurrUB = pInitArr.GetUpperBound(0) - CurrBeki2 + 1;
            mMinOrMaxJagArr[CurrSisuu] = new Type[CurrUB + 1];
        }

        // 長さ1の分を初期化
        for (long I = 0; I <= pInitArr.GetUpperBound(0); I++) {
            mMinOrMaxJagArr[0][I] = pInitArr[I];
        }

        // コンストラクタのヘルパメソッド
        ConstructorHelper();

        // 対応する2べき値[クエリの区間長]を設定
        SetBeki2Arr(pInitArr.Length);
    }

    // コンストラクタ2(Listが引数)
    internal SparseTable(List<Type> pInitList, bool pIsMin)
    {
        mIsMin = pIsMin;

        long Sisuu = 0;
        long Beki2 = 1;
        while (true) {
            mLogDict[Beki2] = Sisuu;
            Beki2 *= 2;

            if (Beki2 > pInitList.Count) {
                break;
            }
            Sisuu++;
        }

        mMinOrMaxJagArr = new Type[Sisuu + 1][];
        foreach (var EachPair in mLogDict) {
            long CurrBeki2 = EachPair.Key;
            long CurrSisuu = EachPair.Value;
            long CurrUB = pInitList.Count - 1 - CurrBeki2 + 1;
            mMinOrMaxJagArr[CurrSisuu] = new Type[CurrUB + 1];
        }

        // 長さ1の分を初期化
        for (int I = 0; I <= pInitList.Count - 1; I++) {
            mMinOrMaxJagArr[0][I] = pInitList[I];
        }

        // コンストラクタのヘルパメソッド
        ConstructorHelper();

        // 対応する2べき値[クエリの区間長]を設定
        SetBeki2Arr(pInitList.Count);
    }

    // コンストラクタ3(列挙が引数)
    internal SparseTable(IEnumerable<Type> pInitEnum, bool pIsMin)
    {
        mIsMin = pIsMin;

        Type[] InitArr = pInitEnum.ToArray();

        long Sisuu = 0;
        long Beki2 = 1;
        while (true) {
            mLogDict[Beki2] = Sisuu;
            Beki2 *= 2;

            if (Beki2 > InitArr.Length) {
                break;
            }
            Sisuu++;
        }

        mMinOrMaxJagArr = new Type[Sisuu + 1][];
        foreach (var EachPair in mLogDict) {
            long CurrBeki2 = EachPair.Key;
            long CurrSisuu = EachPair.Value;
            long CurrUB = InitArr.GetUpperBound(0) - CurrBeki2 + 1;
            mMinOrMaxJagArr[CurrSisuu] = new Type[CurrUB + 1];
        }

        // 長さ1の分を初期化
        for (int I = 0; I <= InitArr.GetUpperBound(0); I++) {
            mMinOrMaxJagArr[0][I] = InitArr[I];
        }

        // コンストラクタのヘルパメソッド
        ConstructorHelper();

        // 対応する2べき値[クエリの区間長]を設定
        SetBeki2Arr(InitArr.Length);
    }

    // 対応する2べき値[クエリの区間長]を設定
    private void SetBeki2Arr(long pDataLen)
    {
        long[] Beki2Arr = mLogDict.Keys.ToArray();

        mBeki2Arr = new long[pDataLen + 1];
        long CurrBeki2 = 1;
        for (long I = 0; I <= pDataLen; I++) {
            mBeki2Arr[I] = CurrBeki2;
            if (mLogDict.ContainsKey(I)) {
                CurrBeki2 = I;
            }
        }
    }

    // コンストラクタのヘルパメソッド
    private void ConstructorHelper()
    {
        //Console.WriteLine("■■■ダブリングします■■■");
        for (long LoopLength = 2; LoopLength < long.MaxValue; LoopLength *= 2) {
            if (mLogDict.ContainsKey(LoopLength) == false) break;

            long HalfRange = LoopLength / 2;
            Type[] CurrArr = mMinOrMaxJagArr[mLogDict[HalfRange]];
            Type[] SendArr = mMinOrMaxJagArr[mLogDict[LoopLength]];
            for (long I = 0; I <= SendArr.GetUpperBound(0); I++) {
                long StaInd1 = I;
                long EndInd1 = I + HalfRange - 1;
                long StaInd2 = EndInd1 + 1;
                long EndInd2 = StaInd2 + HalfRange - 1;

                Type Val1 = CurrArr[I];
                Type Val2 = CurrArr[StaInd2];
                int CompResult = Val1.CompareTo(Val2);
                if (mIsMin) {
                    SendArr[I] = (CompResult >= 1 ? Val2 : Val1);
                }
                else {
                    SendArr[I] = (CompResult >= 1 ? Val1 : Val2);
                }
            }
        }
    }

    // 閉区間 [L,R]の最小値または最大値を求める
    internal Type Query(long pL, long pR)
    {
        // 区間を内包する2べき使用
        long RangeLen = pR - pL + 1;
        long Beki2 = mBeki2Arr[RangeLen];
        long Sisuu = mLogDict[Beki2];

        Type Val1 = mMinOrMaxJagArr[Sisuu][pL];
        Type Val2 = mMinOrMaxJagArr[Sisuu][pR - Beki2 + 1];
        int CompResult = Val1.CompareTo(Val2);

        if (mIsMin) {
            return (CompResult >= 1 ? Val2 : Val1);
        }
        return (CompResult >= 1 ? Val1 : Val2);
    }
}
#endregion
0