AtCoderのABC
次のABCの問題へ
前のABCの問題へ
ABC347-C Ideal Holidays
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 2 5");
WillReturn.Add("1 2 9");
//Yes
}
else if (InputPattern == "Input2") {
WillReturn.Add("2 5 10");
WillReturn.Add("10 15");
//No
}
else if (InputPattern == "Input3") {
WillReturn.Add("4 347 347");
WillReturn.Add("347 700 705 710");
//Yes
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static void Main()
{
List<string> InputList = GetInputList();
long[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();
long KyuujituCnt = wkArr[1];
long HeijituCnt = wkArr[2];
long[] DArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();
string Result = Solve(KyuujituCnt, HeijituCnt, DArr);
Console.WriteLine(Result);
}
static string Solve(long pKyuujituCnt, long pHeijituCnt, long[] pDArr)
{
// 0オリジンで考える
long pKyuujituUB = pKyuujituCnt - 1;
long pAllUB = pKyuujituCnt + pHeijituCnt - 1;
long Hou = pAllUB + 1;
// 法で割ってからDistinctする
for (long I = 0; I <= pDArr.GetUpperBound(0); I++) {
pDArr[I]--;
pDArr[I] %= Hou;
}
pDArr = pDArr.Distinct().ToArray();
// Dの配列がユニークな場合
if (pDArr.Length == 1) {
return "Yes";
}
// ソートする
Array.Sort(pDArr);
// 環状なので先頭の対応
long AddVal = pDArr[0] + Hou;
long[] DArrTwice = pDArr.Concat(new long[] { AddVal }).ToArray();
var SpanList = new List<long>();
for (long I = 1; I <= DArrTwice.GetUpperBound(0); I++) {
SpanList.Add(DArrTwice[I] - DArrTwice[I - 1] - 1);
}
// 連続した平日を、どこかのスパンに設定できれば良い
if (SpanList.Exists(pX => pX >= pHeijituCnt)) {
return "Yes";
}
return "No";
}
}
解説
土曜始まりのカレンダ−で
休日2日、平日5日で考察すると
休休平平平平平
になります。
周期は7ですので
Dの配列値は、mod 7 で考えて良いと分かります。
また、
連続した平日と、連続した休日があるという配置なので、
連続した平日を、どこかの休日の間に設定できれば
OKだと分かります。
後は、
休日の間の日数を、環状対応した配列から、
列挙すれば良いです。