C++で変数aとbの単位を使って通過できる最大要素数を求める方法

本記事では、2値配列 arr[] と、それぞれ初期値を持つ2つの変数 a、b が与えられたときに、配列の要素を最大でいくつ通過できるかを求める問題を解説します。

問題のルール

配列 arr[] の要素を通過するには、次の2つの方法があります。

• arr[i] == 1 の場合： a から1単位を消費できます（b は変化しません）。あるいは b から1単位を消費すると、その代わりに a が1単位増加します。ただし、a の値は元の値を超えて増加できない点に注意してください。

• arr[i] == 0 の場合： a または b のどちらかから1単位を消費できます。

それでは、具体例を使って問題を理解しましょう。

入力例1

arr[] = {0, 0, 0, 1, 1}, a = 2, b = 2

出力例1

5

説明

• 1番目の要素を通過するために、a から1単位消費します（a = 1, b = 2）。

• 2番目の要素を通過するために、a から1単位消費します（a = 0, b = 2）。

• 3番目の要素を通過するために、b から1単位消費します（a = 0, b = 1）。

• 4番目の要素を通過するために、b から1単位消費します。これにより a が1単位増加します（a = 1, b = 0）。

• 5番目の要素を通過するために、a から1単位消費します（a = 0, b = 0）。

このようにしてすべての要素を通過でき、出力は 5 となります。

入力例2

arr[] = {1, 1, 1, 0, 1}, a = 1, b = 2

出力例2

4

アルゴリズムのアプローチ

この問題は貪欲法（グリーディ法）で解くことができます。手順は以下の通りです。

• 関数 MaxElements() 内で、int 型の変数 Oa = 0 と max = 0 を初期化します。Oa は a の元の値を保存するためのもので、max は最終的な答えを格納します。

• i = 0 から i < size までループを回し、配列の各要素を順番に確認します。

• まず、a と b が両方ともゼロの場合は、ループを抜けます。

• 次に (a == 0) かどうかを確認します。該当する場合、現在の要素が1であれば b から1減算してその要素を通過し、a = min(Oa, a + 1) として a が元の値を超えないようにします。それ以外の場合は、単純に b から1減算します（a には影響しません）。

• (b == 0) の場合は、単純に a から1減算します。

• (arr[i] == 1 && a < Oa) の場合も確認します。該当する場合、b から1減算してその要素を通過し、a = min(Oa, a + 1) とします。

• 上記のいずれにも該当しない場合は、単純に a から1減算し、max を1増やします。

• ループを抜けたら、max を返します。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
int MaxElements(int arr[], int a, int b, int size){
    // Oa には a の元の値を保持する
    int Oa = a;
    int max = 0;
    // 2値配列を反復処理
    for (int i = 0; i < size; i++){
        // a と b が両方とも 0 ならループを抜ける
        if (a == 0 && b == 0)
            break;
        // a がない場合は b を使用
        else if (a == 0){
            // arr[i] == 1 なら a を1増やす
            if (arr[i] == 1){
                b -= 1;
                // 元の値を超えていないかチェック
                a = min(Oa, a + 1);
            }
            else
                b -= 1;
        }
        // b がない場合は a を使用
        else if (b == 0)
            a--;
        // arr[i] == 1 なら b を使用
        else if (arr[i] == 1 && a < Oa){
            b -= 1;
            a = min(Oa, a + 1);
        }
        else
            a--;
        max++;
    }
    return max;
}
// main 関数
int main(){
    int arr[] = { 1, 1, 1, 0, 1 };
    int size = sizeof(arr) / sizeof(arr[0]);
    int a = 1;
    int b = 2;
    cout << MaxElements(arr, a, b, size);
    return 0;
}

実行結果

4

まとめ

このアルゴリズムは、配列を一度だけ走査すればよいため、時間計算量は O(n)、補助的な記憶領域は O(1) で済みます。ポイントは、arr[i] == 1 のときに b を優先的に消費することで a を回復させられる点です。ただし a がすでに元の値に達している場合は a を消費する方が得策であるため、条件分岐で適切に判断しています。この貪欲な選択により、通過できる要素数を最大化できます。