C++でコンテストの勝者と非勝者の人数を求める方法

問題概要

2つの整数 n と k が与えられます。あるコンテストには n 人の学生が参加しており、そのうち何人かは記念品を、何人かは賞状を受け取り、残りの人は何も受け取りません。何かしらを受け取った人を「勝者」と呼びます。

記念品と賞状の数を決める際には、以下のルールが定められています。

• 賞状の数は、記念品の数のちょうど k 倍でなければならない
• 勝者の総数は n/2 を超えてはならない
• 勝者が一人も存在しない場合もあり得る

これらのルールに基づき、可能な限り多い勝者の数を求めます。そのうえで、記念品を受け取る学生の人数、賞状を受け取る学生の人数、そして勝者とならない学生の人数をそれぞれ出力します。

例えば、入力が n = 18、k = 2 の場合、出力は [3, 6, 9] となります。

解法のアプローチ

この問題は、次のシンプルな計算で解くことができます。

x := (n / 2) / (1 + k)
return x, (k * x), (n - (x + (k * x)))

考え方のポイント

記念品を x 人分とすると、賞状はその k 倍なので k・x 人分となります。したがって勝者の合計は x + k・x = x(1 + k) です。この値が n/2 を超えないようにするため、x の最大値は「(n / 2) ÷ (1 + k)」の整数除算で求まります。残りの n − x(1 + k) 人が非勝者となります。

C++での実装例

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

#include <bits/stdc++.h>
using namespace std;
void solve(int n, int k){
    int x = (n / 2) / (1 + k);
    cout << x << ", " << (k * x) << ", " << (n - (x + (k * x)));
}
int main(){
    int n = 18;
    int k = 2;
    solve(n, k);
}

入力

18, 2

出力

3, 6, 9

この結果から、記念品を受け取るのは3人、賞状を受け取るのは6人（3の2倍）、勝者になれないのは9人であることがわかります。計算量は O(1) であり、非常に効率的な解法です。