C++で全問題を配布するために必要な最小メール数を求める方法

問題の概要

テストにN問の問題があり、クラスにはK人の生徒が在籍しています。このうちN人の生徒は、それぞれちょうど1問ずつ異なる問題を暗記しています。1通のメールに含められる問題数は最大X問です。

クラス全員がすべての問題を把握できるようにするには、何通のメールが必要になるかを求めます。

具体例

N = 3、K = 3、X = 1 の場合、合計6通のメールを送る必要があります。

• 生徒1が自分の問題を生徒2と生徒3に送信（2通）
• 生徒2と生徒3も同様に、各自の問題を他の2人に送信
• 合計メール数 = 2 × 3 = 6通

アルゴリズム

答えは次の式で計算できます。

ceil(N/X) * (K-N) + ceil((N-1)/X) * (N-1) + (N-1)

この式は大きく分けて次の要素で構成されています。

• すでに問題を知っているN人の生徒同士が互いに情報を共有するために必要なメール数
• まだ何も知らない(K-N)人の生徒1人ひとりに全N問を配布するために必要なメール数（1人あたりceil(N/X)通）

特にX = 1の場合は1通のメールで1問しか送れないため、メール数が大きくなりやすい点に注意してください。

C++での実装例

#include <iostream>
#include <cmath>
using namespace std;

int minMailsToBeSent(int n, int k, int x) {
    int m = (n - 1) + ceil((n - 1) * 1.0 / x) * (n - 1) + ceil(n * 1.0 / x) * (k - n);
    return m;
}

int main() {
    int questions = 3;
    int students = 3;
    int X = 1;
    cout << "No of mails to be sent: " << minMailsToBeSent(questions, students, X) << endl;
    return 0;
}

実行結果

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

No of mails to be sent: 6

まとめ

本記事では、N問の問題とK人の生徒、そして1通のメールで送れる最大問題数Xが与えられたときに、クラス全員がすべての問題を知るために必要な最小メール数を求める方法を解説しました。切り上げ計算（ceil）を組み合わせた数式を使うことで、効率的に答えを求められます。