ABC473-D Coefficient Stair

問題へのリンク

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("3 8");
            //0 1 2 
            //0 4 0 
            //1 2 1 
            //2 0 2 
            //2 3 0 
            //3 1 1 
            //4 2 0 
            //5 0 1 
            //6 1 0 
            //8 0 0 
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("1 200000");
            //200000 
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("8 9");
            //0 0 0 1 1 0 0 0 
            //0 0 1 0 0 1 0 0 
            //0 0 3 0 0 0 0 0 
            //0 1 0 0 0 0 1 0 
            //0 1 1 1 0 0 0 0 
            //0 2 0 0 1 0 0 0 
            //0 3 1 0 0 0 0 0 
            //1 0 0 0 0 0 0 1 
            //1 0 0 2 0 0 0 0 
            //1 0 1 0 1 0 0 0 
            //1 1 0 0 0 1 0 0 
            //1 1 2 0 0 0 0 0 
            //1 2 0 1 0 0 0 0 
            //1 4 0 0 0 0 0 0 
            //2 0 0 0 0 0 1 0 
            //2 0 1 1 0 0 0 0 
            //2 1 0 0 1 0 0 0 
            //2 2 1 0 0 0 0 0 
            //3 0 0 0 0 1 0 0 
            //3 0 2 0 0 0 0 0 
            //3 1 0 1 0 0 0 0 
            //3 3 0 0 0 0 0 0 
            //4 0 0 0 1 0 0 0 
            //4 1 1 0 0 0 0 0 
            //5 0 0 1 0 0 0 0 
            //5 2 0 0 0 0 0 0 
            //6 0 1 0 0 0 0 0 
            //7 1 0 0 0 0 0 0 
            //9 0 0 0 0 0 0 0 
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

    static long mN;
    static long mK;
    static List<long[]> mAnswerList = new List<long[]>();

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = GetSplitArr(InputList[0]);
        mN = wkArr[0];
        mK = wkArr[1];

        mValArr = new long[mN];
        dfs(0);

        // Listの要素である、配列でソート
        mAnswerList.Sort((A, B) =>
        {
            int UB = A.Length - 1;
            for (int I = UB; 0 <= I; I--) {
                if (A[I] != B[I]) {
                    return A[I].CompareTo(B[I]);
                }
            }
            return 0;
        });

        var sb = new System.Text.StringBuilder();
        mAnswerList.ForEach(pX => sb.AppendLine(LongEnumJoin(pX)));
        Console.Write(sb.ToString());
    }

    static long[] mValArr;
    static long mSumVal;

    // 再帰でdfs
    static void dfs(long pDepth)
    {
        // クリア判定
        if (pDepth == mN - 1) {
            mValArr[mN - 1] = mK - mSumVal;
            mAnswerList.Add((long[])mValArr.Clone());
            return;
        }

        long NextProd = mN - pDepth;
        for (long I = 0; I <= mK; I++) {
            if (mSumVal + NextProd * I > mK) break;
            mValArr[pDepth] = I;

            mSumVal += NextProd * I;
            dfs(pDepth + 1);

            mValArr[pDepth] = 0;
            mSumVal -= NextProd * I;
        }
    }

    // セパレータとLong型の列挙を引数として、結合したstringを返す
    static string LongEnumJoin(long[] pArr)
    {
        var sb = new System.Text.StringBuilder();
        for (int I = pArr.GetUpperBound(0); 0 <= I; I--) {
            sb.Append(pArr[I]);
            if (0 < I) {
                sb.Append(' ');
            }
        }
        return sb.ToString();
    }
}

解説

まず、方針を考えます。

方針1 詰まない遷移のみでDFSする。
方針2 途中で詰む遷移もあるけど、枝切りで高速化する。

この問題では、制約が厳しいので、方針1を採用したいです。
これは、大きい値から決めていき
最後に1の分を決定することで方針1を実現できます。

また、DFSの実装には、Stackと再帰の2通りありますが、
選択している要素を覚える必要があるので、再帰で実装します。
選択している要素は、グローバル変数の配列で保持します。

さらに、計算量削減で、最後の1つは、ループを回避してます。