ABC-011-C 123引き算

■■■問題■■■

あなたは、友人から、一人用のゲームを紹介されました。
最初に、数字Nが与えられます。
1,2,3の中から好きな数字を選び、与えられた数字に対し、引き算を行う、
という処理を行うことできます。

この処理は100回まで行うことが可能であり、
最終的に数字を0にすることが目標のゲームです。

しかし、計算途中でなってはいけないNG数字が3つ与えられており、
この数字に一時的にでもなってしまった瞬間、このゲームは失敗となります。
NG数字がNと同じ場合も失敗となります。

あなたは、このゲームが、目標達成可能なゲームとなっているか調べたいです。
目標達成可能な場合は'YES'、そうでない場合は'NO'と出力してください。

■■■入力■■■

N
NG1
NG2
NG3

●1行目には、最初に与えられる数字 N(1 <= N <= 300) が与えられる。
●2行目には、1番目のNG数字 NG1(1 <= NG1 <= 300) が与えられる。
●3行目には、2番目のNG数字 NG2(1 <= NG2 <= 300) が与えられる。
●4行目には、3番目のNG数字 NG3(1 <= NG3 <= 300) が与えられる。

■■■出力■■■

目標達成可能な場合は'YES'、そうでない場合は'NO'を1行で出力せよ。
出力の末尾にも改行をいれること。

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "Input1";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("2");
            WillReturn.Add("1");
            WillReturn.Add("7");
            WillReturn.Add("15");
            //YES
            //2を1回引くことにより、0を作ることが出来ます
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5");
            WillReturn.Add("1");
            WillReturn.Add("4");
            WillReturn.Add("2");
            //YES
            //最初に2を引き、次に3を引くことで、5 → 3 → 0 と変化し、
            //目標を達成することが出来ます。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("300");
            WillReturn.Add("57");
            WillReturn.Add("121");
            WillReturn.Add("244");
            //NO
            //100回連続で3を引かなければ、目標を達成することはできません。
            //しかし、3だけを引き続けていると、
            //途中でNG数字である57になってしまいます。
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int N = int.Parse(InputList[0]);
        int[] NGArr = new int[3];
        NGArr[0] = int.Parse(InputList[1]);
        NGArr[1] = int.Parse(InputList[2]);
        NGArr[2] = int.Parse(InputList[3]);

        if (NGArr.Contains(N)) {
            Console.WriteLine("NO");
            return;
        }

        //到達可能な数値
        var PrevDP = new HashSet<int>();
        PrevDP.Add(N);

        for (int I = 1; I <= 100; I++) {
            var CurrDP = new HashSet<int>();

            foreach (int EachInt in PrevDP) {
                Action<int> AddAct = pNewVal =>
                {
                    if (NGArr.Contains(pNewVal))
                        return;

                    if (pNewVal < 0) return;

                    CurrDP.Add(pNewVal);
                };

                AddAct(EachInt - 1);
                AddAct(EachInt - 2);
                AddAct(EachInt - 3);
            }
            if (CurrDP.Contains(0)) {
                Console.WriteLine("YES");
                return;
            }
            PrevDP = CurrDP;
        }
        Console.WriteLine("NO");
    }
}

解説

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