ABC346-E Paint

問題へのリンク

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

    struct QueryInfoDef
    {
        internal long Type;
        internal long Target;
        internal long Color;
    }
    static List<QueryInfoDef> mQueryInfoList = new List<QueryInfoDef>();

    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]);
        long Height = wkArr[0];
        long Width = wkArr[1];

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            QueryInfoDef WillAdd;
            WillAdd.Type = wkArr[0];
            WillAdd.Target = wkArr[1];
            WillAdd.Color = wkArr[2];
            mQueryInfoList.Add(WillAdd);
        }
        mQueryInfoList.Reverse();

        // 塗った行
        var PaintRowSet = new HashSet<long>();

        // 塗った列
        var PaintColumnSet = new HashSet<long>();

        // 塗ったマス数[色]なDict
        var CntDict = new Dictionary<long, long>();
        foreach (long EachColor in mQueryInfoList.Select(pX => pX.Color).Distinct()) {
            CntDict[EachColor] = 0;
        }

        foreach (QueryInfoDef EachQuery in mQueryInfoList) {
            long Type = EachQuery.Type;
            long Target = EachQuery.Target;
            long Color = EachQuery.Color;

            if (Type == 1) { // 1は行塗り
                if (PaintRowSet.Contains(Target)) {
                    continue;
                }
                PaintRowSet.Add(Target);
                CntDict[Color] += Width - PaintColumnSet.Count;
            }
            if (Type == 2) { // 2は列塗り
                if (PaintColumnSet.Contains(Target)) {
                    continue;
                }
                PaintColumnSet.Add(Target);
                CntDict[Color] += Height - PaintRowSet.Count;
            }
        }

        long ZeroCnt = Width * Height;
        foreach (var EachPair in CntDict) {
            if (EachPair.Key != 0) {
                ZeroCnt -= EachPair.Value;
            }
        }
        CntDict[0] = ZeroCnt;

        var sb = new System.Text.StringBuilder();

        long ColorCnt = 0;
        foreach (var EachPair in CntDict) {
            if (EachPair.Value > 0) ColorCnt++;
        }
        sb.AppendLine(ColorCnt.ToString());

        foreach (var EachPair in CntDict.OrderBy(pX => pX.Key)) {
            if (EachPair.Value > 0) {
                sb.AppendFormat("{0} {1}", EachPair.Key, EachPair.Value);
                sb.AppendLine();
            }
        }
        Console.Write(sb.ToString());
    }
}

解説

ダイソーの蛍光ペン使ってシュミレーションすると、
色を上書きして塗る操作なので、
逆順に処理すれば良いと分かります。