AOJ 0574 釘

問題へのリンク

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("5 2");
            WillReturn.Add("2 2 1");
            WillReturn.Add("2 1 3");
            //12
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static int[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => int.Parse(pX)).ToArray();
    }

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

        int[] wkArr = { };
        Action<string> SplitAct = (pStr) => wkArr = GetSplitArr(pStr);

        SplitAct(InputList[0]);
        int N = wkArr[0];

        // 値[Y座標][X座標]なジャグ配列
        var DictDict = new Dictionary<int, Dictionary<int, int>>();
        for (int Y = 1; Y <= N; Y++) {
            DictDict[Y] = new Dictionary<int, int>();
            for (int X = 1; X <= Y; X++) {
                DictDict[Y][X] = 0;
            }
        }

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            int A = wkArr[0];
            int B = wkArr[1];
            int X = wkArr[2];
            DictDict[A][B] = X + 1;
        }

        int Answer = 0;
        for (int Y = 1; Y <= N; Y++) {
            for (int X = 1; X <= Y; X++) {

                Action<int, int, int> SendAct = (pTargetY, pTargetX, pSendVal) =>
                {
                    if (DictDict.ContainsKey(pTargetY) == false) return;
                    if (DictDict[pTargetY].ContainsKey(pTargetX) == false) return;

                    int CurrVal = DictDict[pTargetY][pTargetX];
                    DictDict[pTargetY][pTargetX] = Math.Max(CurrVal, pSendVal);
                };

                // 左下と右下に配る
                if (DictDict[Y][X] >= 1) {
                    SendAct(Y + 1, X + 0, DictDict[Y][X] - 1);
                    SendAct(Y + 1, X + 1, DictDict[Y][X] - 1);
                }

                if (DictDict[Y][X] > 0) Answer++;
            }
        }

        Console.WriteLine(Answer);
    }
}

解説

パスカルの三角形を意識しつつ、
左下と右下に配るDPをしてます。