yukicoder    次のyukicoderの問題へ    前のyukicoderの問題へ

yukicoder 2567 A_1 > A_2 > ... > A_N


問題へのリンク


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");
            WillReturn.Add("4 10");
            WillReturn.Add("3 5");
            WillReturn.Add("3 9");
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        long[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            long N = wkArr[0];
            long X = wkArr[1];

            string Result = Solve(N, X);
            Console.WriteLine(Result);
        }
    }

    static string Solve(long pN, long pX)
    {
        long[] AnswerArr = new long[pN];
        long UB = AnswerArr.GetUpperBound(0);

        long InitVal = 1;
        for (long I = UB; 0 <= I; I--) {
            AnswerArr[I] = InitVal++;
        }
        long SumVal = AnswerArr.Sum();
        if (SumVal > pX) {
            return "-1";
        }

        long Rest = pX - SumVal;

        long AddVal = Rest / pN;
        for (long I = 0; I <= UB; I++) {
            AnswerArr[I] += AddVal;
        }

        Rest -= AddVal * pN;

        for (long I = 0; I <= UB; I++) {
            if (Rest > 0) {
                AnswerArr[I]++;
                Rest--;
            }
        }
        return LongEnumJoin(" ", AnswerArr);
    }

    // セパレータとLong型の列挙を引数として、結合したstringを返す
    static string LongEnumJoin(string pSeparater, IEnumerable<long> pEnum)
    {
        string[] StrArr = Array.ConvertAll(pEnum.ToArray(), pX => pX.ToString());
        return string.Join(pSeparater, StrArr);
    }
}


解説

数列が3項であれば、
最初に
3 2 1
とおき、和が不足なら、辞書順で最小になるように、
増加させてます。
1回目の増加は、(不足和 / 項数)の割り算結果
2回目の増加は、初項から末項まで、1ずつ増加
となります。