【C++】x^y > y^x となる配列内のペア（x, y）の数を効率的に求める方法

正の整数からなる2つの配列 X と Y が与えられます。このとき、x^y > y^x を満たすペア（x, y）の総数を求めるのが本記事のテーマです。ここで、x は配列 X の要素、y は配列 Y の要素を表します。

例として、X = [2, 1, 6]、Y = [1, 5] の場合を考えてみましょう。このとき出力は 3 になります。条件を満たすペアは (2, 1)、(2, 5)、(6, 1) の3つだからです。

効率的な解法のポイント

すべての組み合わせを総当たりで調べる方法もありますが、計算量が O(m × n) となり、配列が大きくなると非効率です。そこで役立つのが、次の数学的な性質です。

「y > x であれば、x^y > y^x が成り立つ」――ただし、いくつか例外があります。

この性質と例外処理を組み合わせることで、ソートと二分探索を使った高速なアルゴリズムが実現できます。主なケースは以下の通りです。

• x = 0 の場合： 0^y > y^0 となることはないため、条件を満たすペアは存在しません。
• x = 1 の場合： 1^y > y^1 が成り立つのは y = 0 のときだけです。したがって、配列 Y に含まれる 0 の個数をカウントします。
• x ≥ 2 の場合： 基本的に「y > x」を満たす y はすべて条件に合致し、さらに y = 0 と y = 1 も常に条件を満たします。ただし例外として、x = 2 のときは y = 3 と y = 4 を除外する必要があります（2^3 = 8 < 3^2 = 9、2^4 = 16 = 4^2 = 16 となるため）。逆に x = 3 のときは、例外的に y = 2 も条件を満たします（3^2 = 9 > 2^3 = 8 となるため）。

アルゴリズムの手順

1. まず、配列 Y を昇順にソートします。
2. 配列 X の各要素 x について、配列 Y の中で「x より大きい値が最初に現れる位置」を二分探索で求めます。C++ では標準ライブラリの upper_bound() 関数を使うと簡潔に実装できます。
3. 見つかった位置以降の要素はすべて条件を満たすため、その個数を答えに加算します。

あらかじめ Y に含まれる 0〜4 の出現回数を記録しておけば、例外処理も定数時間で行えます。全体の計算量は O((m + n) log n) となり、総当たり法よりも大幅に高速です。

C++での実装例

#include <iostream>
#include <algorithm>
using namespace std;

// x とペアになる Y の要素数を数える関数
int count(int x, int Y[], int n, int no_of_y[]) {
    // x が 0 の場合は条件を満たすペアなし
    if (x == 0)
        return 0;
    // x が 1 の場合は y = 0 のみ有効
    if (x == 1)
        return no_of_y[0];
    // Y の中で x より大きい最初の位置を二分探索で取得
    int* index = upper_bound(Y, Y + n, x);
    int ans = (Y + n) - index;
    // y = 0 と y = 1 は常に条件を満たす
    ans += (no_of_y[0] + no_of_y[1]);
    // x = 2 の場合は y = 3, 4 を除外
    if (x == 2)
        ans -= (no_of_y[3] + no_of_y[4]);
    // x = 3 の場合は y = 2 も条件を満たす
    if (x == 3)
        ans += no_of_y[2];
    return ans;
}

// 条件を満たすペアの総数を求める関数
int howManyPairs(int X[], int Y[], int m, int n) {
    // Y に含まれる 0〜4 の出現回数を記録
    int no_of_y[5] = {0};
    for (int i = 0; i < n; i++)
        if (Y[i] < 5)
            no_of_y[Y[i]]++;
    // 配列 Y をソート
    sort(Y, Y + n);
    int total_pairs = 0;
    // 各 x に対して有効な y の数を加算
    for (int i = 0; i < m; i++)
        total_pairs += count(X[i], Y, n, no_of_y);
    return total_pairs;
}

int main() {
    int X[] = {2, 1, 6};
    int Y[] = {1, 5};
    int m = sizeof(X)/sizeof(X[0]);
    int n = sizeof(Y)/sizeof(Y[0]);
    cout << "合計ペア数: " << howManyPairs(X, Y, m, n);
}

実行結果

合計ペア数: 3

まとめ

このように、「y > x ならば x^y > y^x」という性質と少数の例外処理を組み合わせることで、配列のソートと二分探索だけで問題を効率的に解くことができます。総当たり法の O(m × n) に対し、本手法は O((m + n) log n) と計算量を大幅に抑えられるため、大きなデータセットでも高速に動作するのが魅力です。