C++でN個の範囲から生成される数列のk番目の要素を求める方法

問題の概要

この問題では、区間 L〜R を持つ整数の範囲が N 個、二次元配列 range[N][2] として与えられ、さらに整数値 k が渡されます。求めるのは、与えられた N 個の範囲から生成される数列の中の k 番目の要素です。

具体例で問題を確認してみましょう。

入力 : ranges[][] = {{1, 3}, {5, 7}}, k = 4
出力 : 5

説明:

生成される数列は {1, 2, 3, 5, 6, 7}
4番目の要素は 5 になります。

解法①:配列に全要素を構築するシンプルな方法

もっとも直感的な解決方法は、指定された範囲に含まれるすべての整数を順に配列へ格納していき、その配列の k 番目の要素を返すというものです。

実装例(C++)

#include <iostream>
using namespace std;

int findKthSmallestEleSeries(int n, int k, int range[][2]){
    int rangeVal[10000];
    int rangeSize = 0;
    for(int i = 0; i < n; i++){
        for(int j = range[i][0]; j <= range[i][1]; j++){
            rangeVal[rangeSize] = j;
            rangeSize++;
        }
    }
    return rangeVal[k-1];
}

int main(){
    int range[][2] = {{1, 3}, {5, 8}};
    int n = 2;
    int k = 4;
    cout << k << "番目の要素は " << findKthSmallestEleSeries(n, k, range);
    return 0;
}

実行結果

4番目の要素は 5

この方法は分かりやすい反面、範囲が大きくなると配列のサイズが膨らみ、メモリ不足に陥る恐れがあります。そのため、全要素を事前に格納しておかない、より効率的なアプローチが必要になります。

解法②:二分探索と累積カウント配列を使う効率的な方法

より優れた解決策が、二分探索とカウント配列(累積和)を組み合わせるアプローチです。カウント配列 count[] には、各時点までに含まれる整数の累積個数を格納します。つまり count[i] は「i 番目の範囲までの要素の総数」を表します。

処理の手順は次の通りです。

• まず累積カウント配列を構築する
• 二分探索により、k 番目に小さい値が属する範囲(何番目の範囲か)を特定する
• その範囲内で再度二分探索を行い、k 番目の位置に対応する実際の値を求める

実装例(C++)

#include <iostream>
using namespace std;

int findKthSmallestEleSeries(int n, int k, int range[][2]){
    // 累積カウント配列の構築
    int start = 1;
    int end = n;
    int count[n + 1];
    count[0] = 0;
    for (int i = 0; i < n; i++)
        count[i + 1] = count[i] + (range[i][1] - range[i][0]) + 1;

    // k番目の要素が属する範囲を二分探索で特定
    int index = -1;
    int mid;
    while (start <= end) {
        mid = (start + end) / 2;
        if (count[mid] > k) {
            index = mid;
            end = mid - 1;
        }
        else if (count[mid] < k)
            start = mid + 1;
        else {
            index = mid;
            break;
        }
    }

    // 特定した範囲内でk番目の値を求める
    start = range[index - 1][0];
    end = range[index - 1][1];
    int indexK = k - count[index - 1];
    while (start <= end) {
        mid = (start + end) / 2;
        if ((mid - range[index - 1][0]) + 1 == indexK) {
            return mid;
        }
        else if ((mid - range[index - 1][0]) + 1 > indexK)
            end = mid - 1;
        else
            start = mid + 1;
    }
    return -1;
}

int main(){
    int range[][2] = {{1, 3}, {5, 8}};
    int n = 2;
    int k = 4;
    cout << k << "番目の要素は " << findKthSmallestEleSeries(n, k, range);
    return 0;
}

実行結果

4番目の要素は 5

計算量の比較とまとめ

解法①では、時間計算量・空間計算量の両方が範囲に含まれる全要素数に比例するため、範囲が広い場合は非現実的になります。一方、解法②では範囲の個数 n に対して O(n log R)(R は最大の範囲幅)程度で処理でき、全要素をメモリ上に展開する必要がありません。

そのため、実際の開発や競技プログラミングにおいて大きな範囲が扱われる場合は、二分探索と累積カウントを活用した解法②の採用が推奨されます。