C++で解くゲーム問題：0以下に減らせる数の個数を求めるアルゴリズム

問題概要

正の数からなる配列と、2つの整数 A と B が与えられます。2人のプレイヤーが交互に手番を進め、配列内の数値を操作していくゲームを考えます。プレイヤー1は配列の任意の要素を A だけ減らすことができ、プレイヤー2は任意の要素を B だけ増やすことができます。

求めたいのは、プレイヤー1が0以下に減らせる数の個数です。プレイヤー1が先手であり、一度0以下に減らされた数は、それ以降プレイヤー2の対象とはなりません。

入出力例

例1

入力：

arr[] = { 1, 4, 5, 2 }、A = 2、B = 3

出力：

ゲームで0以下に減らせる数の個数：1

説明：

プレイヤー1が減らせるのは「1」だけです。
先手の最初の手番で −1 に減らされるためです。
残りの要素は、プレイヤー2が値を増やすことで A より大きくなってしまいます。

例2

入力：

arr[] = { 1, 4, 5, 2 }、A = 4、B = 4

出力：

ゲームで0以下に減らせる数の個数：2

説明：

先手でプレイヤー1が 4 を 0 に減らします。arr[] = [ 1, 0, 5, 2 ]
プレイヤー2が 1 を 4 に増やします。arr[] = [ 5, 0, 5, 2 ]
プレイヤー1が 2 を −2 に減らします。arr[] = [ 5, 0, 5, −2 ]
以降、すべての要素が A より大きくなるため、プレイヤー2が同時に値を増やしていることもあり、
プレイヤー1はどの要素も0以下に減らせなくなります。

アプローチ

まず A > B かどうかを判定します。A の方が大きければ、N 手のうちにプレイヤー1は配列の N 個すべての要素を0以下に減らせます。したがって答えは配列のサイズになります。

A ≤ B の場合は、次の2つのグループに分けて考えます。

• プレイヤー2が B を加算しても A を超えない数 → 個数を C1 とします。

• A 以下であり、プレイヤー2が B を加算すると A を超えてしまう数 → 個数を C2 とします。

答えは C = C1 + (C2 + 1) / 2 となります。後者のグループでは、両プレイヤーが同時に値を増減させるため、半分だけが0以下に減らされます。プレイヤー2はそのうち半分を A より大きい状態にでき、その間にプレイヤー1は残りの半分を 0 以下に減らせるからです。

アルゴリズム

• 正の数を含む整数配列 arr[] と、2つの整数 A・B を受け取ります。

• 関数 reduced_zero(int arr[], int size, int A, int B) は、ゲームで0以下に減らせる数の個数を返します。

• 初期カウントを 0 とし、一時的なカウント用に変数 temp_1 と temp_2 を用意します。

• A > B の場合は、配列のサイズ size をそのまま返します。

• for ループで配列を走査し、各 arr[i] について「要素 + B ≤ A」であれば temp_1 をインクリメントします。

• 各要素 arr[i] ≤ A であれば temp_2 をインクリメントします。

• ループ終了後、count = temp_1 + (temp_2 + 1) / 2 を計算します。

• count を結果として返します。

コード例

#include <bits/stdc++.h>
using namespace std;
int reduced_zero(int arr[], int size, int A, int B){
    int count = 0;
    int temp_1 = 0, temp_2 = 0;
    if (A > B){
        return size;
    }
    for(int i = 0; i < size; i++){
        if (A >= arr[i] + B){
            temp_1++;
        }
        else if(A >= arr[i]){
            temp_2++;
        }
    }
    int temp = (temp_2 + 1) / 2;
    count = temp + temp_1;
    return count;
}
int main(){
    int arr[] = { 3, 3, 1, 2, 4, 7, 1};
    int A = 4, B = 1;
    int size = sizeof(arr) / sizeof(arr[0]);
    cout<<"ゲームで0以下に減らせる数の個数："<<reduced_zero(arr, size, A, B);
    return 0;
}

出力

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

ゲームで0以下に減らせる数の個数：7

この例では A = 4、B = 1 と A > B が成り立つため、配列の全要素（7個）が0以下に減らせると判定され、配列のサイズである 7 が返されます。