十分なキャンディーを渡せなくなった人を判定するC++プログラム

2つの整数 a と b があるとします。a はアマル(Amal)が持っているキャンディーの数、b はビマル(Bimal)が持っているキャンディーの数を表します。まずアマルがビマルに1個のキャンディーを渡し、次にビマルがアマルに2個渡します。その後もアマルが3個、ビマルが4個というように、渡す個数を1個ずつ増やしながら交互にキャンディーを渡し合います。このやり取りは、どちらか一方が必要な個数を渡せなくなった時点で終了します。なお、相手から受け取ったキャンディーは自分の持ち分としては数えません。ここで、最初に正しい個数のキャンディーを渡せなくなるのが誰なのかを求める必要があります。

例えば、入力が a = 7、b = 6 の場合、出力は「Amal」となります。アマルが1個、ビマルが2個、アマルが3個、ビマルが4個と渡していき、次のターンでアマルは5個渡さなければなりませんが、手持ちは4個しかないためです。

解法の手順

この問題を解くには、以下の手順に従います。

x := a の平方根
もし x * (x + 1) > b ならば:
    "Bimal" を返す
そうでなければ:
    "Amal" を返す

なぜこの式で判定できるのか

アマルが渡すのは1個、3個、5個…と奇数です。n回目のターンまでにアマルが渡した合計は 1 + 3 + … + (2n−1) = n² となります。つまり、アマルが n 回目のターンを完了できる条件は「a ≥ n²」であり、アマルが完了できる最大のターン数は ⌊√a⌋(これを x とする)です。

一方、ビマルが渡すのは2個、4個…と偶数で、x 回目までに渡す合計は 2 + 4 + … + 2x = x(x+1) です。したがって、b が x(x+1) より小さければビマルが先に行き詰まり、逆に b ≥ x(x+1) であればビマルは x 回目を完了できますが、アマルは次のターンで (x+1)² 個必要になるものの a < (x+1)² のため渡せず、アマルが先に行き詰まることになります。この判定により、シミュレーションを行わずに O(1) で答えを求められます。

実装例

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

#include <bits/stdc++.h>
using namespace std;
string solve(int a, int b){
    int x = sqrt(a);
    if (x * (x + 1) > b)
        return "Bimal";
    else
        return "Amal";
}
int main(){
    int a = 7;
    int b = 6;
    cout << solve(a, b) << endl;
}

入力

7, 6

出力

Amal