mayoko’s diary

プロコンとかいろいろ。

Typical DP Contest K - ターゲット

解法

円の右端が小さい順に円を並べます。

円iがほかの円jを内包している条件は, (円iの左端の座標) < (円jの左端の座標) かつ (円jの右端の座標) < (円iの右端の座標)
であるので, 上記のような並べ方をすると, すでに 右側の条件は満たしていることになります。なので, あと考えるべきなのは 左側の条件のみです(こういうテクよくあるけどなかなか思いつかない…)。

左端の座標については, セグメント木を使うとうまくいきます。

  • dp[i] を求めるときは (Xi-Ri, Xi+Ri) の区間にある円の左端座標の中で dp[j] が最大のものを探す
  • dp[i] の値をセグメント木に入れて更新するときは, (Xi-Ri) の位置に dp[i] を入れて更新

もちろん座標圧縮しておく必要はあります。

円の右端の座標が一致している場合は, セグメント木を更新しないで同時に考えないといけないことに注意です。

追記: LIS で解けるようです。こっちのほうが実装ラクで頭良いです。
kmjp.hatenablog.jp

// セグメント木(RMQ 対応)
// update: k 番目の値を a に変更
// query: [l, r) の区間の最大値を求める
template<typename T>
struct ST {
    vector<T> seg;
    int size;
    ST(int n) {
        size = 1;
        while (size < n) size *= 2;
        seg.resize(2*size-1, 0);
    }
    inline T merge(T x, T y) {
        return max(x, y);
    }
    void update(int k, T a) {
        k += size-1;
        seg[k] = a;
        while (k > 0) {
            k = (k-1)/2;
            seg[k] = merge(seg[k*2+1], seg[k*2+2]);
        }
    }
    T query(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) return 0;
        if (a <= l && r <= b) return seg[k];
        T vl = query(a, b, k*2+1, l, (l+r)/2);
        T vr = query(a, b, k*2+2, (l+r)/2, r);
        return merge(vl, vr);
    }
    T query(int a, int b) {
        return query(a, b, 0, 0, size);
    }
};

const int MAXN = 100100;
pii X[MAXN];
int dp[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) 
    	cin >> X[i].first >> X[i].second;
    vector<int> vs;
    for (int i = 0; i < N; i++) {
    	vs.push_back(X[i].first+X[i].second);
    	vs.push_back(X[i].first-X[i].second);
    }
    sort(vs.begin(), vs.end());
    vs.erase(unique(vs.begin(), vs.end()), vs.end());
    sort(X, X+N, [](const pii& lhs, const pii& rhs){return lhs.first+lhs.second < rhs.first+rhs.second;});
    ST<int> seg(2*N);
    int ans = 0;
    for (int i = 0; i < N; ) {
        int ni = i+1;
        while (ni < N && X[i].first+X[i].second == X[ni].first+X[ni].second) ni++;
        for (int j = i; j < ni; j++) {
            int l = lower_bound(vs.begin(), vs.end(), X[j].first-X[j].second) - vs.begin();
            int r = lower_bound(vs.begin(), vs.end(), X[j].first+X[j].second) - vs.begin();
            dp[j] = seg.query(l+1, r) + 1;
            ans = max(ans, dp[j]);
        }
        for (int j = i; j < ni; j++) {
            int l = lower_bound(vs.begin(), vs.end(), X[j].first-X[j].second) - vs.begin();
            seg.update(l, dp[j]);
        }
        i = ni;
    }
    cout << ans << endl;
    return 0;
}