AOJ 0732 いちご 2

問題へのリンク

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

    struct PosDef
    {
        internal long X;
        internal long Y;
    }
    static List<PosDef> mPosList = new List<PosDef>();

    static Dictionary<decimal, long> mCntDict = new Dictionary<decimal, long>();

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

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

        foreach (string EachStr in InputList.Skip(2)) {
            SplitAct(EachStr);
            PosDef WillAdd;
            WillAdd.X = wkArr[0];
            WillAdd.Y = wkArr[1];
            mPosList.Add(WillAdd);
        }

        foreach (PosDef EachPos in mPosList) {
            decimal Hash = GetHash(EachPos.X, EachPos.Y);
            if (mCntDict.ContainsKey(Hash) == false) {
                mCntDict[Hash] = 0;
            }
            mCntDict[Hash]++;
        }

        var AnswerList = new List<long>();
        foreach (PosDef EachPos in mPosList) {
            long CurrX = EachPos.X;
            long CurrY = EachPos.Y;
            long Cnt1 = GetCnt(CurrX, CurrY, 1, 2);
            long Cnt2 = GetCnt(CurrX, CurrY, -1, -2);
            long Cnt3 = GetCnt(CurrX, CurrY, -1, +1);
            AnswerList.Add(Cnt1);
            AnswerList.Add(Cnt2);
            AnswerList.Add(Cnt3);
        }
        Console.WriteLine(AnswerList.Max());
    }

    // 開始座標と、X座標の変位ベクトル2つを引数として、いちごの数を返す
    static long GetCnt(long pStaX, long pStaY, long pXVect1, long pXVect2)
    {
        long Cnt = 0;

        var XList = new List<long>();
        XList.Add(pStaX);
        XList.Add(pStaX + pXVect1);
        XList.Add(pStaX + pXVect2);
        for (long LoopY = pStaY; LoopY <= pStaY + 2; LoopY++) {
            foreach (long EachX in XList) {
                decimal Hash = GetHash(EachX, LoopY);
                if (mCntDict.ContainsKey(Hash)) {
                    Cnt += mCntDict[Hash];
                }
            }
        }
        return Cnt;
    }

    static decimal GetHash(long pX, long pY)
    {
        decimal Hash = 0;
        Hash += pX * 10000000000M;
        Hash += pY;
        return Hash;
    }
}

解説

Z方向にループして見ていくので
1個目の苺は
下記の3通りのいずれかで
取るのが最適です。

苺□□
□□□
□□□

□苺□
□□□
□□□

□□苺
□□□
□□□

後は、残りの苺が取れるかをHashSetで高速に判断すれば良いです。