C++でバイナリ配列全体をパワフルにするために必要な最小の「1」の個数を求める方法

任意のサイズのバイナリ配列(0 と 1 のみを格納)と、整数型の変数 base が与えられます。この課題の目的は、配列全体を「パワフル」な状態にするために、ほかの要素へ力を貸す必要のある最小の「1」の個数を求めることです。ある要素は、隣接する要素や、距離が base より小さい範囲内にある任意の要素へ力を貸すことができます。

入出力のシナリオ

ケース 1: base = 7 の場合

入力: int arr[] = {1, 1, 0, 1, 1, 0, 1}、int base = 7

出力: 配列全体をパワフルにするために必要な最小の「1」の数: 1

説明: サイズ 7 のバイナリ配列に対して base = 7 が与えられています。これは、たった 1 つの「1」で配列全体に力を貸せることを意味します。したがって、配列内のいずれかの「1」がすべての要素をカバーできるため、必要な数は 1 つだけです。

ケース 2: base = 3 の場合

入力: int arr[] = {1, 1, 0, 1, 1, 0, 1}、int base = 3

出力: 配列全体をパワフルにするために必要な最小の「1」の数: 2

説明: base = 3 の場合、それぞれの「1」は前後 2 要素以内(距離 3 未満)の要素に力を貸すことができます。先頭側の「1」と後半の「1」を組み合わせれば配列全体をカバーできるため、必要な「1」の数は 2 つになります。

ケース 3: base = 1 の場合

入力: int arr[] = {1, 1, 0, 1, 1, 0, 1}、int base = 1

出力: 配列全体をパワフルにすることは不可能

説明: base = 1 の場合、「1」は自分自身にしか力を貸すことができません。そのため「0」の位置を決してカバーできず、配列全体をパワフルにすることは不可能です。

プログラムで使用しているアプローチ

• 任意のサイズのバイナリ配列と整数変数(ここでは base とします)を入力として受け取ります。
• 配列のサイズを計算し、整数型の変数 val を宣言します。
• val に、パワフルな配列の作成に必要な最小の「1」の数を返す関数の呼び出し結果を設定します。作成が不可能な場合には -1 が返され、それに応じてエラーメッセージが表示されます。
• 関数 Lend_Power(int arr[], int size, int base) の内部では、以下の処理を行います。
  • バイナリ配列と同じサイズの整数型配列を宣言します。
  • 一時変数 temp を -1 で初期化し、count を 0 で初期化します。
  • i を 0 から配列サイズまでループさせます。ループ内で arr[i] が 1 であるかを確認し、1 であれば temp を i に設定して arr_2[i] に temp を代入します。これにより、arr_2[i] には「位置 i 以前で最も近い『1』のインデックス」が格納されます。
  • 続いて、i を 0 から開始するループを回します。各ステップで、reset_base を i + base - 1、reset_size を size - 1 とし、変数 set を arr_2[min(reset_base, reset_size)] に設定します。
  • set == -1 または set + base <= i が成立する場合は -1 を返します(カバーできない要素が存在することを意味します)。
  • 変数 i を set + base に更新し、count を 1 増やします。
• 最後に count を返します。

サンプルコード(C++)

#include<bits/stdc++.h>
using namespace std;

int Lend_Power(int arr[], int size, int base)
{
    int arr_2[size];
    int temp = -1;
    int count = 0;
    for(int i = 0; i < size; i++)
    {
        if(arr[i] == 1)
        {
            temp = i;
        }
        arr_2[i] = temp;
    }
    for(int i = 0; i < size;)
    {
        int reset_base = i + base - 1;
        int reset_size = size - 1;

        int set = arr_2[min(reset_base, reset_size)];
        if(set == -1 || set + base <= i)
        {
            return -1;
        }
        i = set + base;
        count++;
    }
    return count;
}
int main()
{
    int arr[] = {1, 1, 0, 1, 1, 0, 1};
    int base = 2;
    int size = sizeof(arr) / sizeof(arr[0]);
    int val = Lend_Power(arr, size, base);
    if(val == -1)
    {
        cout<<"Impossible to make entire array powerful";
    }
    else
    {
        cout<<"Minimum 1s to lend power to make whole array powerful are: "<<val;
    }
    return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます。

Minimum 1s to lend power to make whole array powerful are: 3

この結果は、base = 2 の場合に、配列全体をパワフルにするために最低 3 つの「1」が必要であることを示しています。