C++ですべての要素がXより大きいセグメントの数を求める方法

この記事では、与えられた数列の中から、すべての要素が指定した値Xより大きいセグメント（部分配列）の個数を求める方法を解説します。

重なり合うセグメントは1回だけカウントし、隣接する2つの要素やセグメントは別々に数えないものとします。まずは、この問題の基本的な例を見てみましょう。

入力 : arr[ ] = { 9, 6, 7, 11, 5, 7, 8, 10, 3}, X = 7
出力 : 3
説明 : { 9 }, { 11 }, { 8, 10 } が X=7 より大きい要素だけを持つセグメントです

入力 : arr[ ] = { 9, 6, 12, 2, 11, 14, 8, 14 }, X = 8
出力 : 4
説明 : { 9 }, { 12 }, { 11, 14 }, { 14 } が X=8 より大きい要素だけを持つセグメントです

解決策のアプローチ

シンプルな走査による方法

この問題は、フラグのような役割を持つ変数 state を 0 で初期化し、配列を先頭から順に走査することで解けます。

具体的には、次の手順で処理を進めます。

• Xより大きい要素を見つけたら、state を 1 に設定する。
• X以下の要素を見つけた時点で、state が 1 であればカウントを1増やし、state を 0 に戻す。
• これにより、「Xより大きい要素が連続している区間（セグメント）」が終わるたびにカウントが増えていきます。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
int main (){
    int a[] = { 9, 6, 12, 2, 11, 14, 8, 14 };
    int n = sizeof (a) / sizeof (a[0]);
    int X = 8;
    int state = 0;
    int count = 0;
    // 配列を走査する
    for (int i = 0; i < n; i++){
        // 要素がXより大きいかどうかを判定
        if (a[i] > X){
            state = 1;
        }
        else{
            // stateが立っている場合
            if (state)
                count += 1;
            state = 0;
        }
    }
    // 最後のセグメントをチェック
    if (state)
        count += 1;
    cout << "すべての要素がXより大きいセグメントの数: " << count;
    return 0;
}

出力結果

すべての要素がXより大きいセグメントの数: 4

プログラムの解説

上記のプログラムでは、変数 state をスイッチのように使っています。Xより大きい要素が見つかると state を 1 に設定し、X以下の要素が見つかると 0 に戻します。そして、state が 1 から 0 に切り替わるタイミング、つまり「Xより大きい要素だけで構成されるセグメントが1つ完了した」瞬間ごとにカウントを1増やしています。

ループ終了後に state がまだ 1 のままの場合、配列の末尾までセグメントが続いていたことを意味するため、最後にもう一度カウントを増やす処理を入れています。このチェックを忘れると、配列の最後尾にセグメントがある場合に正しい答えが得られないので注意しましょう。

このアルゴリズムの計算量は、配列を一度だけ走査すればよいため O(n) となり、非常に効率的です。また、必要な補助メモリも O(1) で済みます。

まとめ

この記事では、state 変数を切り替えるシンプルな手法を使って、すべての要素がXより大きいセグメントの数を求める問題を解きました。ロジックさえ理解できれば、C言語、Java、Pythonなど、他のプログラミング言語でも同じ考え方で実装することができます。