ABC099-D Good 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("2 3");
            WillReturn.Add("0 1 1");
            WillReturn.Add("1 0 1");
            WillReturn.Add("1 4 0");
            WillReturn.Add("1 2");
            WillReturn.Add("3 3");
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4 3");
            WillReturn.Add("0 12 71");
            WillReturn.Add("81 0 53");
            WillReturn.Add("14 92 0");
            WillReturn.Add("1 1 2 1");
            WillReturn.Add("2 1 1 2");
            WillReturn.Add("2 2 1 3");
            WillReturn.Add("1 1 2 2");
            //428
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static int mN;
    static int mC;

    // 違和感の二次元配列
    static int[,] mDArr;

    // 盤面の二次元配列
    static int UB;
    static int[,] mBanArr;

    // 件数[ (X座標+Y座標) % 3 , 色]な二次元配列
    static int[,] mColorCntArr;

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

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

        SplitAct(InputList[0]);
        mN = wkArr[0];
        mC = wkArr[1];

        // 違和感の二次元配列
        mDArr = new int[mC, mC];
        for (int Y = 0; Y <= mC - 1; Y++) {
            SplitAct(InputList[1 + Y]);
            for (int X = 0; X <= mC - 1; X++) {
                mDArr[X, Y] = wkArr[X];
            }
        }

        // 盤面の二次元配列
        UB = mN - 1;
        mBanArr = new int[UB + 1, UB + 1];
        for (int Y = 0; Y <= UB; Y++) {
            SplitAct(InputList[1 + mC + Y]);
            for (int X = 0; X <= UB; X++) {
                mBanArr[X, Y] = wkArr[X];
            }
        }

        // 件数[ (X座標+Y座標) % 3 , 色]な二次元配列
        mColorCntArr = new int[3, mC];
        for (int Y = 0; Y <= UB; Y++) {
            for (int X = 0; X <= UB; X++) {
                // 色は0オリジンとする
                mColorCntArr[(X + Y) % 3, mBanArr[X, Y] - 1]++;
            }
        }

        // 全部の色の組み合わせを試す
        long Answer = long.MaxValue;
        for (int I = 0; I <= mC - 1; I++) {
            for (int J = 0; J <= mC - 1; J++) {
                if (J == I) continue;
                for (int K = 0; K <= mC - 1; K++) {
                    if (K == I) continue;
                    if (K == J) continue;
                    long AnswerKouho = DeriveAnswerKouho(I, J, K);
                    Answer = Math.Min(Answer, AnswerKouho);
                }
            }
        }
        Console.WriteLine(Answer);
    }

    // modごとに使う3つの色を引数として、違和感の合計を返す
    static long DeriveAnswerKouho(int pColor0, int pColor1, int pColor2)
    {
        long AnswerKouho = 0;
        for (int I = 0; I <= mColorCntArr.GetUpperBound(0); I++) {
            int AfterColor = -1;
            if (I == 0) AfterColor = pColor0;
            if (I == 1) AfterColor = pColor1;
            if (I == 2) AfterColor = pColor2;

            for (int J = 0; J <= mColorCntArr.GetUpperBound(1); J++) {
                int BeforeColor = J;
                int BeforeColorCnt = mColorCntArr[I, J];
                //int AddVal = mDArr[BeforeColor, AfterColor] * BeforeColorCnt;
                int AddVal = mDArr[AfterColor, BeforeColor] * BeforeColorCnt;

                AnswerKouho += AddVal;
            }
        }
        //Console.WriteLine("pColor0={0},pColor1={1},pColor2={2}の場合は{3}", 
        //    pColor0, pColor1, pColor2, AnswerKouho);

        return AnswerKouho;
    }

    // 2次元配列のデバッグ出力
    static void PrintBan(int[,] pBanArr)
    {
        for (int Y = 0; Y <= pBanArr.GetUpperBound(1); Y++) {
            for (int X = 0; X <= pBanArr.GetUpperBound(0); X++) {
                Console.Write(pBanArr[X, Y]);
            }
            Console.WriteLine();
        }
    }
}

解説

前処理として、(X座標 + Y座標) % 3 ごとの色数を集計しておいてから、
30色から3つ選ぶ順列を全部試してます。