No.115 遠足のおやつ

■■■問題■■■

直樹くんは遠足のおやつを買いに駄菓子屋さんに来ました。
駄菓子屋さんは 1,2,3 ・・・ N円 の N種類の御菓子を売っています。

直樹くんが買える御菓子は合計でD円までで、買える個数はK個までです。
いっぱい御菓子が食べたい直樹くんは次のルールを追加しました。

●お金があまったらもったいないので、合計がD円ぴったりになるように御菓子を買う
●いっぱい食べたいのでK個御菓子を買う
●種類もいっぱい食べたいので、ある金額の御菓子は買うなら1個までにする

このルールを満たすような御菓子の買い方で辞書順最小になるものを答えてください。
もしそのような御菓子の買い方がないなら-1を出力してください。

辞書順最小についてはサンプルを参照してください。

■■■入力■■■

N D K

入力はすべて整数で与えられる

1 <= N <=  100
1 <= D <= 1000
1 <= K <=   10

■■■出力■■■

ルールを満たすような御菓子の買い方で辞書順最小になるものを半角空白区切りで1行に出力してください。
ただしそのような御菓子の買い方がない場合は-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("10 9 3");
            //1 2 6
            //ルールを満たす御菓子の組み合わせは
            //(1円,2円,6円)
            //(1円,3円,5円)
            //(2円,3円,4円)
            //の3つがありますが、
            //このうち辞書順が最小になる(1円,2円,6円)の組み合わせが答えになります。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10 9 4");
            //-1
            //残念ながら直樹くんは御菓子を買うことができませんでした・・・
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("30 40 4");
            //1 2 7 30
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] wkArr = InputList[0].Split(' ').Select(X => int.Parse(X)).ToArray();
        int N = wkArr[0];
        int D = wkArr[1];
        int K = wkArr[2];

        //辞書式最小パス[御菓子の数,金額合計]なDP表
        string[,] CurrDP = new string[K + 1, D + 1];
        string[,] PrevDP = new string[K + 1, D + 1];
        PrevDP[0, 0] = ""; //初期化

        Array.Copy(PrevDP, CurrDP, PrevDP.Length);
        for (int LoopN = 1; LoopN <= N; LoopN++) {
            for (int LoopK = 0; LoopK <= K - 1; LoopK++) {
                for (int LoopD = 0; LoopD <= D; LoopD++) {
                    if (PrevDP[LoopK, LoopD] == null) continue;
                    int NewIndK = LoopK + 1;
                    int NewIndD = LoopD + LoopN;
                    if (NewIndD > D) continue;
                    string NewPath = PrevDP[LoopK, LoopD]
                        + " " + LoopN.ToString().PadLeft(3, '0');

                    if (CurrDP[NewIndK, NewIndD] == null
                     || CurrDP[NewIndK, NewIndD].CompareTo(NewPath) > 0) {
                        CurrDP[NewIndK, NewIndD] = NewPath;
                    }
                }
            }
            Console.WriteLine(new string('■', 15));
            Console.WriteLine("{0}円の御菓子までのDPの結果", LoopN);
            PrintDP(CurrDP);

            Array.Copy(CurrDP, PrevDP, CurrDP.Length);
        }

        if (CurrDP[K, D] != null) {
            int[] AnswerIntArr = CurrDP[K, D].Trim().Split(' ').
                Select(X => int.Parse(X)).ToArray();
            string[] AnswerStrArr = Array.ConvertAll(AnswerIntArr, X => X.ToString());
            Console.WriteLine(string.Join(" ", AnswerStrArr));
        }
        else Console.WriteLine(-1);
    }

    static void PrintDP(string[,] pCurrDP)
    {
        var sb = new System.Text.StringBuilder();
        for (int LoopK = 0; LoopK <= pCurrDP.GetUpperBound(0); LoopK++) {
            for (int LoopD = 0; LoopD <= pCurrDP.GetUpperBound(1); LoopD++) {
                if (pCurrDP[LoopK, LoopD] == null) continue;
                sb.AppendFormat("{0}個で{1}円の辞書順最小パスは{2}",
                    LoopK, LoopD, pCurrDP[LoopK, LoopD]);
                sb.AppendLine();
            }
        }
        Console.WriteLine(sb.ToString());
    }
}

デバッグ情報付の実行結果

省略
■■■■■■■■■■■■■■■
10円の御菓子までのDPの結果
0個で0円の辞書順最小パスは
1個で1円の辞書順最小パスは 001
1個で2円の辞書順最小パスは 002
1個で3円の辞書順最小パスは 003
1個で4円の辞書順最小パスは 004
1個で5円の辞書順最小パスは 005
1個で6円の辞書順最小パスは 006
1個で7円の辞書順最小パスは 007
1個で8円の辞書順最小パスは 008
1個で9円の辞書順最小パスは 009
2個で3円の辞書順最小パスは 001 002
2個で4円の辞書順最小パスは 001 003
2個で5円の辞書順最小パスは 001 004
2個で6円の辞書順最小パスは 001 005
2個で7円の辞書順最小パスは 001 006
2個で8円の辞書順最小パスは 001 007
2個で9円の辞書順最小パスは 001 008
3個で6円の辞書順最小パスは 001 002 003
3個で7円の辞書順最小パスは 001 002 004
3個で8円の辞書順最小パスは 001 002 005
3個で9円の辞書順最小パスは 001 002 006

1 2 6

解説

string[御菓子の数,金額合計]な2次元配列に
辞書順最小Pathを記憶するDPを使ってます。