ABC274-F Fishing

問題へのリンク

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 10");
            WillReturn.Add("100 0 100");
            WillReturn.Add("1 10 30");
            WillReturn.Add("10 20 10");
            //111
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3 10");
            WillReturn.Add("100 100 100");
            WillReturn.Add("1 10 30");
            WillReturn.Add("10 20 10");
            //100
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("4 10");
            WillReturn.Add("1000 100 10");
            WillReturn.Add("100 99 1");
            WillReturn.Add("10 0 100");
            WillReturn.Add("1 1 1");
            //1110
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long mA;

    struct FishInfoDef
    {
        internal long W;
        internal long X;
        internal long V;
    }
    static List<FishInfoDef> mFishInfoList = new List<FishInfoDef>();
    static int UB;

    static void Main()
    {
        List<string> InputList = GetInputList();

        long[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();

        SplitAct(InputList[0]);

        mA = wkArr[1];

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            FishInfoDef WillAdd;
            WillAdd.W = wkArr[0];
            WillAdd.X = wkArr[1];
            WillAdd.V = wkArr[2];
            mFishInfoList.Add(WillAdd);
        }
        UB = mFishInfoList.Count - 1;

        Solve();
    }

    struct EventInfoDef : IComparable<EventInfoDef>
    {
        internal long TimeBunshi; // 時間の分子
        internal long TimeBunbo; // 時間の分母
        internal int Type; // イベントのタイプ (1が魚の増加、2が魚の脱出)
        internal int FishInd; // 魚のListでのInd

        public int CompareTo(EventInfoDef pOtherIns)
        {
            long Bunsi1 = TimeBunshi * pOtherIns.TimeBunbo;
            long Bunsi2 = TimeBunbo * pOtherIns.TimeBunshi;

            if (Bunsi1 != Bunsi2) {
                return Bunsi1.CompareTo(Bunsi2);
            }
            return Type.CompareTo(pOtherIns.Type);
        }
    }

    static void Solve()
    {
        long Answer = mFishInfoList.Max(pX => pX.W);

        // 網の左端にする魚を全探索
        for (int I = 0; I <= UB; I++) {
            var EventInfoList = new List<EventInfoDef>();
            for (int J = 0; J <= UB; J++) {
                if (I == J) continue;

                var ResultList = DeriveEventList1(I, J);
                if (ResultList.Count > 0) {
                    EventInfoList.AddRange(ResultList);
                    EventInfoList.AddRange(DeriveEventList2(I, J));
                }
            }
            EventInfoList.Sort();

            long SumW = mFishInfoList[I].W;
            foreach (EventInfoDef EachEventInfo in EventInfoList) {
                if (EachEventInfo.Type == 1) {
                    SumW += mFishInfoList[EachEventInfo.FishInd].W;
                    Answer = Math.Max(Answer, SumW);
                }
                else {
                    SumW -= mFishInfoList[EachEventInfo.FishInd].W;
                }
            }
        }
        Console.WriteLine(Answer);
    }

    // 左のFishのIndと、イベントのFishのIndを引数として、網に入るイベントのListを返す
    static List<EventInfoDef> DeriveEventList1(int pLeftInd, int pEventInd)
    {
        var WillReturn = new List<EventInfoDef>();

        FishInfoDef LeftFish = mFishInfoList[pLeftInd];
        FishInfoDef EventFish = mFishInfoList[pEventInd];

        EventInfoDef WillAdd;
        WillAdd.Type = 1;
        WillAdd.FishInd = pEventInd;

        // 最初から網に入ってる場合
        if (LeftFish.X <= EventFish.X && EventFish.X <= LeftFish.X + mA) {
            WillAdd.TimeBunshi = 0;
            WillAdd.TimeBunbo = 1;
            WillReturn.Add(WillAdd);
            return WillReturn;
        }

        // 速度が等しい場合
        if (LeftFish.V == EventFish.V) return WillReturn;

        long VDiff = Math.Abs(LeftFish.V - EventFish.V);

        // 位置関係で場合分け
        if (LeftFish.X < EventFish.X) {
            if (LeftFish.V <= EventFish.V) return WillReturn;

            long Distance = Math.Abs(LeftFish.X - EventFish.X);
            Distance -= mA;

            WillAdd.TimeBunshi = Distance;
            WillAdd.TimeBunbo = VDiff;
            WillReturn.Add(WillAdd);
            return WillReturn;
        }

        // 位置関係で場合分け
        if (EventFish.X < LeftFish.X) {
            if (EventFish.V <= LeftFish.V) return WillReturn;

            long Distance = Math.Abs(LeftFish.X - EventFish.X);
            WillAdd.TimeBunshi = Distance;
            WillAdd.TimeBunbo = VDiff;
            WillReturn.Add(WillAdd);
            return WillReturn;
        }

        return WillReturn;
    }

    // 左のFishのIndと、イベントのFishのIndを引数として、網から出るイベントのListを返す
    static List<EventInfoDef> DeriveEventList2(int pLeftInd, int pEventInd)
    {
        var WillReturn = new List<EventInfoDef>();

        FishInfoDef LeftFish = mFishInfoList[pLeftInd];
        FishInfoDef EventFish = mFishInfoList[pEventInd];

        // 速度が等しい場合
        if (LeftFish.V == EventFish.V) return WillReturn;

        long VDiff = Math.Abs(LeftFish.V - EventFish.V);

        EventInfoDef WillAdd;
        WillAdd.Type = 2;
        WillAdd.FishInd = pEventInd;

        // 位置関係で場合分け
        if (LeftFish.X <= EventFish.X) {

            // 速度の大小関係で場合分け
            if (LeftFish.V < EventFish.V) {
                long Distance = Math.Abs(LeftFish.X - EventFish.X);
                Distance = mA - Distance;
                WillAdd.TimeBunshi = Distance;
                WillAdd.TimeBunbo = VDiff;
                WillReturn.Add(WillAdd);
                return WillReturn;
            }

            if (LeftFish.V > EventFish.V) {
                long Distance = Math.Abs(LeftFish.X - EventFish.X);
                WillAdd.TimeBunshi = Distance;
                WillAdd.TimeBunbo = VDiff;
                WillReturn.Add(WillAdd);
                return WillReturn;
            }
        }

        if (LeftFish.X > EventFish.X) {
            // 速度の大小関係で場合分け
            if (LeftFish.V < EventFish.V) {
                long Distance = Math.Abs(LeftFish.X - EventFish.X);
                Distance += mA;
                WillAdd.TimeBunshi = Distance;
                WillAdd.TimeBunbo = VDiff;
                WillReturn.Add(WillAdd);
                return WillReturn;
            }
        }
        return WillReturn;
    }
}

解説

網の左端にする魚を全探索し、
他の魚が網に入るイベントと
網から出るイベントを構造体で定義してます。

次に、イベントの構造体のListをソートし、
Wの総和の最大値を求めてます。

定数倍高速化で、
LINQのOrderByメソッドではなく
ListクラスのSortメソッドを使ってます。