川添さん問題08 プラス・マイナス・ゼロ

■■■問題■■■

自然数nに対して、次の等式を考えます。

    □1□2□3□4 ・・・ □n = 0

四角の部分には、プラス(+)またはマイナス(-)の記号が入ります。
等式を成立させるような記号の入れ方を考えましょう。

例えば、n=7のとき、次の8通りの入れ方が可能です。
●+1+2-3+4-5-6+7 = 0
●+1+2-3-4+5+6-7 = 0
●+1-2+3+4-5+6-7 = 0
●+1-2-3-4-5+6+7 = 0
●-1+2+3+4+5-6-7 = 0
●-1+2-3-4+5-6+7 = 0
●-1-2+3+4-5-6+7 = 0
●-1-2+3-4+5+6-7 = 0

自然数nに対し、等式を成立させる記号の入れ方の数をF(n)と定義します。

例えば F(7) = 8 です。
同様に、F(3) = 2、F(8) = 14 となることが確かめられます。

標準入力から、自然数n (1 <= n <= 50)が与えられます。
標準出力にF(n)の値を出力するプログラムを書いてください。

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    static string InputPattern = "Input1";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("3");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("7");
            //8
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("8");
            //14
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        //場合の数[和]なDP表
        var PrevDP = new Dictionary<long, long>();
        PrevDP[0] = 1;

        for (long I = 1; I <= n; I++) {
            var CurrDP = new Dictionary<long, long>();
            foreach (var EachPair in PrevDP) {

                Action<long> UpdateAct = pNewKey =>
                {
                    if (CurrDP.ContainsKey(pNewKey)) {
                        CurrDP[pNewKey] += EachPair.Value;
                    }
                    else CurrDP[pNewKey] = EachPair.Value;
                };

                UpdateAct(EachPair.Key + I);
                UpdateAct(EachPair.Key - I);
            }
            //PrintDP(CurrDP);
            PrevDP = CurrDP;
        }
        if (PrevDP.ContainsKey(0)) {
            Console.WriteLine(PrevDP[0]);
        }
        else Console.WriteLine(0);
    }

    static void PrintDP(Dictionary<long, long> pDP)
    {
        foreach (var EachPair in pDP) {
            Console.WriteLine("和が{0}になるのは{1}通り",
                EachPair.Key, EachPair.Value);
        }
    }
}

解説

動的計画法で解いてます。

「プラス・マイナス・ゼロ」問題解説 --- CodeIQ MAGAZINE