【C++解説】小さい箱を大きい箱に入れた後に「見える箱」の数を求めるアルゴリズム

この記事では、各箱のサイズが格納された配列が与えられ、「大きい箱が小さい箱の2倍以上のサイズであれば、その小さい箱を大きい箱の中に収めることができる」という条件のもとで、最終的に外から見える箱の数を求める問題を解いていきます。

問題の例

入力 : arr[] = { 1, 3, 4, 5 }
出力 : 3
サイズ1の箱を、サイズ3の箱の中に入れます。

入力 : arr[] = { 4, 2, 1, 8 }
出力 : 1

1つ目の例では、サイズ1の箱をサイズ3の箱に収められるため、残る見える箱は3つになります。2つ目の例では、箱同士の組み合わせ次第ですべての箱を入れ子にできるため、最終的に見える箱は1つだけです。

解法のアプローチ

この問題に対する基本的な方針は以下の通りです。

まず、配列を昇順にソートします。その後、要素を順番に処理しながらキュー（queue）を使って管理していきます。具体的には、現在の要素がキューの先頭要素の2倍以上であるかどうかを判定します。もし2倍以上であれば、先頭の箱は現在の箱の中に収められるということなので、キューの先頭を取り除き（pop）ます。そして、現在の要素をキューに追加（push）します。

すべての要素を処理し終えたときのキューのサイズが、答えとなる「見える箱の数」です。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
int main(){
    int arr[] = { 1, 2, 3, 4, 5, 6 }; // 箱のサイズを格納した配列
    int n = sizeof(arr) / sizeof(arr[0]); // 配列のサイズ
    queue<int> q;
    sort(arr, arr + n); // 配列をソート
    q.push(arr[0]); // 最も小さい要素をキューに入れる
    for (int i = 1; i < n; i++) { // 配列を走査
        int curr = q.front(); // キューの先頭要素
        if (arr[i] >= 2 * curr) // 現在の箱が先頭の箱の2倍以上なら、
                                // 先頭の箱は中に収められるので取り除く
            q.pop();

        q.push(arr[i]); // 現在の要素をキューに追加
    }
    cout << q.size() << "\n";; // 答え（見える箱の数）
    return 0;
}

出力結果

3

このコードでは、配列 { 1, 2, 3, 4, 5, 6 } が与えられた場合、出力は 3 となります。実際、1を2に、2を4に収めることができるため、最終的に見える箱は3つになるのです。

まとめ

本記事では、箱を入れ子にした後に見える箱の数を求める問題を取り上げました。ソートとキューを組み合わせたシンプルな貪欲法（グリーディ法）のアプローチにより、効率よく解くことができます。同じロジックはC言語、Java、Pythonなど他のプログラミング言語でも同様に実装可能です。競技プログラミングやアルゴリズムの学習の参考にぜひ活用してください。