ABC272-E Add and Mex

問題へのリンク

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 3");
            WillReturn.Add("-1 -1 -6");
            //2
            //2
            //0
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5 6");
            WillReturn.Add("-2 -2 -5 -7 -15");
            //1
            //3
            //2
            //0
            //0
            //0
        }
        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 N = wkArr[0];
        long M = wkArr[1];

        var ValSetDict = new Dictionary<long, HashSet<long>>();
        for (long I = 1; I <= M; I++) {
            ValSetDict[I] = new HashSet<long>();
        }

        long[] AArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();

        for (long I = 0; I <= AArr.GetUpperBound(0); I++) {
            long Kousa = I + 1;
            long Syokou = AArr[I] + Kousa;
            long KouBan = 1;

            if (Syokou < 0) {
                long Uhen = -Syokou + Kousa;
                KouBan = Uhen / Kousa;

                if (Uhen % Kousa != 0) {
                    KouBan++;
                }
            }

            while (KouBan <= M) {
                long CurrVal = Syokou + Kousa * (KouBan - 1);
                if (N < CurrVal) break;
                ValSetDict[KouBan].Add(CurrVal);
                KouBan++;
            }
        }

        var sb = new System.Text.StringBuilder();
        for (long I = 1; I <= M; I++) {
            for (long J = 0; J <= long.MaxValue; J++) {
                if (ValSetDict[I].Contains(J) == false) {
                    sb.Append(J);
                    sb.AppendLine();
                    break;
                }
            }
        }
        Console.Write(sb.ToString());
    }
}

解説

Mexに影響があるのは、0以上N以下の数になります。
なので、i回目の操作の段階での数の集合を求めるようにします。

等差数列で考えると
一般項は、初項 + 公差 * (項番 - 1)
なので、不等式
一般項 >= 0 を考えると
初項 + 公差 * (項番 - 1) >= 0
項番 >= (初項 - 公差) / 公差
になります。
0以上になる等差数列の項番が分かったので、
Nを超えるまでループさせてます。