配列の要素をdで割った後、正の数が配列サイズの半分以上になるようなdを求めるC++プログラム

n個の要素からなる配列Aがあるとします。配列内のすべての数値を、ある非ゼロ整数dで割ったとき、結果として配列に現れる正の値の個数が配列サイズの半分以上になるようなdを見つけるのがこの問題です。条件を満たすdが複数存在する場合は、そのうちのどれか1つを返せば構いません。

例として、入力が A = [10, 0, -7, 2, 6] の場合を考えてみます。n = 5 なので、除算後には少なくとも ⌈5/2⌉ = 3 個の要素が正である必要があります。d = 4 を選んだ場合、除算後の配列は [2.5, 0, -1.75, 0.5, 1.5] となり、正の数は 2.5、0.5、1.5 の3個あるため、条件を満たしています。

解法のポイント

この問題は、数の符号に関する性質を利用すると非常にシンプルに解くことができます。正の数dで割り算をしても各要素の符号は変化しません。一方、負の数dで割ると、すべての要素の符号が反転します。つまり、元の配列に含まれる正の要素と負の要素の個数を数えるだけで答えが求まります。

• 正の要素の個数が配列サイズの半分以上の場合:d = 1 を返します。
• 負の要素の個数が配列サイズの半分以上の場合:d = -1 を返します(符号が反転するため、正の数が半分以上になります)。
• いずれの条件も満たさない場合:どのような非ゼロ整数dを選んでも条件を満たせないため、0 を返します。

アルゴリズムの手順

以下の手順に従って問題を解きます。

z := 0, f := 0
n := size of A
for initialize i := 0, when i < n, update (increase i by 1), do:
    a := A[i]
    if a > 0, then:
        (increase z by 1)
    if a < 0, then:
        (increase f by 1)
if 2 * z >= n, then:
    return 1
otherwise when 2 * f >= n, then:
    return -1
Otherwise
    return 0

C++での実装例

理解を深めるために、実際の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A){
    int z = 0, f = 0;
    int n = A.size();
    for (int i = 0; i < n; i++){
        int a = A[i];
        if (a > 0)
            z++;
        if (a < 0)
            f++;
    }
    if (2 * z >= n)
        return 1;
    else if (2 * f >= n)
        return -1;
    else
        return 0;
}
int main(){
    vector<int> A = { 10, 0, -7, 2, 6 };
    cout << solve(A) << endl;
}

入力

{ 10, 0, -7, 2, 6 }

出力

1

この入力では、正の要素は 10、2、6 の3個であり、2 × 3 = 6 が配列サイズの5以上となるため、関数は 1 を返します。