C++でc[i] = d*a[i] + b[i]となる配列Cのゼロの個数を最大化するdの求め方

概要

M個の整数からなる2つの配列 a[] と b[] が与えられたとします。ここで、i番目の要素が d × a[i] + b[i] で表される配列Cを考えます（dは任意の実数）。本記事では、配列Cに含まれるゼロの個数が最大になるようなdの値を求め、そのゼロの個数を出力する方法を解説します。

入力例

a[] = {15, 40, 45}
b[] = {4, 5, 6}

出力例

Value of d is: -0.133333
The number of zeros in array C is: 1

d を -0.133333 に設定すると、配列Cには1つのゼロが現れます。これが実現可能なゼロの最大個数です。

解法のアプローチ

この問題は、次の手順で解くことができます。

• 式 c[i] = d × a[i] + b[i] = 0 を変形し、d = -b[i] / a[i] という形に書き直します。
• ハッシュテーブルを使って各d候補値の出現回数をカウントし、最も多く出現するdの値を特定します。
• ゼロの総数は「最頻出のdの出現回数 ＋ a[i] と b[i] が両方とも0であるペアの個数」になります。

この方法が機能する理由

c[i] が0になるのは d = -b[i]/a[i] のときだけです。そのため、同じdの値が複数のインデックスで導かれれば、その回数だけゼロを作り出せます。一方、a[i] = 0 かつ b[i] = 0 の要素は、dの値に関係なく常に c[i] = 0 となるため、別途カウントして加算する必要があります。

C++による実装例

// 上記のアプローチを実装するC++プログラム
#include <bits/stdc++.h>
using namespace std;

// dの値を求め、配列内のゼロの個数を計算する関数
void findDandZeros1(int a[], int b[], int m){
    // ハッシュテーブル
    unordered_map<long double, int> mpp1;
    int count1 = 0;

    // 各要素について反復処理
    for (int i = 0; i < m; i++) {
        // a[i] と b[i] がどちらも0でない場合
        if (b[i] != 0 && a[i] != 0) {
            long double val1 = (long double)(-1.0 * b[i]) /
                               (long double)(a[i]);
            mpp1[val1] += 1;
        }
        // a[i] と b[i] がどちらも0の場合
        else if (b[i] == 0 && a[i] == 0)
            count1 += 1;
    }

    // 最も多く出現するdを求める
    int maxi1 = 0;
    for (auto it : mpp1) {
        maxi1 = max(it.second, maxi1);
    }

    // 出現回数が最大のdを出力する
    for (auto it : mpp1) {
        if (it.second == maxi1) {
            cout << "Value of d is: "
                 << it.first << endl;
            break;
        }
    }

    // ゼロの個数を出力する
    cout << "The number of zeros in array C is: "
         << maxi1 + count1;
}

// ドライバーコード
int main(){
    int a[] = { 15, 40, 45 };
    int b[] = { 4, 5, 6 };
    int m = sizeof(a) / sizeof(a[0]);
    findDandZeros1(a, b, m);
    return 0;
}

実行結果

Value of d is: -0.133333
The number of zeros in array C is: 1

計算量

このアルゴリズムの時間計算量は O(m) であり、ハッシュテーブルの分だけ空間計算量も O(m) となります。配列のサイズが大きくなっても効率的に動作するのが特徴です。