ABC176-E Bomber

問題へのリンク

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

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

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

        // Y座標のSet[X座標]なDict
        var YSetDict = new Dictionary<int, HashSet<int>>();

        // 横合計[Y座標]なDict
        var YokokeiDict = new Dictionary<int, int>();

        // 縦合計[X座標]なDict
        var TatekeiDict = new Dictionary<int, int>();

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

            int PosY = wkArr[0];
            int PosX = wkArr[1];

            if (YSetDict.ContainsKey(PosX) == false) {
                YSetDict[PosX] = new HashSet<int>();
            }
            YSetDict[PosX].Add(PosY);

            if (TatekeiDict.ContainsKey(PosX) == false) {
                TatekeiDict[PosX] = 0;
            }
            TatekeiDict[PosX]++;

            if (YokokeiDict.ContainsKey(PosY) == false) {
                YokokeiDict[PosY] = 0;
            }
            YokokeiDict[PosY]++;
        }

        int TatekeiMax = TatekeiDict.Values.Max();
        int YokokeiMax = YokokeiDict.Values.Max();

        var TatekeiMaxSet = new HashSet<int>();
        foreach (var EachPair in TatekeiDict) {
            if (EachPair.Value == TatekeiMax) {
                TatekeiMaxSet.Add(EachPair.Key);
            }
        }

        var YokokeiMaxSet = new HashSet<int>();
        foreach (var EachPair in YokokeiDict) {
            if (EachPair.Value == YokokeiMax) {
                YokokeiMaxSet.Add(EachPair.Key);
            }
        }

        int Answer = int.MinValue;
        foreach (int EachX in TatekeiMaxSet) {
            if (YokokeiMaxSet.IsSubsetOf(YSetDict[EachX])) {
                Answer = Math.Max(Answer, TatekeiMax + YokokeiMax - 1);
            }
            else {
                Answer = Math.Max(Answer, TatekeiMax + YokokeiMax);
                break;
            }
        }
        Console.WriteLine(Answer);
    }
}

解説

オセロセットを使って下記のサンプルで考察します。

□□□●□
□●●□●
□□□□●
□□●□□
●□●●●

爆破数を最大にする必要条件は、
横計が最大の行、かつ、縦計が最大の列
になります。

爆破数が最大の座標が、横計が最大の行でない場合は、矛盾するし
爆破数が最大の座標が、縦計が最大の列でない場合も、矛盾するからです。

必要条件で絞れたので、
横計が最大の行と縦計が最大の列の組み合わせ、ダブルカウントしてるかの判定を
HashSetのIsSubsetOfメソッドで高速に判定してます。