Pythonで配列C[i] = d×A[i] + B[i]のゼロの個数を最大化するdを求める方法

n個の整数からなる2つの配列 A と B が与えられ、i番目の要素が d * A[i] + B[i] で表される配列 C を考えます。ここで d は任意の実数です。本記事では、配列Cに含まれるゼロ（0）の個数が最大になるような d の値を求め、あわせてそのゼロの個数を返す方法を解説します。

たとえば、入力が A = [15, 40, 45]、B = [4, 5, 6] の場合、出力は d = -0.266666、ゼロの個数は 1 となります。

解法のポイント

この問題の鍵は、C[i] = d * A[i] + B[i] が0になる条件を整理することです。

• C[i] = 0 となるのは d = -B[i] / A[i] のときです。つまり、各インデックス i ごとに、その要素をゼロにできる候補の d の値が1つずつ求まります。

• A[i] = 0 かつ B[i] = 0 の要素は、d の値にかかわらず常に0になるため、別途カウントしておきます。

• A[i] = 0 だが B[i] ≠ 0 の要素は、どのような d を選んでも0にならないため無視できます。

したがって、「候補となる d の値の中で最も出現回数が多いもの」を採用すれば、それだけ多くの要素が同時にゼロになります。

アルゴリズムの手順

• n := 配列Aのサイズ

• my_map := 空の辞書（マップ）

• count := 0

• i を 0 から n-1 まで繰り返す：

  • B[i] ≠ 0 かつ A[i] ≠ 0 の場合：

    • val := (-1.0 * B[i]) / A[i]

    • val が my_map に存在しなければ my_map[val] := 0 で初期化

    • my_map[val] := my_map[val] + 1

  • B[i] = 0 かつ A[i] = 0 の場合：

    • count := count + 1

• maximum := 0

• my_map の各要素について、maximum を出現回数の最大値に更新

• my_map のキーと値を走査し、値が maximum と一致するキーを表示してループを抜ける

• maximum + count を表示（これがゼロの総数）

Pythonでの実装例

以下のコードで実際の動作を確認できます。

def find_d_zero(A, B) :
    n = len(A)
    my_map = {}
    count = 0
    for i in range(n) :
        if (B[i] != 0 and A[i] != 0) :
            val = (-1.0 * B[i]) / A[i]
            if val not in my_map :
                my_map[val] = 0
            my_map[val] += 1
        elif (B[i] == 0 and A[i] == 0) :
            count += 1
    maximum = 0
    for item in my_map :
        maximum = max(my_map[item], maximum)
    for keys, values in my_map.items() :
        if (values == maximum) :
            print("d = ", keys)
            break
    print("Number of 0s: ", maximum + count)

a = [15, 40, 45]
b = [4, 5, 6]
find_d_zero(a, b)

入力

[15, 40, 45], [4, 5, 6]

出力

d = -0.26666666666666666
Number of 0s: 1

まとめ

このアルゴリズムでは、各要素をゼロにできる d の候補値を辞書で集計し、最も頻度の高い値を採用することで、配列Cのゼロの個数を最大化しています。計算量は O(n) であり、線形時間で効率的に解くことができる点が大きな特徴です。