予鈴

アウトプットとメモ書きの中間みたいな記事がたくさん出ます。

ABC038 D - プレゼント

問題概要

D - プレゼント

解く前に考えていたこと

AOJのマトリョーシカと非常に似ている。
・ただし、この問題は制約がN \leq10^5O(N^2)解は部分点しか取れない。
・LISであることは間違えないので、比較関数を書き換えて蟻本にある N log N のLISを書くがWA
・途中でpair型dpを更新していた。

正解

まず前提として、プレゼントaがプレゼントbの中に梱包される条件とは、
 w_b>w_a \land h_b > h_a  が成立することである。
プレゼントの順番は自由に並びかえることができるので、ソートして考えるのが良い。
wを昇順にソートして h に関してLISを考えればうまくいきそう。
以下,二分探索で、 i番目の要素の更新位置を探す解法を考える。

i番目の要素でLISの配列を上書きする場合を考える。ただし、上書きされる要素はj番目( j < i)とする。
・このとき、w_i = w_jが成り立っていると、h_i < h_jとなっているため、上書きできない。(直感的に説明すると、j番目の要素の方がi番目の要素より条件が厳しい)

逆に言えば、w_i = w_jのときh_i > h_jとなっていれば、通常通り更新することができる。

追記

6/10 別解で解いたので、その解法を載せる.
通常のLISと同じく、lower_boundを用いて更新していく(ただし、今回はpair型のdp)。
更新する位置は、 (h_i,w_i)以上の要素がある部分である。
さて、この問題で (h_i,w_i)より真に大きいとは、 h_i < h_j &&  w_i <  w_jが成り立つことである。
さらに,  (h_i,w_i)以上とは、 h_i \leq  h_j or  w_i \leq  w_j となる。なので、適当に二分探索して置き換える位置を探す。
この定義を採用すると、同値の w または hの更新時に厄介なことになる。よって最初の同じく、比較関数をよしなにしてソートすること。

lower_boundといっておきながら普通の二分探索の理由は、また比較関数を書き換えないと行けないので。(比較関数を書き換えたver)

#include<bits/stdc++.h>
using namespace std;
using Int = long long;
constexpr Int inf =1e18;
template<class F, class T>
auto  minimize(T imin,T imax,F &f){
    while(imax - imin > 1){
        T mid = imin + (imax - imin)/2;
        if(f(mid)) imax = mid;
        else imin = mid;
    }
    return imax;
}
int main(){
    int N; cin >> N;
    vector<pair<Int,Int>>v(N);
    for(auto& p : v)
        cin >> p.first >> p.second;
    sort(v.begin(),v.end(),[&](const auto& l, const auto& r){
        if(l.first == r.first) return l.second > r.second;
        return l.first < r.first;
    });
    pair<Int,Int>p;
    vector<pair<Int,Int>>dp(N,make_pair(inf,inf));
    auto f = [&](int mid){
        return dp[mid].first >= p.first or dp[mid].second >= p.second;
    };
    for(int i = 0; i < N; ++i){
        p = v[i];
        int id = minimize(-1,N - 1,f);
        dp[id] = p;
    }
    cout << count_if(dp.begin(), dp.end(), [&](auto p){
        return p != make_pair(inf,inf);
    }) <<  endl;
}