square869120コンテスト3 A問題 カレンダー

問題へのリンク

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("7 7");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("6 0");
            //2
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("18 10");
            //7
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("100 8");
            //45
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static int mN;
    static int mK;

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

        int[] wkArr = InputList[0].Split(' ').Select(pX => int.Parse(pX)).ToArray();
        mN = wkArr[0];
        mK = wkArr[1];

        // 項数
        int Kousuu = mN - 2;
        if (Kousuu <= 0) {
            Console.WriteLine(0);
            return;
        }

        int Answer = 0;
        for (int I = 1; I <= 5; I++) {
            int[] PreCycleArr;
            int[] CycleArr;
            DeriveArr(9 * (9 + I - 1), 63, out PreCycleArr, out CycleArr);

            // 周期に入る前の分を加算
            int Rest = Kousuu;
            int TakeCnt = Math.Min(Rest, PreCycleArr.Length);
            int CurrAnswer = PreCycleArr.Take(TakeCnt).Count(pX => pX == mK);
            Rest -= PreCycleArr.Length;
            if (Rest == 0) {
                Console.WriteLine(Answer);
                continue;
            }

            // 周期の分を加算
            if (CycleArr.Length <= Rest) {
                int OneCycleSum = CycleArr.Count(pX => pX == mK);
                CurrAnswer += OneCycleSum * (Rest / CycleArr.Length);
                Rest %= CycleArr.Length;
            }

            // 残りの分を加算
            CurrAnswer += CycleArr.Take(Rest).Count(pX => pX == mK);

            Answer += CurrAnswer;
        }
        Console.WriteLine(Answer);
    }

    // 初項、項数、公差を引数として、PreCycleArrとCycleArrを設定
    static void DeriveArr(int pSyokou, int pKousa, out int[] pPreCycleArr, out int[] pCycleArr)
    {
        var AppearList = new List<int>();
        var AppearSet = new HashSet<int>();

        int CurrVal = pSyokou % 11;
        while (true) {
            if (AppearSet.Contains(CurrVal)) {
                pPreCycleArr = AppearList.TakeWhile(pX => pX != CurrVal).ToArray();
                pCycleArr = AppearList.SkipWhile(pX => pX != CurrVal).ToArray();
                break;
            }
            AppearList.Add(CurrVal);
            AppearSet.Add(CurrVal);

            CurrVal += pKousa;
            CurrVal %= 11;
        }
    }
}

解説

 1  2  3  4  5  6  7
 8  9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31 32 33 34 35
36 37 38 39 40 41 42
43 44 45 46 47 48 49

 9のマス +  9のマスの8近傍の和は、 9 * 9 = 81
10のマス + 10のマスの8近傍の和は、10 * 9 = 90
11のマス + 11のマスの8近傍の和は、11 * 9 = 99
そして、

 9*9,16*9,23*9,30*9 ・・・ の等差素列
10*9,17*9,24*9,31*9 ・・・ の等差素列
11*9,18*9,25*9,32*9 ・・・ の等差素列
12*9,19*9,26*9,33*9 ・・・ の等差素列
13*9,20*9,27*9,34*9 ・・・ の等差素列
の5つの等差素列に着目すれば、
mod 11 で見て周期があるので、周期を使って、解を求めることができます。