C++で解く配列の順列問題：別の配列より大きくなる位置を最大化する方法

このチュートリアルでは、2つの配列 A と B が与えられたとき、A[i] > B[i] となるインデックスの数が最大になるように配列Aを並べ替えた順列を出力する方法を解説します。まずは具体例を見てみましょう。

入力:
A = [12, 22, 41, 13]
B = [1, 20, 10, 12]
出力: 12, 22, 41, 13

入力:
A = [2, 5, 9, 7]
B = [1, 12, 4, 54]
出力: 2 7 5 9

※ 条件を満たす答えが複数存在する場合は、そのうちのどれか1つを出力すれば問題ありません。

この問題では、A[i] が B[i] を上回るインデックスの数を最大化する必要があるため、貪欲法（グリーディ法）を用いて解いていきます。

解法のアプローチ

まず、両方の配列を昇順にソートします。そのうえで、配列Bの各要素に対して「その値より大きい A[i]」を貪欲に対応付け、見つかった要素を答えの配列に配置していきます。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
int main(){
    int A[] = { 2, 5, 9, 7 };
    int B[] = { 1, 12, 4, 54 };
    int n = sizeof(A) / sizeof(int); // 配列のサイズ
    vector<pair<int, int> > A_pair, B_pair;
    /************** 要素と元のインデックスを紐付ける **************/
    for (int i = 0; i < n; i++)
        A_pair.push_back({A[i], i});
    for (int i = 0; i < n; i++)
        B_pair.push_back({B[i], i});
    /*************************************************************/
    /******************* ペアのベクトルをソートする ******************/
    sort(A_pair.begin(), A_pair.end());
    sort(B_pair.begin(), B_pair.end());
    int i = 0, j = 0, ans[n];
    memset(ans, -1, sizeof(ans)); // 全要素を -1 で初期化
    vector<int> remaining; // B のどの要素より大きくできない A の要素を格納する
    while (i < n && j < n) {
        // 配列はソート済みなので、現在の位置で B_pair より小さい値なら、
        // 残りのどの B の要素に対しても勝てない。
        // そのため、そのような要素は remaining へ、勝てる要素は ans へ格納する
        if (A_pair[i].first > B_pair[j].first) {
            ans[B_pair[j].second] = A_pair[i].first;
            i++;
            j++;
        }
        else {
            remaining.push_back(i);
            i++;
        }
    }
    j = 0;
    for (int i = 0; i < n; ++i){
        // まだ -1 のままの位置には、remaining に残った要素を詰める
        if (ans[i] == -1){
            ans[i] = A_pair[remaining[j]].first;
            j++;
        }
    }
    for (int i = 0; i < n; i++) // 答えの出力
        cout << ans[i] << " ";
    return 0;
}

実行結果

2 7 5 9

コードの解説

この実装では、まずすべての要素を「値と元のインデックス」のペアとして保存します。これにより、ソートを行った後でも、その要素がもともとどの位置に属していたのかという情報を失いません。

続いて、ペアのベクトルを両方ともソートし、2つの配列を先頭から同時に走査しながら貪欲に答えを構築していきます。A_pair の現在の値が B_pair の現在の値より大きければ、その値を B_pair の元のインデックス位置に格納します。逆に、等しいか小さい場合は、両ベクトルがソート済みであることを利用すると、この A_pair の値は残りのどの B の要素に対しても大きくなれない、つまりもう使えないことが分かります。そこで、その要素のインデックスを remaining ベクトルに記録しておきます。

最後に、答えの配列の中でまだ埋まっていない位置（初期値 -1 のままの箇所）を、remaining に残しておいた要素で順番に埋め、結果を出力して完了です。

まとめ

今回は、別の配列との比較で A[i] > B[i] となる位置の数を最大化する配列の順列を見つける問題を取り上げました。ソートと貪欲法を組み合わせたC++プログラムと、その考え方についても詳しく解説しました。同じロジックは、C、Java、Python など他のプログラミング言語でも容易に実装できます。このチュートリアルが皆さんの学習のお役に立てば幸いです。