C++で解くロシア人形の封筒問題 ― ソートと二分探索によるLISの活用

問題概要

高さと幅のペアで表される複数の封筒が与えられるとします。ある封筒が別の封筒の中に入ることができるのは、その封筒の高さと幅の両方が相手の封筒よりも厳密に小さい場合のみです。この条件下で、封筒を最大で何重に入れ子にできるかを求めるのが本問題です。

例えば、入力が [[5,5], [6,4], [6,8], [2,3]] の場合、出力は 3 になります。最も小さい封筒は [2,3] であり、その中に [5,5]、さらにその中に [6,8] を入れることで、合計3枚の封筒を入れ子にできるためです。

解法のアプローチ

この問題は、ソートと最長増加部分列（LIS: Longest Increasing Subsequence）を二分探索で求めるアルゴリズムを組み合わせることで、効率的に解くことができます。具体的な手順は以下の通りです。

• 配列 v を高さを基準にソートします。高さが同じ場合は、幅を降順で比較します
• v のサイズが 0 の場合は、0 を返します
• 結果を格納する配列 ret を定義します
• i を 0 から v のサイズ未満まで1ずつ増やしながら、以下の処理を繰り返します
  • temp := v[i] とし、x := temp[1]（現在の封筒の幅）を取得します
  • low := 0、high := ret のサイズ、curr := 0 で初期化します
  • low ≤ high の間、次の二分探索を繰り返します
    • mid := low + (high − low) / 2 とします
    • ret[mid] < temp[1] の場合：curr := mid + 1、low := mid + 1 とします
    • それ以外の場合：high := mid − 1 とします
  • curr < 0 の場合は、以降の処理をスキップして次の反復へ進みます
  • curr ≥ ret のサイズの場合は、ret の末尾に temp[1] を追加します
  • それ以外の場合は、ret[curr] := temp[1] として値を更新します
• 最後に ret のサイズを返します

なぜ同じ高さでは幅を降順にソートするのか

高さが等しい封筒同士は、幅がどうであれ互いに入れ子にすることができません。そこで、同じ高さのグループ内では幅を降順に並べます。こうすることで、幅に関する最長増加部分列（LIS）を求めた際に、同一の高さを持つ封筒が誤って連続して選ばれることを防げます。この工夫によって、元の二次元の問題を「幅のみのLIS問題」へ帰着させることができます。

C++による実装例

それでは、理解を深めるために以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    static bool cmp(vector <int> a, vector <int> b){
        if(a[0] == b[0])return a[1] > b[1];
        return a[0] < b[0];
    }
    int maxEnvelopes(vector<vector<int>>& v) {
        sort(v.begin(), v.end(), cmp);
        if(v.size() == 0)return 0;
        vector <int> ret;
        for(int i = 0; i < v.size(); i++){
            vector <int> temp = v[i];
            int x = temp[1];
            int low = 0;
            int high = ret.size() - 1;
            int curr = 0;
            while(low <= high){
                int mid = low + (high - low) / 2;
                if(ret[mid] < temp[1]){
                    curr = mid + 1;
                    low = mid + 1;
                }else{
                    high = mid - 1;
                }
            }
            if(curr < 0) continue;
            if(curr >= (int)ret.size()){
                ret.push_back(temp[1]);
            }else{
                ret[curr] = temp[1];
            }
        }
        return ret.size();
    }
};
main(){
    Solution ob;
    vector<vector<int>> v = {{5,5}, {6,4}, {6,8}, {2,3}};
    cout << (ob.maxEnvelopes(v));
}

入力

{{5,5}, {6,4}, {6,8}, {2,3}}

出力

3

計算量

このアルゴリズムの時間計算量は、ソートに O(N log N)、各封筒に対する二分探索に O(log N) ずつかかるため、全体で O(N log N) です。また、結果を保持する配列 ret の分だけ空間を必要とし、空間計算量は O(N) となります。