C++で行列内の降順にソートされた列の数を数える方法

このチュートリアルでは、C++を使って「行列（マトリックス）の中で降順にソートされている列の数」を求めるプログラムについて解説します。

ここでは、ある行列が与えられたとき、その中から要素が降順（大きい値から小さい値へ）に並んでいる列を数えることが課題となります。

アルゴリズムの考え方

基本的なアプローチはシンプルです。各列について、下の行から上の行へ向かって隣り合う要素を順番に比較していきます。もし「上の要素が下の要素より小さい」という箇所がひとつでも見つかれば、その列は降順ではないと判断できます。最後まで問題なく確認できた列だけをカウントします。

サンプルコード

#include <bits/stdc++.h>
#define MAX 100
using namespace std;

// 降順にソートされた列を数える関数
int count_dcolumns(int mat[][MAX], int r, int c){
    int result = 0;
    for (int i = 0; i < c; i++){
        int j;
        for (j = r - 1; j > 0; j--)
            // 上の要素が下の要素より小さければ降順ではない
            if (mat[j-1][i] < mat[j][i])
                break;
        if (j == 0)
            result++;
    }
    return result;
}

int main(){
    int m = 2, n = 2;
    int mat[][MAX] = {{1, 3}, {0, 2}};
    cout << count_dcolumns(mat, m, n);
    return 0;
}

出力結果

2

コードの解説

この例では、2×2 の行列 {{1, 3}, {0, 2}} を扱っています。1 列目は 1 → 0、2 列目は 3 → 2 と、どちらも上から下へ値が減少しているため、両方の列が降順にソートされていると判定され、結果として「2」が出力されます。

外側のループが各列を走査し、内側のループがその列の要素を下の行から上の行へと比較していきます。計算量は O(r × c)、つまり行列の全要素を一度ずつ確認するだけで済むため、非常に効率的なアルゴリズムです。