ARC176-A 01 Matrix Again

問題へのリンク

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

    static long mN;
    static long mM;

    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]);
        mN = wkArr[0];
        mM = wkArr[1];

        var PosSet = new HashSet<long>();

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            long CurrY = wkArr[0];
            long CurrX = wkArr[1];

            long Hash = GetHash(CurrX, CurrY);
            PosSet.Add(Hash);
        }

        // ------------------------------------------------------------
        // 01 斜めのラインに追加
        // ------------------------------------------------------------
        foreach (long EachHash in PosSet.ToArray()) {
            long CurrX = EachHash / 1000000;
            long CurrY = EachHash % 1000000;

            for (long LoopCnt = 1; LoopCnt <= mN + 10; LoopCnt++) {
                if (++CurrX > mN) CurrX = 1;
                if (--CurrY < 1) CurrY = mN;
                long CurrHash = GetHash(CurrX, CurrY);
                if (PosSet.Add(CurrHash) == false) break;
            }
        }

        // ------------------------------------------------------------
        // 02 不足分を追加
        // ------------------------------------------------------------
        long RestCnt = mN * mM - PosSet.Count;
        for (long LoopX = 1; LoopX <= mN; LoopX++) {
            if (RestCnt == 0) break;

            long CurrX = LoopX;
            long CurrY = 1;
            long CurrHash = GetHash(CurrX, CurrY);

            if (PosSet.Contains(CurrHash) == false) {
                for (long LoopCnt = 1; LoopCnt <= mN + 10; LoopCnt++) {
                    if (++CurrX > mN) CurrX = 1;
                    if (--CurrY < 1) CurrY = mN;
                    CurrHash = GetHash(CurrX, CurrY);
                    if (PosSet.Add(CurrHash) == false) break;
                    RestCnt--;
                }
            }
        }

        // ------------------------------------------------------------
        // 03 解を出力
        // ------------------------------------------------------------
        var sb = new System.Text.StringBuilder();
        sb.Append(PosSet.Count);
        sb.AppendLine();
        foreach (long EachHash in PosSet) {
            long CurrX = EachHash / 1000000;
            long CurrY = EachHash % 1000000;
            sb.AppendFormat("{0} {1}", CurrY, CurrX);
            sb.AppendLine();
        }
        Console.Write(sb.ToString());
    }

    static long GetHash(long pX, long pY)
    {
        return pX * 1000000 + pY;
    }
}

解説

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

のように斜めライン1つで
全ての列と、全ての行の
●を1増やすことができます。

なので
初期配置の●の分の斜めラインを最初に引く。
それでも、●が不足してたら
任意の斜めラインに●を配置する。

というロジックで解けます。