ABC038 D - プレゼント
問題概要
解く前に考えていたこと
・AOJのマトリョーシカと非常に似ている。
・ただし、この問題は制約がで解は部分点しか取れない。
・LISであることは間違えないので、比較関数を書き換えて蟻本にあるのLISを書くがWA
・途中でpair型dpを更新していた。
正解
まず前提として、プレゼントがプレゼントの中に梱包される条件とは、
> > が成立することである。
プレゼントの順番は自由に並びかえることができるので、ソートして考えるのが良い。
を昇順にソートして に関してLISを考えればうまくいきそう。
以下,二分探索で、番目の要素の更新位置を探す解法を考える。
・番目の要素でLISの配列を上書きする場合を考える。ただし、上書きされる要素は番目()とする。
・このとき、が成り立っていると、となっているため、上書きできない。(直感的に説明すると、番目の要素の方が番目の要素より条件が厳しい)
逆に言えば、のときとなっていれば、通常通り更新することができる。
追記
6/10 別解で解いたので、その解法を載せる.
通常のLISと同じく、lower_boundを用いて更新していく(ただし、今回はpair型のdp)。
更新する位置は、以上の要素がある部分である。
さて、この問題でより真に大きいとは、 && が成り立つことである。
さらに, 以上とは、 or となる。なので、適当に二分探索して置き換える位置を探す。
この定義を採用すると、同値のまたはの更新時に厄介なことになる。よって最初の同じく、比較関数をよしなにしてソートすること。
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; }