ARC-035-B アットコーダー王国のコンテスト事情

■■■問題■■■

高橋くん様は、アットコーダー王国の王様です。

プログラミングコンテスト好きな彼が統治するアットコーダー王国では、
年に一度コンテストが開催されます。

このコンテストではN問の問題が出題されます。
また、順位を付ける際の1つの要素としてペナルティというものが存在します。
ある問題を正解したとき、
コンテスト開始から経過した時間分だけのペナルティが、各問題ごとに発生します。
そして、その発生したペナルティの総和がコンテストペナルティとなります。
ARCのペナルティとは異なるルールであることに注意してください。

非常に優秀な国民である貴方には、全ての問題を解く力があります。
しかも、全ての問題について、
その問題を正解するためにどれだけ時間をかければよいのかを知っており、
ちょうどその時間取り組むと必ず正解することができます。

貴方は、自由な順番で問題を解くことができるので、
コンテストペナルティが最小となるように解こうと思いました。

全ての問題を解くときのコンテストペナルティの最小値と、
そのような解き方が何通りあるかを 1000000007(10の9乗+7)で割った余りを答えて下さい。

■■■入力■■■

N
T1
T2
・
・
・
TN

●1行目には、コンテストでの問題数を表す整数 N(1 <= N <= 1万) が
  スペース区切りで与えられる。
●2行目からのN行には、各問題を解くのにかかる時間の情報が与えられる。
  そのうち i(1 <= i <= N) 行目には、整数 Ti(1 <= Ti <= 1万) が書かれており、
  i番目の問題を解くのにTi分かかることを示す。

■■■出力■■■

出力は以下の形式で標準出力に出力せよ。
●1行目には、コンテストペナルティの最小値を出力せよ。
  32bit整数型ではオーバーフローする可能性があることに気をつけること。
●2行目には、コンテストペナルティが最小となるような解き方の数を
  1000000007(10の9乗+7) で割った余りを出力せよ。

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");
            WillReturn.Add("20");
            WillReturn.Add("10");
            //40
            //1
            //2番目の問題を解いてから1番目の問題を解くのがよい。
            //●コンテストが開始する(時刻：0 分)。
            //●10分後、2番目の問題に正解する(時刻：10 分)。
            //  この時点で発生するペナルティは10分である。
            //●その20分後、1番目の問題に正解する(時刻： 30 分)。
            //  この時点で発生するペナルティは30分である。
            //コンテストペナルティは 40(=10+30) 分となる。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5");
            WillReturn.Add("2");
            WillReturn.Add("1");
            WillReturn.Add("2");
            WillReturn.Add("1");
            WillReturn.Add("2");
            //21
            //12
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("13");
            WillReturn.Add("1");
            WillReturn.Add("1");
            WillReturn.Add("1");
            WillReturn.Add("1");
            WillReturn.Add("1");
            WillReturn.Add("1");
            WillReturn.Add("1");
            WillReturn.Add("1");
            WillReturn.Add("1");
            WillReturn.Add("1");
            WillReturn.Add("1");
            WillReturn.Add("1");
            WillReturn.Add("1");
            //91
            //227020758
            //どのような順番で解いても良い。
            //余りを取るのを忘れないこと。
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    const long Hou = 1000000007;

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] TArr = InputList.Skip(1).Select(X => long.Parse(X)).ToArray();

        var CntDict = new Dictionary<long, long>();
        for (int I = 0; I <= TArr.GetUpperBound(0); I++) {
            long KeyVal = TArr[I];
            if (CntDict.ContainsKey(KeyVal))
                CntDict[KeyVal]++;
            else CntDict[KeyVal] = 1;
        }

        //階乗を求めておく
        long CntMax = CntDict.Values.Max();
        long[] KaijyouArr = new long[CntMax + 1];
        KaijyouArr[1] = 1;
        for (int I = 2; I <= KaijyouArr.GetUpperBound(0); I++) {
            KaijyouArr[I] = I * KaijyouArr[I - 1];
            KaijyouArr[I] %= Hou;
        }

        //ペナルティ合計と場合の数を求める
        long PenaltySum = 0;
        long CurrTime = 0;
        long PatternCnt = 1;
        foreach (var EachPair in CntDict.OrderBy(X => X.Key)) {
            //積の法則
            PatternCnt *= KaijyouArr[EachPair.Value];
            PatternCnt %= Hou;
            for (int I = 1; I <= EachPair.Value; I++) {
                CurrTime += EachPair.Key;
                PenaltySum += CurrTime;
            }
        }
        Console.WriteLine(PenaltySum);
        Console.WriteLine(PatternCnt);
    }
}

解説

全部で4問あってABCDとすると
合計ペナルティ = A*4 + B*3 + C*2 + D*1
なので、昇順に解いていくのが最適となります。