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

ARC過去問の難易度レビュー - ヘクトのメモ
hecさんの記事を参考にできそうなものから進めています。

B: アットコーダー王国のコンテスト事情 - AtCoder Regular Contest 035 | AtCoder

短い時間で解ける問題から解くのが最もコンテストペナルティが少なくなります。
解くのにかかる時間を昇順にソートして、貪欲法っぽく(別の言い方をするなら「普通に」)時間を足していきます。

解き方の順は以下のように通り数をかけるだけです。(入力例2を例にすると)

1minの問題 1min 2min 2min 2min (最適な解く順番)
<---- 2! -----> <---- 3! ---->

2! * 3! = 2 * 6 = 12

このとき階乗を求める関数で随時modを取っていかないとオーバーフローで計算できなくなります。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
using ll = long long;
const ll INF = 1e9;
const ll MOD = 1e9 + 7;

ll modfact(ll n) { // 階乗して1e9+7で割ったあまりを計算
    if (n <= 1) return 1;
    return (n * modfact(n - 1)) % MOD;
}

int main() {
    int N;
    cin >> N;
    vector<int> T(N);
    for (int i = 0; i < N; i++) cin >> T[i];

    sort(T.begin(), T.end());

    ll ansMin = 0; // 求める最小のコンテストペナルティ
    ll ansWays = 1; // 求める通り数
    ll sum = 0;
    int prev = T[0];
    int cnt = 0;
    for (int i = 0; i < N; i++) {
        if (prev == T[i]) {
            cnt++;
        } else {
            ansWays *= modfact(cnt);
            ansWays %= MOD;
            cnt = 1;
        }
        sum += T[i];
        ansMin += sum;
        prev = T[i];
    }
    if (cnt > 0) {
        ansWays *= modfact(cnt);
        ansWays %= MOD;
    }

    cout << ansMin << endl;
    cout << ansWays << endl;

    return 0;
}