AtCoder Regular Contest 053 C - 魔法使い高橋君

問題

　 $N(\le 10^5)$ 個の魔法があり、 $i$ 番目の魔法を唱えると気温が $a_i(\le 10^9)$ 度上がって $b_i(\le 10^9)$ 度下がる。全ての魔法を1回ずつ唱えるとき、この間の気温の最大値を最小化せよ。

解法

　まず $a_i \lt b_i$ であるものについて $a_i$ の昇順に、次に $a_i = b_i$ であるものについて任意の順番に、最後に $a_i \gt b_i$ であるものについて $b_i$ の降順に使用していけば良い。

　 $a_i \lt b_i$ であるものについて $a_i$ の昇順に使用すれば良いことはわかりやすいが、 $a_i \gt b_i$ であるものについて $b_i$ の降順に使用すれば最善となることについては、逆から見た状況を考えると良い。最後の温度から考え始めて $a_i \gt b_i$ であるものを用いて気温の最大値を最小化するのは、最初の気温から $a_i \lt b_i$ であるものを用いて最小化するのと変わらない状況である。

反省

　1時間12分(0WA)でAC。1時間考察したがコードを書く段階には到達せず、結局1行も書かないまま解説を見ることになった。

　これが解けないのはちょっとつらいところ。 $a_i$ と $b_i$ の大小関係で場合分けして考えることはしていたが、 $a_i \gt b_i$ であるものについてどういう順番で使用すれば最善なのかがわからなかった。逆から見るという発想が完全に抜けてしまっていたとは……。そうでなくとも大きい $b$ が来ればそれ以降はその中に変化が収まってしまうみたいなところは考えていたのになぁ。残念。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N;
    cin >> N;
    vector<pair<ll, ll>> lesser, equal, greater;
    for (ll i = 0; i < N; i++) {
        ll a, b;
        cin >> a >> b;
        if (a > b) {
            greater.emplace_back(a, b);
        } else if (a == b) {
            equal.emplace_back(a, b);
        } else {
            lesser.emplace_back(a, b);
        }
    }

    sort(lesser.begin(), lesser.end(), [&](pair<ll, ll>& lhs, pair<ll, ll>& rhs) {
        return lhs.first < rhs.first;
    });
    sort(greater.begin(), greater.end(), [&](pair<ll, ll>& lhs, pair<ll, ll>& rhs) {
        return lhs.second > rhs.second;
    });

    ll ans = 0, curr = 0;
    for (auto p : lesser) {
        curr += p.first;
        ans = max(ans, curr);
        curr -= p.second;
    }
    for (auto p : equal) {
        curr += p.first;
        ans = max(ans, curr);
        curr -= p.second;
    }
    for (auto p : greater) {
        curr += p.first;
        ans = max(ans, curr);
        curr -= p.second;
    }

    cout << ans << endl;
}