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ずつ増加
となります。