Pythonで最初のN個の自然数の順列から、中央値がMとなる部分配列の個数を求める方法

問題の概要

最初のN個の自然数の順列を並べ替えた配列Aと整数M（ただし M ≤ N）が与えられたとします。このとき、中央値がMとなる部分配列（連続する要素からなる部分列）の個数を求めるのが本記事の目的です。

なお、ここでの中央値とは、数列を昇順にソートした際に中央に位置する要素の値を指します。長さが偶数の数列については、中央に並ぶ2つの要素のうち左側（小さい方）を採用します。

例として、入力が A = [3, 5, 6, 4, 2]、M = 5 の場合を考えてみましょう。条件を満たす部分配列は [3, 5, 6]、[5]、[5, 6]、[5, 6, 4] の4つであるため、答えは 4 となります。

解法のポイント：累積バランスの活用

すべての部分配列を総当たりで調べると計算量が膨大になってしまいます。そこで、各要素を次のように数値化し、「累積バランス」という考え方を用いることで線形時間 O(N) で解けます。

• M より小さい要素 → −1
• M より大きい要素 → +1
• M 自身 → 0（バランスに影響しない）

部分配列の中央値がMになるための条件は次のとおりです。

• 長さが奇数の場合：「Mより大きい要素の数」−「Mより小さい要素の数」＝ 0
• 長さが偶数の場合（左側の中間要素がMとなる）：同じ差 ＝ +1

つまり、差が 0 または 1 であり、かつ部分配列がMを含んでいることが条件になります。この性質を利用すると、ハッシュマップ（辞書）に「Mより前に現れた累積バランスの出現回数」を記録しておき、M以降の位置では「現在の累積バランス」と「その値から1を引いたもの」に一致する過去のバランスを探せばよいことが分かります。

アルゴリズムの手順

1. n := 配列 arr のサイズとする
2. my_map := 新しいマップ（辞書）を作成し、my_map[0] := 1 で初期化する
3. has := False、add := 0、result := 0 と初期化する
4. i を 0 から n−1 まで繰り返す：
   
   • arr[i] < m なら add := add − 1
   • そうでなく arr[i] > m なら add := add + 1
   • arr[i] が m と等しければ has := True とする
   • has が True の場合（Mを通過した後）：
     
     • add が my_map に存在すれば、result := result + my_map[add]
     • add − 1 が my_map に存在すれば、result := result + my_map[add − 1]
   • それ以外の場合（Mより前の区間）：my_map[add] := （既存の値、なければ0）＋ 1
5. result を返す

実装例（Python）

以下の実装を見ると、仕組みがより理解しやすくなります。

def solve(arr, m):
    n = len(arr)
    my_map = {}
    my_map[0] = 1
    has = False
    add = 0
    result = 0
    for i in range(n):
        if (arr[i] < m):
            add -= 1
        elif (arr[i] > m):
            add += 1
        if (arr[i] == m):
            has = True
        if (has):
            if(add in my_map):
                result += my_map[add]
            if add-1 in my_map:
                result += my_map[add - 1]
        else:
            my_map[add] = my_map.get(add, 0) + 1
    return result

arr = [3, 5, 6, 4, 2]
m = 5
print(solve(arr, m))

入力

[3, 5, 6, 4, 2], 5

出力

4

計算量について

時間計算量は O(N)、空間計算量は O(N) です。配列を一度だけ走査すればよく、各ステップの処理もハッシュマップへの参照・更新のみで済むため、大規模な入力に対しても非常に効率的に動作します。