ABC136-E Max GCD

問題へのリンク

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("2 3");
            WillReturn.Add("8 20");
            //7
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2 10");
            WillReturn.Add("3 5");
            //8
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("4 5");
            WillReturn.Add("10 1 2 22");
            //7
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("8 7");
            WillReturn.Add("1 7 5 6 8 2 6 5");
            //5
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long mK;

    static long[] mAArr;
    static long UB;

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        mK = wkArr[1];

        mAArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        UB = mAArr.GetUpperBound(0);

        long SumVal = mAArr.Sum();

        // 総和の約数であることが必要条件
        long[] YakusuuArr = DeriveYakusuuArr(SumVal);

        foreach (long EachYakusuu in YakusuuArr.OrderByDescending(pX => pX)) {
            if (CanAchive(EachYakusuu)) {
                Console.WriteLine(EachYakusuu);
                break;
            }
        }
    }

    // K回の加算と減算で、数列の全ての項を、pHouの倍数にできるかを判定
    static bool CanAchive(long pHou)
    {
        var ModList = new List<long>();
        for (int I = 0; I <= UB; I++) {
            ModList.Add(mAArr[I] % pHou);
        }
        ModList.Sort();

        // 全てをプラス方向への移動回数の総合計
        long PlusSum = 0;
        foreach (long EachMod in ModList) {
            PlusSum += pHou - EachMod;
        }

        // K回以内に、数列の全要素のmodを0にできるかを判定
        long RestCnt = mK;
        long MinusSum = 0;
        foreach (long EachMod in ModList) {
            MinusSum += EachMod;
            PlusSum -= pHou - EachMod;
            RestCnt -= EachMod;

            if (RestCnt < 0) return false;
            if (PlusSum == MinusSum) return true;
        }
        return false;
    }

    // 約数を列挙する
    static long[] DeriveYakusuuArr(long pTarget)
    {
        var YakusuuSet = new HashSet<long>();
        for (long I = 1; I * I <= pTarget; I++) {
            if (pTarget % I == 0) {
                YakusuuSet.Add(I);
                YakusuuSet.Add(pTarget / I);
            }
        }
        long[] YakusuuArr = YakusuuSet.ToArray();
        Array.Sort(YakusuuArr);
        return YakusuuArr;
    }
}

解説

P ⇒ Q 成立する場合、
QはPであるための必要条件となります。

Xが数列の各項の約数  ⇒ Xが数列の合計値の約数
なので
必要条件で絞ることができます。

数列の合計値の約数を全探索して、
数列の各項が判定するのは、
modで考えて、modを昇順にソートして、
左の項から引いて、右の項に足して、
全ての項をK回以下の操作で0にできるかを判定することになります。

これは、左の項からどの項までを引いて、それ以降を足すかの
全探索で判定できます。