Pythonで配列の半分以上をゼロに還元できるかどうかを判定する方法

サイズ n の正整数からなるリストと、もうひとつの正整数 m が与えられたとします。ループの各反復において、配列内のいくつかの要素の値を 1 減らし、残りの要素の値を m 増やしていくことを考えます。何回かの反復の後、リストの要素のうち半分以上をゼロにできるかどうかを判定し、可能であれば True を、不可能であれば False を返すのが目的です。

たとえば、入力が input_list = [10, 18, 35, 5, 12]、m = 4 の場合、出力は True になります。

解法のポイント：剰余（mod）に着目する

この問題を効率的に解く鍵は、「m + 1 で割った余り」に注目することです。

ある要素 x に対して、全体 t 回の反復のうち d 回だけ「−1」を適用し、残りの t − d 回は「+m」が適用されるとすると、最終的な値は x − d + m × (t − d) と表せます。これが 0 になるには d × (m + 1) = x + m × t が必要で、変形すると t ≡ x (mod m + 1) という条件が導かれます。つまり、同じタイミングで同時にゼロにできる要素同士は、m + 1 で割った余りが互いに等しいということです。

したがって、「半分以上の要素をゼロに還元できる」ことは、「ある余りのグループにリスト全体の半分以上の要素が含まれている」ことと完全に一致します。

解法の手順

1. サイズ m + 1 の頻度リスト（frequency_list）を 0 で初期化して作成します。
2. 入力リストの各要素について input_list[i] mod (m + 1) を計算し、対応するインデックスのカウントを 1 増やします。
3. 頻度リストを先頭から走査し、どれかのカウントがリストサイズの半分（n / 2）以上であれば、そこでループを抜けます。
4. 条件を満たすカウントが見つかれば True を、最後まで見つからなければ False を返します。

実装例

以下に Python での実装例を示します。

def solve(input_list, m):
    frequency_list = [0] * (m + 1)
    i = 0
    while(i < len(input_list)):
        frequency_list[(input_list[i] % (m + 1))] += 1
        i += 1
    i = 0
    while(i <= m):
        if(frequency_list[i] >= (len(input_list)/ 2)):
            break
        i += 1
    if (i <= m):
        return True
    else:
        return False

input_list = [10, 18, 35, 5, 12]
print(solve(input_list, 4))

入力

[10, 18, 35, 5, 12], 4

出力

True

動作の解説

入力例では、各要素を m + 1 = 5 で割った余りは次のようになります。

• 10 % 5 = 0
• 18 % 5 = 3
• 35 % 5 = 0
• 5 % 5 = 0
• 12 % 5 = 2

その結果、frequency_list は [3, 0, 1, 1, 0] となり、余り 0 のグループに 3 個の要素が含まれています。リストサイズ 5 の半分は 2.5 なので、3 ≥ 2.5 という条件を満たし、True が返されます。

計算量

• 時間計算量：O(n + m)（各要素の余り計算に O(n)、頻度リストの走査に O(m)）
• 空間計算量：O(m)（頻度リストの分）

補足

Python 3 では len(input_list) / 2 は浮動小数点数を返しますが、整数との比較は問題なく動作します。より明示的にしたい場合は、math.ceil(len(input_list) / 2) や (len(input_list) + 1) // 2 を使う方法もあります。