問題概要

$ N (\leq 2 \times 10^5) $ 個の長方形がある．$ i (1 \leq i \leq N) $ 番目の長方形は幅 $ A_i (1 \leq A_i \leq 10^9) $ ，高さ $ B_i (1 \leq B_i \leq 10^9) $ である．

以下の条件で長方形を重ねていく．最大いくつの長方形を重ねることができるか．

長方形の幅と高さを入れ替えても良い．
j 番目に配置した長方形が j-1 番目に配置した長方形に完全に含まれる．
j 番目に配置した長方形の辺と j-1 番目に配置した長方形の辺が接してはならない
j 番目に配置した長方形の各辺は j-1 番目に配置した長方形の辺のうちいずれかと並行でなければならない．

解法概要

D - プレゼントの類題．違いは幅と高さを入れ替えても良いのかどうかぐらい？

ただ，横長 (縦長) の長方形の中に縦長 (横長) の長方形を入れるくらいだったら縦長横長を揃えた方がたくさんの長方形を重ねられるので，初めに幅 < 高さか高さ < 幅かで揃えておく．

D - プレゼントと同様に，最長増加列 (LIS) を求める要領で解く．

LIS は $ i \lt j $ かつ $ X_i \lt X_j $ となるような列で長さが最大になるものであり，

$ dp_i = $ 長さが i の増加列の最後の値の最小値

として時間計算量 $ O(n\log n)$ で求める DP が有名である．

$ A_i $ ， $ B_i $ で同じ値が再度登場しないとすると，$ A_i $ の昇順で長方形の ($ A_i, B_i $ ) のペアをソートしておいて，$ B_i $ の LIS を求めればよい．

問題は，$ A_i $ や $ B_i $ で同じ値が登場しうるということである．これについては，ペアをソートする際に例えば ($ A_i , -B_i $ ) でソートするなどすればよい．すると， $ A_i $ が同じなら $ B_i $ } の降順でソートされることになる．こうすることで， $ A_i = A_j $ なのに $ B_i \lt B_j $ となっているがために長方形 i を長方形 j が包んでいることになってしまう……といった事態を防ぐことができる．

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> Pii;

const int A_MAX = 1<<30;

int main() {
    int n;
    cin >> n;
    vector<Pii> a(n);
    for(int i=0;i<n;++i){
        cin >> a[i].first >> a[i].second;
        if(a[i].first > a[i].second) {
            swap(a[i].first, a[i].second);
        }
        a[i].second *= -1;
    }

    sort(a.begin(), a.end());

    vector<int> dp(n+1, A_MAX);
    dp[0] = -a[0].second;
    for(int i=1;i<n;++i) {
        *lower_bound(dp.begin(), dp.end(), -a[i].second) = -a[i].second;
    }

    cout << distance(dp.begin(), lower_bound(dp.begin(), dp.end(), A_MAX)) << endl;
}

所感

SpeedRun は初めてだったけど楽しかった！

LIS を求める DP は見かけるたびに理解し直しになってる気がする……．

NoiminのNoise

Chokudai SpeedRun 002 L - 長方形 β

問題概要

解法概要

ソースコード

所感