ABC224-E Integers on Grid

問題へのリンク

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 3 7");
            WillReturn.Add("1 1 4");
            WillReturn.Add("1 2 7");
            WillReturn.Add("2 1 3");
            WillReturn.Add("2 3 5");
            WillReturn.Add("3 1 2");
            WillReturn.Add("3 2 5");
            WillReturn.Add("3 3 5");
            //1
            //0
            //2
            //0
            //3
            //1
            //0
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5 7 20");
            WillReturn.Add("2 7 8");
            WillReturn.Add("2 6 4");
            WillReturn.Add("4 1 9");
            WillReturn.Add("1 5 4");
            WillReturn.Add("2 2 7");
            WillReturn.Add("5 5 2");
            WillReturn.Add("1 7 2");
            WillReturn.Add("4 6 6");
            WillReturn.Add("1 4 1");
            WillReturn.Add("2 1 10");
            WillReturn.Add("5 6 9");
            WillReturn.Add("5 3 3");
            WillReturn.Add("3 7 9");
            WillReturn.Add("3 6 3");
            WillReturn.Add("4 3 4");
            WillReturn.Add("3 3 10");
            WillReturn.Add("4 2 1");
            WillReturn.Add("3 5 4");
            WillReturn.Add("1 2 6");
            WillReturn.Add("4 7 9");
            //2
            //4
            //1
            //5
            //3
            //6
            //6
            //2
            //7
            //0
            //0
            //4
            //1
            //5
            //3
            //0
            //5
            //2
            //4
            //0
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    class RCAInfoDef
    {
        internal int ID;
        internal int R;
        internal int C;
        internal int A;
        internal int Answer;
    }

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

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

        var RCAInfoList = new List<RCAInfoDef>();
        int ID = 0;
        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            RCAInfoDef WillAdd = new RCAInfoDef();
            WillAdd.ID = ID++;
            WillAdd.R = wkArr[0];
            WillAdd.C = wkArr[1];
            WillAdd.A = wkArr[2];
            WillAdd.Answer = -1;
            RCAInfoList.Add(WillAdd);
        }

        // 横の最大移動数[Y座標] なDict
        var YokoMaxCntDict = new Dictionary<int, int>();

        // 縦の最大移動数[X座標] なDict
        var TateMaxCntDict = new Dictionary<int, int>();

        RCAInfoList = RCAInfoList.OrderByDescending(pX => pX.A).ToList();

        // 値がBreakするまで、更新を遅延させる必要あり
        var UpdateYokoDict = new Dictionary<int, int>();
        var UpdateTateDict = new Dictionary<int, int>();

        int UB = RCAInfoList.Count - 1;
        for (int I = 0; I <= UB; I++) {
            int CurrX = RCAInfoList[I].C;
            int CurrY = RCAInfoList[I].R;

            int YokoMax = 0;
            if (YokoMaxCntDict.ContainsKey(CurrY)) {
                YokoMax = 1 + YokoMaxCntDict[CurrY];
            }

            int TateMax = 0;
            if (TateMaxCntDict.ContainsKey(CurrX)) {
                TateMax = 1 + TateMaxCntDict[CurrX];
            }

            int Answer = Math.Max(YokoMax, TateMax);
            RCAInfoList[I].Answer = Answer;

            if (UpdateYokoDict.ContainsKey(CurrY) == false || UpdateYokoDict[CurrY] < Answer) {
                UpdateYokoDict[CurrY] = Answer;
            }
            if (UpdateTateDict.ContainsKey(CurrX) == false || UpdateTateDict[CurrX] < Answer) {
                UpdateTateDict[CurrX] = Answer;
            }

            // 値がBreakしたら更新
            if (I < UB && RCAInfoList[I].A != RCAInfoList[I + 1].A) {
                foreach (var EachPair in UpdateYokoDict) {
                    YokoMaxCntDict[EachPair.Key] = EachPair.Value;
                }
                foreach (var EachPair in UpdateTateDict) {
                    TateMaxCntDict[EachPair.Key] = EachPair.Value;
                }
                UpdateYokoDict.Clear();
                UpdateTateDict.Clear();
            }
        }

        foreach (RCAInfoDef EachRCAInfo in RCAInfoList.OrderBy(pX => pX.ID)) {
            Console.WriteLine(EachRCAInfo.Answer);
        }
    }
}

解説

□６□１４□２
10７□□□４８
□□10□４３９
９１４□□６９
□□３□２９□

という盤面で考えると、
値の降順に、
横の最大移動数[Y座標] なDictと
縦の最大移動数[X座標] なDictを
更新していけばいいと分かります。