解き切りたかった

問題概要

オレンジが $X$ 個、みかんが $Y$ 個ある。これを $N$ 人で分け合う ( $X+Y$ が $N$ の倍数であることは保証される)。

それぞれの人 $i$ について、オレンジとみかんそれぞれ 1 個あたりの満足度が $A_i, B_i$ で与えられる。

うまく分けて、各人の満足度の最大値と最小値の差を最小にせよ。

制約

$1 \le X + Y \le 10^{5}$
$1 \le A_i, B_i \le 10^{9}$

考えたこと

第一感「これが解ける問題なの、すごい」と思った。とりあえず、1 人あたりの個数を $K = \frac{X+Y}{N}$ としておく。

落ち着いて考える。「最大値と最小値の差の最小化」は扱いづらいイメージがあるので、最小値を固定してしまうといいことが多そう。最小値を $L$ に固定してしまえば、単純に「全体が $L$ 以上という制約下での最大値の最小化」の問題になる。そうすると二分探索が決まったり、Greedy に解けたりする。

今回は最小値は一見、10⁹ といった巨大な場合を考えないといけなさそうだが、そんなことはなく。 $N$ 人それぞれについて、 $Ax + By$ のとりうる値は $x + y = K$ という制約のもとで、 $K+1$ 通りなので、とりうる最小値は $O(KN) = O(X+Y)$ 通り。最小値 left を $O(X+Y)$ 個固定して left + d 以下に全員の満足度をおさめられるかを d で二分探索することを考える。

各人 i に対して、満足度が left 以上 left + d 以下になるような A の選択個数 $x$ の上限 maxx[i], minx[i] を求める (例えば二分探索などで)
全員について所望の満足度が達成できる $x$ が存在し、sum(minx[i], i) <= X <= sum(maxx[i], i) が成り立てば OK

という感じ。しかしこのままだとまだ計算時間は $U$ を答えの上限として、 $O((X+Y)N\log{K}\log{U})$ になって厳しい。

.......... コンテスト本番ではここまで考えた。以下、詰め切れなかった部分 ..........

最小値 left と二分探索パラメータ d の固定順序を入れ替えることを考える。d を固定して、left を動かすことで、

ある left に対する結果を持いて、次の left の結果をしゃくとり法によって求める

ことができる！！！！！

そうすれば計算時間は $O((X+Y)\log{U})$ まで下がって通せる。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using pint = pair<int,int>;
using plint = pair<long long, pint>;

// 入力
int X, Y, N, K;
vector<long long> A, B;

// 計算値
vector<plint> vals; // {A[i]x + B[i]y の取りうる値, {i 人目, そのときの x}}

bool solve(long long d) {
    vector<int> minx(N, -1), maxx(N, -1); // 各人 i に対して、left 以上 left+d 以下となる x 値の範囲 (0 <= x <= K)
    int bad = N; // left 以上 left + d 以下の値を取りえないような人数
    int minx_sum = 0, maxx_sum = 0; // 各人についての、minx[i], maxx[i] の総和
    
    // 最小値を決め打ち, しゃくとり法っぽく最大値を 最小値 + d を超えない範囲で動かす
    int right = 0;
    for (int left = 0; left < (int)vals.size(); ++left) {
        for (; right < (int)vals.size(); ++right) {
            if (vals[right].first - vals[left].first > d) break;
            int id = vals[right].second.first;
            int num = vals[right].second.second;
            if (maxx[id] == -1) {
                --bad;
                minx[id] = maxx[id] = num;
                minx_sum += num, maxx_sum += num;
            }
            else if (maxx[id] < num) ++maxx_sum, ++maxx[id]; // x を増やすと満足度が上がるパターン
            else --minx_sum, --minx[id]; // x を増やすと満足度が下がるパターン
        }
        if (bad == 0 && minx_sum <= X && X <= maxx_sum) return true;
        
        // left を除く
        int id = vals[left].second.first;
        int num = vals[left].second.second;
        if (maxx[id] == num) {
            // 人 id のとりうる満足度が left〜right の範囲から一旦消滅
            if (minx[id] == num) {
                ++bad;
                minx_sum -= num; maxx_sum -= num;
                minx[id] = -1, maxx[id] = -1;
            }
            else --maxx[id], --maxx_sum;
        }
        else ++minx[id], ++minx_sum;
    }
    return false;
}

int main() {
    scanf("%d %d %d", &X, &Y, &N);
    A.resize(N); B.resize(N);
    for (int i = 0; i < N; ++i) scanf("%lld %lld", &A[i], &B[i]);
    K = (X + Y) / N;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j <= K; ++j) {
            long long val = A[i] * j + B[i] * (K - j);
            vals.push_back(plint(val, pint(i, j)));
        }
    }
    sort(vals.begin(), vals.end());
    
    long long low = -1, high = 1LL<<50;
    while (high - low > 1) {
        long long mid = (high + low) / 2;
        if (solve(mid)) high = mid;
        else low = mid;
    }
    cout << high << endl;
}

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

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

CODE FESTIVAL 2018 qual A E - オレンジとみかん (800 点)

問題概要

制約

考えたこと