AOJ 0556 タイル

問題へのリンク

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

    static long mN;

    struct RectDef
    {
        internal long StaX;
        internal long EndX;
        internal long StaY;
        internal long EndY;
        internal long Color;
    }

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

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

        foreach (string EachStr in InputList.Skip(2)) {
            SplitAct(EachStr);
            long PosX = wkArr[0];
            long PosY = wkArr[1];

            long Result = DeriveColor(PosX, PosY);
            Console.WriteLine(Result);
        }
    }

    // 座標を引数として、色を返す
    static long DeriveColor(long pPosX, long pPosY)
    {
        long L = 1;
        long R = mN;

        Predicate<RectDef> IsInside = (pRect) =>
        {
            bool CheckX = (pRect.StaX <= pPosX && pPosX <= pRect.EndX);
            bool CheckY = (pRect.StaY <= pPosY && pPosY <= pRect.EndY);
            return CheckX && CheckY;
        };

        if (IsInside(GetRectInfo(R))) {
            return GetRectInfo(R).Color;
        }

        while (L + 1 < R) {
            long Mid = (L + R) / 2;

            if (IsInside(GetRectInfo(Mid))) {
                L = Mid;
            }
            else {
                R = Mid;
            }
        }
        return GetRectInfo(L).Color;
    }

    // 正方形番号を引数として、正方形の外周の情報を返す
    static RectDef GetRectInfo(long pNo)
    {
        RectDef WillReturn;
        WillReturn.StaX = pNo;
        WillReturn.EndX = mN - pNo + 1;
        WillReturn.StaY = pNo;
        WillReturn.EndY = mN - pNo + 1;
        WillReturn.Color = (pNo - 1) % 3 + 1;
        return WillReturn;
    }
}

解説

正方形の番目が決まれば、
正方形の左上と右下と色は、決まります。

なので、内包できる正方形の番目の上限を二分探索して解けます。