C++で2つの整数を使う偶奇ターンゲームの解き方

この問題では、3つの整数 A、B、T が与えられます。私たちのタスクは、2つの整数を使った偶奇ターンゲームをシミュレートするプログラムを C++ で作成することです。

ゲームのルール

各整数の意味は次の通りです。

• T: ゲームのターン数
• A: プレイヤー1の値
• B: プレイヤー2の値

ターンごとに以下の操作が行われます。

• T が奇数のとき:A の値が2倍される
• T が偶数のとき:B の値が2倍される

そして、すべてのターンが終わった時点の max(A, B) / min(A, B) の値を求めて返します。

例で問題を理解しよう

入力: A = 3, B = 4, T = 3

出力: 1

説明:

1ターン目:T は奇数なので A が2倍され、A = 6 になります。
2ターン目:T は偶数なので B が2倍され、B = 8 になります。
3ターン目:T は奇数なので A が2倍され、A = 12 になります。

最終的な値は A = 12、B = 8 です。

max(A, B) = max(12, 8) = 12
min(A, B) = min(12, 8) = 8
max(A, B) / min(A, B) = 12 / 8 = 1(整数除算)

解法アプローチ

最も単純な解法は、T 回のターンを実際にシミュレートして A と B の値を更新し、最後に max(A, B) / min(A, B) を返す方法です。T 回の反復で正しい結果が得られます。

しかし、次の性質に注目すると、より効率的な解法が見つかります。

• T が偶数の場合: A と B はどちらも同じ回数(T/2 回)だけ2倍されます。つまり新しい A は 2^(T/2) × A、新しい B は 2^(T/2) × B となり、両方に同じ係数が掛かるため比率は変化しません。したがって答えは、初期値のままの max(A, B) / min(A, B) と一致します。
• T が奇数の場合: A は (T+1)/2 回、B は (T-1)/2 回2倍されます。A だけが1回余分に2倍されることになるため、答えは max(2A, B) / min(2A, B) と一致します。

以上をまとめると、結果は次のように表せます。

T が偶数の場合:max(A, B) / min(A, B)
T が奇数の場合:max(2A, B) / min(2A, B)

この方法なら、ターン数 T がどれほど大きくても O(1) で答えを求められるのが大きなメリットです。

解法の動作を示すプログラム

例

#include <iostream>
using namespace std;

int EvenOddGame(int A, int B, int T) {
    if (T % 2 == 0)
        return (max(A, B) / min(A, B));
    else
        return (max(2*A, B) / min(2*A, B));
    return -1;
}

int main() {
    int A = 3, B = 2, T = 3;
    cout << "偶奇ターンゲームの戻り値は " << EvenOddGame(A, B, T);
    return 0;
}

出力

偶奇ターンゲームの戻り値は 3

この例では A = 3、B = 2、T = 3(奇数)なので、max(6, 2) / min(6, 2) = 6 / 2 = 3 が返されます。