JOI 春合宿 2022 day2-3 チーム戦 (4D, 難易度 10)

面白かった！

• 問題へのリンク

問題概要

人がいて、人 の考察力、実装力、運はそれぞれ である。

これら から 3 人を選ぶ。ただし、3 人全員について「考察力・実装力・運のうちのいずれかについては他 2 人よりも真に高い」という条件を満たさなければならない。

この条件を満たすように 3 人を選ぶ方法をすべて考えたときの、考察力最強の人の考察力、実装力最強の人の実装力、運最強の人の運の総和の最大値を求めよ。

制約

• 
• 

考えたこと

最初座圧して考えたが、結局座圧は必要なかった。

さて、まず「人 が考察力、実装力、運のうちの 2 種類以上で最大であるならば、人 をチームに採用できない」ということを考察した。なぜならば、残り 2 人をどのように選んだとしても、それら 2 人がともに「考察力・実装力・運のうちのいずれかでは 3 人中最強」という状態を満たすようにはできなくなるからだ。

よって、その場合、 人の中から人 を除外した 人についての問題を解けばよいということになる。

なお、人 を除外した結果、新たに人 が考察力、実装力、運のうちの 2 種類以上で最強という状態になることもありうる。その場合は、その人 も削除する......ということを繰り返す。具体的には、次のようにすればよい。

---

• 考察力が最強の人（複数人ありうる）を 1 人選ぶ（ とする）
  • もし が実装力または運においても最強であるとき： を除外して、上に戻って考察力が最強の人 を選ぶのをやり直す
• 実装力が最強の人を 1 人選ぶ（ とする）
  • もし が考察力または運においても最強であるとき： を除外して、上に戻って実装力が最強の人 を選ぶのをやり直す
• 運が最強の人を 1 人選ぶ（ とする）
  • もし が考察力または実装力においても最強であるとき： を除外して、上に戻って運が最強の人 を選ぶのをやり直す

---

この繰り返しの手続きを繰り返していき、最後に残った 3 人 を取れたならば、それら 3 人で組む場合が最適であると言える。なお、各力について最強が複数人いるような場合が気になる。その場合であっても「各力について最強の人を 1 人選ぶ」とすればよい。

以上の手続きは、set などを用いて の計算量で実装できる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<long long> A(N), B(N), C(N);
    for (int i = 0; i < N; i++) cin >> A[i] >> B[i] >> C[i];

    set<pair<long long, int>> as, bs, cs;
    for (int i = 0; i < N; i++) {
        as.insert(make_pair(A[i], i));
        bs.insert(make_pair(B[i], i));
        cs.insert(make_pair(C[i], i));
    }

    // 人 ind を削除する操作
    auto erase = [&](int ind) -> void{
        as.erase(make_pair(A[ind], ind));
        bs.erase(make_pair(B[ind], ind));
        cs.erase(make_pair(C[ind], ind));
    };

    // A の最強の人が条件を満たすかの check（満たさなければ削除する）
    auto acheck = [&]() -> bool {
        auto [val, ind] = *as.rbegin();
        if (B[ind] == bs.rbegin()->first || C[ind] == cs.rbegin()->first) {
            erase(ind);
            return false;
        }
        return true;
    };

    // B の最強の人が条件を満たすかの check（満たさなければ削除する）
    auto bcheck = [&]() -> bool {
        auto [val, ind] = *bs.rbegin();
        if (A[ind] == as.rbegin()->first || C[ind] == cs.rbegin()->first) {
            erase(ind);
            return false;
        }
        return true;
    };

    // C の最強の人が条件を満たすかの check（満たさなければ削除する）
    auto ccheck = [&]() -> bool {
        auto [val, ind] = *cs.rbegin();
        if (A[ind] == as.rbegin()->first || B[ind] == bs.rbegin()->first) {
            erase(ind);
            return false;
        }
        return true;
    };

    // A, B, C の最強が被るならば削除することを繰り返していく
    while (!as.empty() && !bs.empty() && !cs.empty()) {
        if (acheck() && bcheck() && ccheck()) {
            cout << as.rbegin()->first + bs.rbegin()->first + cs.rbegin()->first << endl;
            return 0;
        }
    }
    cout << -1 << endl;
}