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だと分かります。

後は、
休日の間の日数を、環状対応した配列から、
列挙すれば良いです。