CODE FESTIVAL 2015 決勝 D - 足ゲームII

CODE FESTIVAL 2015 決勝 に参加しました。5 完最下位です。ABCDE で辛い思いをしていたら終わってしまって, あまりおもしろいところに食い込めなかったのが残念です。

問題

code-festival-2015-final-open.contest.atcoder.jp

解法

本番は脳筋遅延評価セグメント木で通しました。

よくある区間スケジューリング問題と同じで, 押す時間が終わるのが早い順にソートして, 貪欲に取っていけば最適です。
ということで, リズムゲーをする人が x 人であるとした時に, あるボタン i を押し続けられるかどうかの判定は, 「S[i] から T[i] の時間の間に, x 人以上ボタンを押している時間が存在しない」ということになります。

これは, 各時間にボタンを押している人数を持ったセグメント木を考えれば解けます。
区間の最大値を取得でき, 区間に対して 1 を加えるような遅延評価セグメント木を作れば良いです。

ただ, そんなことしなくても解けます(そもそも D 問題でそんな難しくないんだよなぁ)。

押さなければならないボタンの数は N-1 ですが, もし押さなければならないボタンの数が N であったとすると, 答えは区間の最大重複数(a とする)になります。
ということは, N-1 個のボタンを押すには a か a-1 人の人がいることになります。

a-1 人でいける場合, どれかの区間を取り除いた場合必要人数が 減ってくれれば良いです。
最大重複数, 減るかの判定はそれぞれいもす法を使えばいけます。

いもす法

const int MAXN = 100010;
int S[MAXN];
int F[MAXN], T[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int s, t;
        cin >> s >> t;
        F[i] = s; T[i] = t;
        S[s] += 1; S[t] -= 1;
    }
    for (int i = 1; i < MAXN; i++) {
        S[i] += S[i-1];
    }
    int ans = 0;
    for (int i = 0; i < MAXN; i++) ans = max(ans, S[i]);
    int L = MAXN, R = 0;
    for (int i = 0; i < MAXN; i++) {
        if (S[i] == ans) {
            L = min(L, i);
            R = max(R, i);
        }
    }
    bool ok = false;
    for (int i = 0; i < n; i++) {
        if (F[i] <= L && R < T[i]) ok = true;
    }
    if (ok) ans--;
    cout << ans << endl;
    return 0;
}

脳筋セグメント木

const int MAXN = 100010;
pii P[MAXN];

struct segtree {
    int N;
    vector<int> dat, sum;
    segtree(int n) {
        N = 1;
        while(N < n) N <<= 1;
        dat.assign(2*N-1,0);
        sum.assign(2*N-1,0);
    }
    void add(int a, int b, int x) { add(a,b,x,0,0,N); }
    int add(int a, int b, int x, int k, int l, int r) {
        if(b <= l or r <= a) return dat[k];
        if(a <= l and r <= b) {
            sum[k] += x;
            return dat[k] += x;
        }
        int m = (l+r)/2;
        return dat[k] = min(add(a,b,x,2*k+1,l,m),add(a,b,x,2*k+2,m,r))+sum[k];
    }
    int minimum(int a, int b) { return minimum(a,b,0,0,N); }
    int minimum(int a, int b, int k, int l, int r) {
        if(b <= l or r <= a) return 1e9;
        if(a <= l and r <= b) return dat[k];
        int m = (l+r)/2;
        return min(minimum(a,b,2*k+1,l,m),minimum(a,b,2*k+2,m,r))+sum[k];
    }
};

bool ok(int x, int n) {
    segtree seg(MAXN);
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        int tmp = -seg.minimum(P[i].second, MAXN);
        if (tmp < x) {
            seg.add(P[i].second, P[i].first, -1);
            cnt++;
        }
    }
    return cnt >= n-1;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> P[i].second >> P[i].first;
    sort(P, P+n);
    int low = 0, high = n;
    while (high - low > 1) {
        int med = (high+low) / 2;
        if (ok(med, n)) high = med;
        else low = med;
    }
    cout << high << endl;
    return 0;
}