ferinの競プロ帳

競プロについてのメモ

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