アリ本-999 くじびき

■■■問題■■■

あなたの友人は次のようなゲームをあなたに仕掛けてきました。
数字が書かれたN枚の紙切れが袋に入っています。
あなたはこの袋から紙切れを取り出し、数字と見て袋に戻すということを4回行い、
4回の紙切れの数字の和がmになってればあなたの勝ち、そうでなければ友人の勝ちとなります。

あなたはこのゲームに何度か挑戦しましたが、一度も勝つことができませんでした。
怒ったあなたは袋を破り、全ての紙切れを取り出して本当に勝つ可能性があるのかを調べることにしました。

紙切れに書かれている数字がK1,K2...Knであったとき、和がmになる可能性が存在するかどうかを計算し、
存在するならYes、存在しないならNoと出力するプログラムを作成してください。

■■■制約■■■

1 <= n  <= 50
1 <= m  <= 1億
1 <= Ki <= 1億

C#のソース

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

class Program
{
    static string InputPattern = "Input1";

    //入力値の設定
    static void GetInputValues(out int pM, out int[] pK)
    {
        if (InputPattern == "Input1") {
            pM = 10; pK = new int[] { 1, 3, 5 };
            return;
            //Yes(例えば1,1,3,5のように出れば、和が10になります)
        }
        else if (InputPattern == "Input2") {
            pM = 9; pK = new int[] { 1, 3, 5 };
            return;
            //No(和が9になるような出力は存在しません)
        }
        else { //最悪計算量
            pM = 100000000;
            pK = Enumerable.Range(1, 50).ToArray();
            pK[0] = pK[10] = pK[20] = pK[30] = 100000000 / 4;
        }
    }

    struct JyoutaiDef
    {
        internal int SumVal;
        internal string ExtractLog;
        internal int CurrentP;
        internal int Level;
    }

    static void Main()
    {
        //入力値の設定
        int m; int[] K;
        GetInputValues(out m, out K);

        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;

        WillPush.SumVal = 0;
        WillPush.ExtractLog = "";
        WillPush.CurrentP = 0;
        WillPush.Level = 0;
        stk.Push(WillPush);

        while (stk.Count > 0) {
            JyoutaiDef Popped = stk.Pop();

            if (Popped.Level == 4) {
                if (Popped.SumVal == m) {
                    Console.WriteLine("Yes(例えば{0}のように出れば、和が{1}になります)",
                        Popped.ExtractLog, m);
                    return;
                }
                continue;
            }

            for (int I = Popped.CurrentP; I <= K.GetUpperBound(0); I++) {
                WillPush.SumVal = Popped.SumVal + K[I];
                if (WillPush.SumVal > m) continue;
                WillPush.ExtractLog = Popped.ExtractLog;
                WillPush.ExtractLog += (Popped.Level == 0 ? "" : ",") + K[I].ToString();
                WillPush.CurrentP = I;
                WillPush.Level = Popped.Level + 1;
                stk.Push(WillPush);
            }
        }
        Console.WriteLine("No(和が{0}になるような出力は存在しません)", m);
    }
}

実行結果

Yes(例えば1,3,3,3のように出れば、和が10になります)

解説

Stackクラスを使って深さ優先探索してます。