C++で列の合計が行の合計より大きいペアの個数を数える方法

問題の概要

N×N のサイズの行列が与えられたとき、「列 j の要素の合計が行 i の要素の合計よりも大きい」という条件を満たすインデックスのペア (i, j) の総数を求めるのが目標です。

この問題は、行列を一度走査して各行・各列の要素の合計をあらかじめ計算しておくことで、効率よく解くことができます。

まず、各行の要素の合計を配列 rowsum[N] に、各列の要素の合計を配列 colsum[N] にそれぞれ格納します。

その後、rowsum[i] と colsum[j] のすべての組み合わせについて colsum[j] > rowsum[i] が成り立つかどうかを調べ、条件を満たすペアのカウントを増やしていきます。

それでは、具体例を使って理解しましょう。

具体例

例1

入力: matrix = {
    { 1,2,0,1},
    { 3,3,0,2},
    { 1,3,0,2},
    { 3,0,0,2}
};

出力 − 有効なペアの個数 − 9

説明 −

Rowsum[0]= 1+2+0+1=5   Colsum[0]= 1+3+1+3=8
Rowsum[1]= 3+3+0+2=8   Colsum[1]= 2+3+3+0=8
Rowsum[2]= 1+3+0+2=6   Colsum[2]= 0+0+0+0=0
Rowsum[3]= 3+0+0+2=5   Colsum[3]= 1+2+2+2=7

rowsum[i] < colsum[j] を満たすペア (i,j):
(0,0), (0,1), (0,3), (2,0), (2,1), (2,3), (3,0), (3,1), (3,3)

例2

入力: Arr[]= { {1,1,1}, {1,1,1}, {1,1,1} }  N=3

出力 − 有効なペアの個数 − 0

説明 −

Rowsum[0]= 1+1+1=3   Colsum[0]= 1+1+1=3
Rowsum[1]= 1+1+1=3   Colsum[1]= 1+1+1=3
Rowsum[2]= 1+1+1=3   Colsum[2]= 1+1+1=3

rowsum[i] < colsum[j] を満たすペアは存在しません

アルゴリズム（プログラムで使うアプローチ）

• ランダムな整数で初期化された整数型配列 Arr[] を用意します。
• 配列 Arr[] の長さを保持する変数 n を宣言します。
• 関数 countPairs(int arr[][3], int n) は、配列とその長さを引数として受け取り、条件を満たす有効なペアの個数を返します。
• 行の合計を格納する rowsum[n] と、列の合計を格納する colsum[n] の2つの配列を用意します。
• 行列を走査しながら arr[i][j] を rowsum[i] および colsum[j] に加算し、行 i と列 j の合計を計算します。
• 続いて、2重の for ループを使って rowsum[] と colsum[] を走査します。
• colsum[j] > rowsum[i] が成立した場合は、カウントを1つ増やします。
• 最後にカウントを結果として返します。

C++実装例

#include <bits/stdc++.h>
using namespace std;
int countPairs(int arr[][3], int n){
    // ペアの個数
    int count = 0;
    int rowsum[n]={0};
    int colsum[n]={0};
    int i,j;
    for (i = 0; i < n; i++){
        for (j = 0; j < n; j++){
            rowsum[i]+=arr[i][j];
            colsum[j]+=arr[i][j];
        }
    }
    for(i=0;i<n;i++){
        for(j=0;j<n;j++)
            if(colsum[j]>rowsum[i])
                { count++; }
    }
    return count;
}
int main(){
    int Arr[][3] = { {1,3,5},{2,4,6},{3,5,7} };
    int side=3;
    cout <<endl<<"ペアの個数 : "<< countPairs(Arr, side);
    return 0;
}

出力

上記のコードを実行すると、次のような出力が得られます −

ペアの個数 : 4

計算量について

このアルゴリズムでは、行列の全要素を一度走査して行・列ごとの合計を求める処理に O(N²)、ペアの判定にも O(N²) の時間がかかるため、全体の時間計算量は O(N²) となります。また、補助配列 rowsum と colsum の分だけ、空間計算量は O(N) です。前計算により毎回行・列の合計を再計算せずに済むため、非常に効率的な手法と言えます。