ゆらのふなびと

競プロ, Python, C++

ABC038 D - プレゼント

問題

i 個の数の組 (w_i, h_i) が与えられる。これらから自由に選んで並べてw, hともに狭義単調増加な列を作るとき、その最大の長さは?

制約

  • 1 <= N <= 105
  • 1 <= w_i <= 105
  • 1 <= h_i <= 105

解法1: LIS

まず、入力をwの昇順にソートします。すると、以下の制約を満たしながらhを選ぶときの、その最大の長さを求めればよいことになります。

  • 制約1: hが狭義単調増加
  • 制約2: wが同じペアからは高々1つしかとらない(wが狭義単調増加であるための条件)

制約1からはLISの香りがします。普通にやると制約2を破ってしまうのですが、ソートの時に、hについては降順になるようにしておくと制約2も守られます。

誤解法として、wの昇順にソートしたあと、hが同じペアからはhが最小のもののみ選べばよいのでは?というのがあります。これは嘘で、以下のような反例があります。({(1, 1), (2, 1)} はとれないが {(1, 1), (2, 2)} はとれる)

3
1 1
2 1
2 2

wの昇順→(wが同じペアの中では)hの降順にソートすれば、どの要素も削除することなく、また同じwから複数のhを取ることなくLISを求められます。

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
 
    int N;
    cin >> N;
    vector<P> v;
    rep(i, N) {
        int w, h;
        cin >> w >> h;
        v.emplace_back(P(w, -h));
    }
 
    sort(all(v));
 
    const int INF = 1e9;
    vector<int> c(N + 1, INF);
    c[0] = -INF;
    rep(i, N) {
        int l = 0;
        int r = N + 1;
        int cand = -v[i].second;
        while (r - l > 1) {
            int m = (l + r) / 2;
            if (c[m] < cand) {
                l = m;
            } else {
                r = m;
            }
        }
        c[l + 1] = cand;
    }
 
    rrep(i, c.size()) {
        if (c[i] < INF) {
            cout << i << endl;
            return 0;
        }
    }
 
}

解法2: SegTree

解説を見て、セグ木でも実装してみました。(りんごさんのセグ木解説がとてもわかりやすかったのでぜひ見ましょう↓)

www.nicovideo.jp

LISはにぶたんで解くよりこっちの方が直感的かもしれない。

// 本問では、
// * 0で初期化
// * updateはもともと入っている値とのmax
class SegTreeMax {
private:
    int init_val = 0;
    int n;  // width of bottom
    vector<int> dat;

public:
    SegTreeMax(int _n) {
        n = 1;
        while (n < _n) n *= 2;
        dat.clear();
        dat.resize(2 * n - 1, init_val);
    }

    void update(int k, int a) {
        k += n - 1;
        dat[k] = max(dat[k], a);    // <---!!!!!!!
        while (k > 0) {
            k = (k - 1) / 2;
            dat[k] = max(dat[2 * k + 1], dat[2 * k + 2]);
        }
    }

    // get min value in [a, b)
    // dat[k] corresponds to [l, r)
    int query(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) return init_val;
        if (a <= l && r <= b) return dat[k];
        return max(query(a, b, k * 2 + 1, l, (l + r) / 2), query(a, b, k * 2 + 2, (l + r) / 2, r));
    }

    int query(int a, int b) { return query(a, b, 0, 0, n); }

};

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int N;
    cin >> N;
    vector<P> v;
    rep(i, N) {
        int w, h;
        cin >> w >> h;
        v.emplace_back(P(w, -h));
    }

    // wの昇順 -> hの降順 でソート (segtree更新時に、同じhから複数取らないようにするため)
    sort(all(v));

    const int MAX = 100010;
    SegTreeMax seg(MAX);    // dp[h] = 一番外側の箱の高さがhのときの、箱の最大数
    rep(i, N) {
        int h = -v[i].second;
        // dp[h] = max{dp[j] | j in [0, h)} + 1
        seg.update(h, seg.query(0, h) + 1);
    }

    cout << seg.query(0, MAX) << endl;
}

セグ木の可能性を感じた問題でした。