ARC149-C Avoid Prime Sum

問題へのリンク

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");
            //15 11 16 12
            //13 3 6 9
            //14 7 8 1
            //4 2 10 5
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static int mN;
    static int UB;

    static int[] mSosuuArr;


    static void Main()
    {
        List<string> InputList = GetInputList();
        mN = int.Parse(InputList[0]);
        UB = mN - 1;

        Eratosthenes(mN * mN * 2);

        var OddList = new List<int>();
        var EvenList = new List<int>();
        for (int I = 1; I <= mN * mN; I++) {
            if (I % 2 == 0) EvenList.Add(I);
            if (I % 2 == 1) OddList.Add(I);
        }
        OddList = OddList.OrderBy(pX => pX % 3 > 0 ? 0 : 1).ToList();
        EvenList = EvenList.OrderBy(pX => pX % 3 > 0 ? 1 : 0).ToList();

        var ValList = new List<int>();
        ValList.AddRange(OddList);
        ValList.AddRange(EvenList);

        int[,] BanArr = new int[UB + 1, UB + 1];
        int CurrInd = 0;
        for (int LoopX = 0; LoopX <= UB; LoopX++) {
            for (int LoopY = 0; LoopY <= UB; LoopY++) {
                BanArr[LoopX, LoopY] = ValList[CurrInd++];
            }
        }
        if (IsOKBan(BanArr)) {
            PrintBan(BanArr);
            return;
        }

        SolveDFS();
    }

    // OKな盤面かを判定する
    static bool IsOKBan(int[,] pBanArr)
    {
        for (int LoopX = 0; LoopX <= UB; LoopX++) {
            for (int LoopY = 0; LoopY <= UB; LoopY++) {
                int AddX = LoopX + 1;
                int AddY = LoopY + 1;
                if (AddX <= UB) {
                    int SumVal = pBanArr[LoopX, LoopY] + pBanArr[AddX, LoopY];
                    if (Array.BinarySearch(mSosuuArr, SumVal) >= 0) {
                        return false;
                    }
                }
                if (AddY <= UB) {
                    int SumVal = pBanArr[LoopX, LoopY] + pBanArr[LoopX, AddY];
                    if (Array.BinarySearch(mSosuuArr, SumVal) >= 0) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    static void SolveDFS()
    {
        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CurrX = 0;
        WillPush.CurrY = 0;
        WillPush.BanArr = new int[UB + 1, UB + 1];
        Stk.Push(WillPush);

        while (Stk.Count > 0) {
            JyoutaiDef Popped = Stk.Pop();

            if (Popped.CurrX > UB) {
                Popped.CurrX = 0;
                Popped.CurrY++;
            }
            if (Popped.CurrY > UB) {
                if (IsOKBan(Popped.BanArr)) {
                    PrintBan(Popped.BanArr);
                    return;
                }
                continue;
            }
            var ValList = Popped.BanArr.Cast<int>().ToList();
            for (int I = 1; I <= mN * mN; I++) {
                if (ValList.Contains(I)) continue;

                WillPush.CurrX = Popped.CurrX + 1;
                WillPush.CurrY = Popped.CurrY;
                WillPush.BanArr = (int[,])Popped.BanArr.Clone();
                WillPush.BanArr[Popped.CurrX, Popped.CurrY] = I;

                int MinusX = Popped.CurrX - 1;
                int MinusY = Popped.CurrY - 1;
                if (0 <= MinusX) {
                    int SumVal = WillPush.BanArr[Popped.CurrX, Popped.CurrY]
                               + WillPush.BanArr[MinusX, Popped.CurrY];
                    if (Array.BinarySearch(mSosuuArr, SumVal) >= 0) {
                        continue;
                    }
                }
                if (0 <= MinusY) {
                    int SumVal = WillPush.BanArr[Popped.CurrX, Popped.CurrY]
                               + WillPush.BanArr[Popped.CurrX, MinusY];
                    if (Array.BinarySearch(mSosuuArr, SumVal) >= 0) {
                        continue;
                    }
                }
                Stk.Push(WillPush);
            }
        }
    }

    struct JyoutaiDef
    {
        internal int CurrX;
        internal int CurrY;
        internal int[,] BanArr;
    }

    // エラトステネスの篩
    static void Eratosthenes(int pJyougen)
    {
        bool[] IsSosuuArr = new bool[pJyougen + 1];
        for (int I = 2; I <= IsSosuuArr.GetUpperBound(0); I++) {
            IsSosuuArr[I] = true;
        }
        for (int I = 2; I * I <= IsSosuuArr.GetUpperBound(0); I++) {
            if (IsSosuuArr[I]) {
                for (int J = I * 2; J <= IsSosuuArr.GetUpperBound(0); J += I) {
                    IsSosuuArr[J] = false;
                }
            }
        }

        var SosuuList = new List<int>();
        for (int I = 2; I <= IsSosuuArr.GetUpperBound(0); I++) {
            if (IsSosuuArr[I]) SosuuList.Add(I);
        }

        mSosuuArr = SosuuList.ToArray();
    }

    ////////////////////////////////////////////////////////////////
    // 2次元配列(int型)のデバッグ出力
    ////////////////////////////////////////////////////////////////
    static void PrintBan(int[,] pBanArr)
    {
        var sb = new System.Text.StringBuilder();
        for (int Y = 0; Y <= UB; Y++) {
            for (int X = 0; X <= UB; X++) {
                sb.Append(pBanArr[X, Y]);
                if (X < UB) sb.Append(" ");
            }
            sb.AppendLine();
        }
        Console.Write(sb.ToString());
    }
}

解説

この問題の制約であれば、
奇数 + 奇数 は 合成数
偶数 + 偶数 は 合成数
になります。

なので、奇数の塊と、偶数の塊で配置するようにします。

3の倍数を考えると、奇数と偶数の両方にもあって、和も合成数なので
奇数の塊と偶数の塊の隣接は、なるべく3の倍数同士で隣接させる配置を試し、

この配置でNGなら、今度は、DFSで配置してます。