C++プログラム：通信遅延を考慮したタイピングゲームの勝者を判定する方法

5つの整数 s、v1、v2、t1、t2 が与えられます。Amal（アマル）とBimal（ビマル）は、オンラインでタイピングゲームの対戦を行っています。このゲームでは、長さ s の文字列を入力します。Amalが1文字入力するのにかかる時間は v1 ミリ秒、Bimalは v2 ミリ秒です。また、Amalのネットワーク遅延は t1 ミリ秒、Bimalのネットワーク遅延は t2 ミリ秒です。

通信遅延がある場合のゲームの流れ

通信遅延が t ミリ秒であるとき、各参加者にとって競技は次のように進行します。

• ゲーム開始からちょうど t ミリ秒後に入力すべきテキストが届く。
• テキストを受け取った直後に入力を開始する。
• すべてのテキストの入力を完了してからちょうど t ミリ秒後に、サイトへその情報が送信される。

より早く完了した方が勝者となり、両者の所要時間が同じであれば引き分けとなります。この勝者を求めるのが今回の課題です。

入力例と出力例

例えば、s = 5、v1 = 1、v2 = 2、t1 = 1、t2 = 2 が入力として与えられた場合、出力は Amal になります。Amalの結果がサイトに届くのは7ミリ秒後であるのに対し、Bimalは14ミリ秒後だからです。したがって、Amalの勝利となります。

解法の考え方

この問題は非常にシンプルで、各参加者の合計所要時間を計算して比較するだけです。合計所要時間は次の式で求められます。

合計時間 = 文字列の長さ × 1文字あたりの入力時間 + 2 × 通信遅延

通信遅延は「テキスト受信時」と「結果送信時」の2回発生するため、2倍する必要がある点に注意しましょう。

アルゴリズムの手順

以下の手順で問題を解くことができます。

p := (s * v1) + (2 * t1)
q := (s * v2) + (2 * t2)
if p == q then:
    return "Draw"（引き分け）
else if p < q then:
    return "Amal"
else:
    return "Bimal"

C++による実装例

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

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

string solve(int s, int v1, int v2, int t1, int t2) {
    int p = (s * v1) + (2 * t1);
    int q = (s * v2) + (2 * t2);
    if (p == q)
        return "Draw";
    else if (p < q)
        return "Amal";
    else
        return "Bimal";
}

int main() {
    int s = 5;
    int v1 = 1;
    int v2 = 2;
    int t1 = 1;
    int t2 = 2;
    cout << solve(s, v1, v2, t1, t2) << endl;
}

入力

5, 1, 2, 1, 2

出力

Amal

計算量

このアルゴリズムは定数回の演算のみで構成されているため、時間計算量は O(1)、空間計算量も O(1) です。入力サイズに依存しないため、非常に効率的な解法と言えます。