Codeforces #661 Div3 F. Yet Another Segments Subset

問題のリンク

問題概要

クエリ毎にN個の区間が与えられる。次の条件を満たす区間の部分集合のサイズの最大値を求めよ。

• 部分集合内の任意の区間のペアについて、どちらかが片方を完全に包含している。または共有点を持たないかのいずれかが成立する。

制約

解法

区間の相対的な位置関係さえ分かれば問題ないのでまず座圧しておく。

基本的な方針としては、区間長の短いものから見ていき、その区間内で最大で何個区間を包含できるか？のDPをすれば良い。

そのDPを計算する時のイメージとしては次の図の通り。

： 右端がi以下の区間のみを見た時の最大値

として区間を昇順に並び替えて左から見ていくと、これまでのDPの計算結果から線形時間でが計算できて、区間Iの右端まで計算した最大値をとすると と更新可能。

番兵として最大長の区間を入れておくと最適解には必ずその区間は選ばれるので、 が答えとなり実装が楽になる。

実装

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
typedef long long int ll;

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int q; cin >> q;
    while(q--){
        int n; cin >> n;
        vector<array<int,2>> v(n);
        vector<int> z;
        for(int i=0;i<n;i++){
            cin >> v[i][0] >> v[i][1];
            v[i][1]++;
            z.push_back(v[i][0]);
            z.push_back(v[i][1]);
        }
        sort(z.begin(), z.end());
        z.erase(unique(z.begin(), z.end()),z.end());
        int m=z.size();
        for(int i=0;i<n;i++){
            for(int j=0;j<2;j++){
                v[i][j]=lower_bound(z.begin(), z.end(),v[i][j])-z.begin();
            }
        }
        // sort them in increasing order by length
        sort(v.begin(), v.end(),[](auto i,auto j){
            return i[1]-i[0]<j[1]-j[0];
        });
        v.push_back({0,m-1});
        vector<int> dp(n+1);
        vector<int> dpx(m);
        for(int i=0;i<=n;i++){
            int netx=0;
            int prebest=0;
            for(int j=0;j<m;j++){
                dpx[j]=0;
            }
            for(int j=0;j<i;j++){
                if(v[i][0]<=v[j][0]&&v[j][1]<=v[i][1]){
                    while(netx<=v[j][0]){
                        prebest=max(prebest,dpx[netx++]);
                    }
                    dpx[v[j][1]]=max(dpx[v[j][1]],prebest+dp[j]);
                }
            }
            while(netx<=v[i][1]){
                prebest=max(prebest,dpx[netx++]);
            }
            dp[i]=prebest+1;
            if(i==n)break;
            // insertion sort
            for(int j=i-1;j>=0&&v[j+1]<v[j];j--){
                swap(v[j+1],v[j]);
                swap(dp[j+1],dp[j]);
            }
        }
        printf("%d\n",dp[n]-1);
    }
}