問題概要

$N$ 人がいて、人 $i$ の考察力、実装力、運はそれぞれ $A_{i}, B_{i}, C_{i}$ である。

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

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

制約

$3 \le N \le 150000$
$1 \le A_{i}, B_{i}, C_{i} \le 10^{18}$

考えたこと

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

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

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

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

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

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

以上の手続きは、set などを用いて $O(N + Q \log N)$ の計算量で実装できる。

コード

#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;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

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

問題概要

制約

考えたこと

コード