C++で数学コンテストの勝者を判定するアルゴリズムの解説

問題概要

サイズ n の2つの配列 P と T、および定数 c が与えられます。Amal と Bimal の2人が数学コンテストに参加することになりました。コンテストには n 問の問題が出題され、i 番目の問題の初期スコアは P[i]、それを解くのにかかる時間は T[i] です。P と T はどちらも昇順にソートされています。c は減点を決める定数で、ある問題をコンテスト開始 x 分後に提出した場合、その問題から得られるスコアは max(0, P[i] - c * x) となります。

Amal は問題を 1, 2, ..., n の順番で解き、Bimal は n, n-1, ..., 1 の順番で解きます。それぞれが自分の順序ですべての問題に取り組んだとき、合計スコアが高い方を勝者として求めてください。両者のスコアが同じ場合は「Tie」（引き分け）と出力します。

たとえば、入力が c = 2、P = [50, 85, 250]、T = [10, 15, 25] のとき、出力は「Amal」となります。

アルゴリズムの手順

この問題は、次の手順で解くことができます。

n := P のサイズ
m := 0
ans1 := 0
ans2 := 0
i := 0 として初期化し、i < n の間、i を 1 ずつ増やしながら繰り返す：
    m := m + T[i]
    ans1 := ans1 + max(0, P[i] - c * m)
m := 0
i := n - 1 として初期化し、i >= 0 の間、i を 1 ずつ減らしながら繰り返す：
    m := m + T[i]
    ans2 := ans2 + max(0, P[i] - c * m)
もし ans1 > ans2 ならば：
    "Amal" を返す
そうでなく ans1 < ans2 ならば：
    "Bimal" を返す
それ以外の場合：
    "Tie" を返す

考え方のポイント

各参加者のスコアは、配列を順方向（または逆方向）に一度だけ走査し、そこまでに費やした時間の累積値 m を更新しながら、各問題について max(0, P[i] - c * m) を加算することで求められます。後から解く問題ほど減点の影響が大きくなるため、この累積時間の管理が重要です。計算量は配列を1回ずつ見るだけの O(n) で、非常に効率的です。

C++による実装例

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

#include <bits/stdc++.h>
using namespace std;
string solve(int c, vector<int> P, vector<int> T){
    int n = P.size();
    int m = 0, ans1 = 0, ans2 = 0;
    for (int i = 0; i < n; i++){
        m += T[i];
        ans1 += max(0, P[i] - c * m);
    }
    m = 0;
    for (int i = n - 1; i >= 0; i--){
        m += T[i];
        ans2 += max(0, P[i] - c * m);
    }
    if (ans1 > ans2)
        return "Amal";
    else if (ans1 < ans2)
        return "Bimal";
    else
        return "Tie";
}
int main(){
    int c = 2;
    vector<int> P = { 50, 85, 250 };
    vector<int> T = { 10, 15, 25 };
    cout << solve(c, P, T) << endl;
}

入力

2, { 50, 85, 250 }, { 10, 15, 25 }

出力

Amal

実行結果の解説

この入力では、Amal の合計スコアは 215 点、Bimal の合計スコアは 205 点となります。したがって、より高いスコアを獲得した「Amal」が出力されます。