ABC173-E Multiplication 4

問題へのリンク

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("4 2");
            WillReturn.Add("1 2 -3 -4");
            //12
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4 3");
            WillReturn.Add("-1 -2 -3 -4");
            //1000000001
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("2 1");
            WillReturn.Add("-1 1000000000");
            //1000000000
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("10 10");
            WillReturn.Add("1000000000 100000000 10000000 1000000 100000 10000 1000 100 10 1");
            //999983200
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    const long Hou = 1000000007;

    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];
        UB = mK;

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

        long Result = Solve();
        Console.WriteLine(Result);
    }

    static long Solve()
    {
        // 正の数にできるかの判定
        bool CanCreatePlus = DeriveCanCreatePlus();

        // 正の数にできない場合
        if (CanCreatePlus == false) {
            return DeriveMaxNonPlus();
        }

        // 正の数にできる場合
        return DeriveMaxPlus();
    }

    // 正の数にできるかの判定
    static bool DeriveCanCreatePlus()
    {
        long RestK = mK;
        long PlusCnt = 0;
        long MinusCnt = 0;
        foreach (long EachLong in mAArr) {
            if (EachLong == 0) continue;
            if (EachLong > 0) PlusCnt++;
            if (EachLong < 0) MinusCnt++;
        }

        // 優先順位1 2個ペアで負数を使う
        while (RestK >= 2 && MinusCnt >= 2) {
            RestK -= 2;
            MinusCnt -= 2;
        }
        if (RestK == 0) {
            return true;
        }

        // 優先順位2 正の数を使う
        while (RestK >= 1 && PlusCnt >= 1) {
            RestK--;
            PlusCnt--;
        }
        return RestK == 0;
    }

    // 正の数にできない場合の、最大値を返す
    static long DeriveMaxNonPlus()
    {
        long WillReturn = 1;

        // 絶対値の昇順でのK個の積
        foreach (long EachLong in mAArr.OrderBy(pX => Math.Abs(pX)).Take((int)mK)) {
            WillReturn *= EachLong;
            WillReturn %= Hou;
        }

        if (WillReturn < 0) WillReturn += Hou;
        return WillReturn;
    }

    // 正の数にできる場合の、最大値を返す
    static long DeriveMaxPlus()
    {
        var PlusList = mAArr.Where(pX => pX > 0).OrderByDescending(pX => pX).ToList();
        var MinusList = mAArr.Where(pX => pX < 0).OrderBy(pX => pX).ToList();

        long WillReturn = 1;

        long RestK = mK;

        // 奇数の場合は、正の最大値を事前に取る
        if (RestK % 2 == 1) {
            WillReturn *= PlusList[0];
            WillReturn %= Hou;
            RestK--;
            PlusList.RemoveAt(0);
        }
        if (RestK == 0) {
            return WillReturn;
        }

        // 2個ペアを作る
        var PlusPairList = new List<long>();
        var MinusPairList = new List<long>();

        for (int I = 1; I <= PlusList.Count - 1; I += 2) {
            // Modを取らずに比較する必要あり
            PlusPairList.Add(PlusList[I - 1] * PlusList[I]);
        }

        for (int I = 1; I <= MinusList.Count - 1; I += 2) {
            // Modを取らずに比較する必要あり
            MinusPairList.Add(MinusList[I - 1] * MinusList[I]);
        }

        var UnionList = new List<long>();
        UnionList.AddRange(PlusPairList);
        UnionList.AddRange(MinusPairList);

        // 降順で2個ずつ取る
        foreach (long EachLong in UnionList.OrderByDescending(pX => pX)) {
            long Mod = EachLong % Hou;
            WillReturn *= Mod;
            WillReturn %= Hou;
            RestK -= 2;
            if (RestK == 0) break;
        }
        return WillReturn;
    }
}

解説

最初に場合分けで、
正の数を作れる場合と
正の数を作れない場合に分けます。

正の数を作れるかの判定は、
優先順位1 マイナスの数が2つあったら使う
優先順位2 プラスの数を使う
これでK個の数を使えれば積を正にできます。

正の数を作れない場合は、絶対値の昇順にK個取るのが最適になります。

正の数を作れる場合は、
さらにKの偶奇で場合分けします。
Kが奇数の場合は、
負の数を偶数個、正の数を奇数個使う必要があるので、
最大の正の数を最初に使って、
負の数を偶数個、正の数を偶数個使う状態に遷移できます。

Kが偶数の場合は、
負の数を偶数個、正の数を偶数個使う必要があるので、
負の数の昇順での2個ずつペアの積と
正の数の降順での2個ずつペアの積を
混ぜた集合から、降順で K / 2 個の積が解になります。