C++で「pが配列にq回以上出現し、qがp回以上出現する」ペア（p, q）を数える方法

問題の概要

正の整数からなる配列が与えられます。この問題のゴールは、配列arr[]の要素から選んだペア（p, q）のうち、「pが配列内に少なくともq回出現し、かつqが配列内に少なくともp回出現する」という条件を満たすものの総数を求めることです。
具体例を見ながら理解を深めましょう。

入出力例

例1

入力: int arr[] = { 3, 3, 3, 5, 5, 6, 6 }

出力: 条件を満たすペアの数 ― 1

説明: 配列内で条件を満たす有効なペアは(3, 3)のみです。値3は配列内にちょうど3回出現しているためです。有効なペアはこの1つだけなので、答えは1になります。

例2

入力: int arr[] = { 3, 3, 3, 3, 3, 5, 5, 5, 6, 6 }

出力: 条件を満たすペアの数 ― 3

説明: 有効なペアは(3, 3)、(5, 5)、(3, 5)の3つです。値3は配列内に5回、値5は3回出現しています。したがって、有効なペアは3つとなり、答えは3になります。

本プログラムで採用するアプローチ

• 整数要素からなる配列を入力として受け取り、配列のサイズを計算した上で、以降の処理を行う関数にデータを渡します。
• pとqの出現回数を格納するための一時変数countを宣言します。
• vector型の変数vecと、unordered_map型の変数umを作成します。
• 0から配列のサイズまでのFORループを開始します。
• ループ内ではum[arr[i]]の値を1増やし、その値が1になった場合（要素が最初に出現した場合）はarr[i]をvecに追加します。
• 続いて、0からvecのサイズまでの別のFORループを開始します。um[vec[i]] < vec[i]であればcontinueし、等しい場合はcountを1増やします。それ以外の場合もcountを1増やした上で、jをvec[i] + 1からum[vec[i]]まで動かす内側のループを実行します。
• jのループ内では、um[j] >= vec[i]を満たしていればcountを1増やします。
• countを返します。
• 結果を出力します。

アルゴリズムのポイント

この手法では、unordered_mapを使って各値の出現回数を一度の走査で集計し、重複しない値だけをvectorに記録します。その後、各一意な値について「自分自身とのペア」や「出現回数が互いの条件を満たす他の値とのペア」を効率よく数え上げます。すべての要素の組み合わせを素朴に調べる方法に比べ、探索対象を一意な値とその出現回数に限定できるため、はるかに高速に答えを求められます。

コード例

#include <bits/stdc++.h>
using namespace std;
int pair_count(int arr[], int len){
    int count = 0;
    vector<int> vec;
    unordered_map<int, int> um;
    for (int i = 0; i < len; i++){
        um[arr[i]]++;
        if (um[arr[i]] == 1){
            vec.push_back(arr[i]);
        }
    }
    for (int i = 0; i < vec.size(); i++){
        if (um[vec[i]] < vec[i]){
            continue;
        }
        else if (um[vec[i]] == vec[i]){
            count++;;
        }
        else{
            count++;
            for (int j = vec[i] + 1; j <= um[vec[i]]; j++){
                if (um[j] >= vec[i]){
                    count++;
                }
            }
        }
    }
    return count;
}
int main(){
    int arr[] = { 1, 1, 1, 5, 5, 1};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout<<"Count of pairs (p, q) such that p occurs in array at least q times and q occurs at least
p times are: "<<pair_count(arr, size);
    return 0;
}

出力

上記のコードを実行すると、以下の出力が得られます。

Count of pairs (p, q) such that p occurs in array at least q times and q occurs at least p times are: 1