ABC298-F Rook Score

問題へのリンク

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("4");
            WillReturn.Add("1 1 2");
            WillReturn.Add("1 2 9");
            WillReturn.Add("2 1 8");
            WillReturn.Add("3 2 3");
            //20
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("1");
            WillReturn.Add("1 1000000000 1");
            //1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("15");
            WillReturn.Add("158260522 877914575 602436426");
            WillReturn.Add("24979445 861648772 623690081");
            WillReturn.Add("433933447 476190629 262703497");
            WillReturn.Add("211047202 971407775 628894325");
            WillReturn.Add("731963982 822804784 450968417");
            WillReturn.Add("430302156 982631932 161735902");
            WillReturn.Add("880895728 923078537 707723857");
            WillReturn.Add("189330739 910286918 802329211");
            WillReturn.Add("404539679 303238506 317063340");
            WillReturn.Add("492686568 773361868 125660016");
            WillReturn.Add("650287940 839296263 462224593");
            WillReturn.Add("492601449 384836991 191890310");
            WillReturn.Add("576823355 782177068 404011431");
            WillReturn.Add("818008580 954291757 160449218");
            WillReturn.Add("155374934 840594328 164163676");
            //1510053068
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

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

        // 縦合計[X座標]
        var TateSumDict = new Dictionary<long, long>();

        // 横合計[Y座標]
        var YokoSumDict = new Dictionary<long, long>();

        // 値[座標のハッシュ値]
        var ValDict = new Dictionary<string, long>();

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);

            long Y = wkArr[0];
            long X = wkArr[1];
            long Val = wkArr[2];

            if (TateSumDict.ContainsKey(X) == false) {
                TateSumDict[X] = 0;
            }
            if (YokoSumDict.ContainsKey(Y) == false) {
                YokoSumDict[Y] = 0;
            }
            TateSumDict[X] += Val;
            YokoSumDict[Y] += Val;

            string Hash = GetHash(X, Y);
            ValDict[Hash] = Val;
        }

        var AnswerList = new List<long>();

        // 場合1 数値のあるマス
        foreach (var EachPair in ValDict) {
            long CurrX, CurrY;
            GetXY(out CurrX, out CurrY, EachPair.Key);
            long CurrSum = 0;
            CurrSum += TateSumDict[CurrX];
            CurrSum += YokoSumDict[CurrY];
            CurrSum -= EachPair.Value;
            AnswerList.Add(CurrSum);
        }

        // 場合2 数値のないマス
        var YokoSumDictSorted = new Dictionary<long, long>();
        foreach (var EachPair in YokoSumDict.OrderByDescending(pX => pX.Value)) {
            YokoSumDictSorted[EachPair.Key] = EachPair.Value;
        }

        foreach (var EachPair1 in TateSumDict) {
            foreach (var EachPair2 in YokoSumDictSorted) {
                long CurrX = EachPair1.Key;
                long CurrY = EachPair2.Key;

                string Hash = GetHash(CurrX, CurrY);
                if (ValDict.ContainsKey(Hash)) {
                    continue;
                }
                AnswerList.Add(EachPair1.Value + EachPair2.Value);
                break;
            }
        }
        Console.WriteLine(AnswerList.Max());
    }

    // ハッシュ値を返す
    static string GetHash(long pX, long pY)
    {
        return string.Format("{0},{1}", pX, pY);
    }

    // ハッシュ値から、X座標とY座標を返す
    static void GetXY(out long pX, out long pY, string pHash)
    {
        string[] SplitArr = pHash.Split(',');
        pX = long.Parse(SplitArr[0]);
        pY = long.Parse(SplitArr[1]);
    }
}

解説

場合に分けて考えます。

数値マスを解とする場合は、
縦合計[X座標]
横合計[Y座標]
を事前計算で求めておけば、
高速に縦計と横計を求めることができます。

数値マスを解としない場合は、
少なくとも1つは、数値があるX座標を全探索し、
数値があるY座標を、横合計の降順に見ていき、
数値が無いマスを解候補とし、Breakするようにします。

これで、2つの場合で解候補を列挙することができます。