C++で解く：ゲーム開始前の子どもの人数の最小値と最大値を求めるプログラム

問題の概要

要素数 K の配列 A があるとします。ここに N 人の子どもとゲームマスターがおり、ゲームは全部で K ラウンド行われます。第 i ラウンドでは、ゲームマスターが「A[i] 人のグループを作れ」と宣告します。子どもたちは A[i] 人ずつのグループをできるだけ多く結成し、どのグループにも所属できなかった子どもはその場でゲームから脱落します。残った子どもたちは次のラウンドへ進みます（脱落者が誰も出ないラウンドがあっても構いません）。そして第 K ラウンド終了時にちょうど 2 人が残り、その 2 人が優勝者となります。求めたいのは、ゲーム開始前の子どもの人数 N として考えられる最小値と最大値であり、条件を満たす N が存在しない場合はそのことを報告します。

例えば、入力が A = [3, 4, 3, 2] なら、出力は [6, 8] になります。6 人でスタートした場合、ゲームは次のように進行します。

• 第1ラウンド：6 人が 3 人組を 2 つ結成する（脱落者なし）
• 第2ラウンド：4 人組が 1 つ結成され、余った 2 人が脱落
• 第3ラウンド：3 人組が 1 つ結成され、余った 1 人が脱落
• 第4ラウンド：2 人組が 1 つ結成され、余った 1 人が脱落

こうして最後に残った 2 人が優勝者となります。実際、開始人数が 6 人以上 8 人以下のときにのみ最終的に 2 人が残るため、答えは最小 6 人・最大 8 人です。

解き方の手順

この問題は、最終ラウンドから順に逆向きへ範囲を広げていく逆算アプローチで効率よく解けます。最終状態は「ちょうど 2 人」なので、まず l = 2、r = 2 という区間を用意し、各ラウンドを後ろから処理していきます。

1. そのラウンドのグループサイズを x とします。
2. このラウンドを通過したあとの人数が区間 [l, r] に収まるためには、直前の人数 c について ⌊c ÷ x⌋ × x が [l, r] 内の値になればよいので、条件を満たす c の最小値 L = ⌈l ÷ x⌉ × x、最大値 R = ⌊r ÷ x⌋ × x を計算します。
3. L > R となる場合は、条件を満たす開始人数が存在しないため「-1, 0」を出力します。
4. それ以外の場合は、区間を l = L、r = R + x − 1 へと更新して次へ進みます。

n := A のサイズ
十分に大きな配列 a を用意（サイズ 100010）
l := 2, r := 2
i := 1 から n まで:
    a[i] := A[i - 1]
i := n から 1 まで（逆順で）:
    x := a[i]
    L := (l + x - 1) / x * x   // l 以上で最小の x の倍数
    R := r / x * x             // r 以下で最大の x の倍数
    もし L > R ならば:
        return -1, 0
    l := L, r := R + x - 1
return l, r

各ラウンドの処理は定数時間で済むため、全体の計算量は O(K) と非常に効率的です。

C++での実装例

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

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

void solve(vector<int> A){
    int n = A.size();
    int l, r, a[100010];
    l = 2, r = 2;
    for (int i = 1; i <= n; i++)
        a[i] = A[i - 1];
    for (int i = n; i >= 1; i--){
        int x = a[i], L = (l + x - 1) / x * x, R = r / x * x;
        if (L > R){
            cout << \"-1, 0\";
        }
        l = L, r = R + x - 1;
    }
    cout << l << \", \" << r << endl;
    return;
}
int main(){
    vector<int> A = { 3, 4, 3, 2 };
    solve(A);
}

入力

{ 3, 4, 3, 2 }

出力

6, 8