CODE FESTIVAL 2018 qualA E問題オレンジとみかん

考えたこと

差がmid以下にできるか？が解ければ，二分探索で解ける
差分を決め打ったところでつらそう
min と max を決め打ってみる
全ての人の満足度をこの範囲に収められるか？
dp[i人目まで][残りのみかんj個] = 可能か？
普通にやると $O(NX)$ かかる
満足度を範囲に収める条件で取れるみかんの個数は，連続した整数の区間になる
i人目で可能な残りのみかんの数の区間を保持しながら遷移する
遷移が $O(1)$ なので $O(N)$ で判定可能
minとmaxを両方決めうったところで単調性ないから高速には解けない
minを決めたときにmaxを最小化なら二分探索できるが，minを全探索してたらどう考えてもTLE
----- 解説を見た -----
判定条件をもっと簡単な条件にできる
取れるみかんの数の下限を $l_i$ ，上限を $r_i$ とする
2条件を両方満たす
- 取れるみかんの数がそもそもないような人はいない
- $\sum l_i \leq X \leq \sum r_i$
min,max=min+mid として，minを $0,1,\ldots$ と動かす
minを移動させるときに「不可能な人の数」「 $\sum l_i$ 」「 $\sum r_i$ 」が変動するタイミングは？
min,max が誰かの満足度と一致しているタイミングだけで $O(X+Y)$ 個しかない
$O(X+Y+N)$ で差がmid以下にできるか？を解けた

DPを睨むともっと単純な形にできる
tokaidoを思い出した

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG_   
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
const ll INF = 1LL<<60;  
  
int main(void) {  
    ll x, y, n;  
    cin >> x >> y >> n;  
    vector<ll> a(n), b(n);  
    REP(i, n) cin >> a[i] >> b[i];  
  
    const ll s = (x+y)/n;  
    using P = pair<ll,PII>;  
    vector<P> v;  
    REP(i, n) REP(j, s+1) v.push_back({a[i]*j+b[i]*(s-j), {i, j}});  
    sort(ALL(v));  
  
    // 差がmid以下にできるか？  
    auto check = [&](ll mid) {  
        vector<ll> l(n, -1), r(n, -1);  
        ll bad = n, lsum = 0, rsum = 0;  
  
        ll ma = 0;  
        REP(mi, v.size()) {  
            while(ma < (ll)v.size()) {  
                if(v[ma].first - v[mi].first > mid) break;  
                // v[mi] <= a[id]*num + b[id]*(s-num) <= v[mi]+mid なので追加   
                ll id = v[ma].second.first, num = v[ma].second.second;  
                // id番目がbadだった  
                if(l[id] == -1) {  
                    l[id] = r[id] = num;  
                    bad--;  
                    lsum += num;  
                    rsum += num;  
                }  
                // id番目のrを1更新  
                else if(r[id] == num-1) {  
                    r[id]++;  
                    rsum++;  
                }  
                // id番目のlを1更新  
                else {  
                    l[id] = num;  
                    lsum--;  
                }  
                ma++;  
            }  
            if(bad == 0 && lsum <= x && x <= rsum) return true;  
            // a[id]*num + b[id]*(s-num) が範囲外になるなので削除   
            ll id = v[mi].second.first, num = v[mi].second.second;  
            if(l[id] == num) {  
                // id番目で範囲に入っているやつがなくなる  
                if(r[id] == num) {  
                    l[id] = -1;  
                    r[id] = -1;  
                    lsum -= num;  
                    rsum -= num;  
                    bad++;  
                }  
                // l[id] が範囲から外れる  
                else {  
                    l[id]++;  
                    lsum++;  
                }  
            } else {  
                r[id]--;  
                rsum--;  
            }  
        }  
        return false;  
    };  
  
    ll lb = -1, ub = INF;  
    while(ub-lb > 1) {  
        ll mid = (lb+ub)/2;  
        if(check(mid)) ub = mid;  
        else lb = mid;  
    }  
    cout << ub << endl;  
  
    return 0;  
}

ferinの競プロ帳

競プロについてのメモ

CODE FESTIVAL 2018 qualA E問題オレンジとみかん

考えたこと