C++でレビュー投票の結果と不確実性を判定するコード

問題の概要

3つの整数 x、y、z が与えられます。あるレビューサイトでは、x 人が賛成票(アップ投票)を、y 人が反対票(ダウン投票)を投じることが確定しており、さらに z 人が投票予定ですが、彼らが賛成票を投じるのか反対票を投じるのかは不明です。各人は最大1回しか投票できません。

賛成票が反対票より多ければ結果は「+」、反対票が多ければ「-」、同数であれば「0」となります。しかし、投票先が不明な z 人が存在するため、結果が1通りに確定しないケースがあります。z 人の投票の仕方に2通り以上の異なるシナリオが存在するとき、結果は不確実(「?」)とみなされます。この問題では、結果を求めるか、不確実であることを報告します。

入力例

x = 2、y = 0、z = 2 の場合を考えてみましょう。すでに賛成票が2票あり、残りの2票がすべて反対票なら結果は「0」になりますが、すべて賛成票なら「+」になります。このように結果が確定しないため、出力は「?」となります。

解法のステップ

この問題は、次の条件分岐で解くことができます。

• x > y + z の場合: 不明な z 人が全員反対票を投じても賛成票が上回るため、結果は「+」で確定します。
• x + z < y の場合: 不明な z 人が全員賛成票を投じても反対票が上回るため、結果は「-」で確定します。
• z = 0 の場合: 投票がすべて確定しており、上記の条件を通過した時点で x = y が成り立つため、結果は「0」です。
• 上記以外の場合: 不明な票によって結果が変わり得るため、「?」を返します。

C++による実装例

以下は、このロジックをC++で実装した例です。

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

string solve(int x, int y, int z){
    if (x > y + z)
        return "+";
    else if (x + z < y)
        return "-";
    else if (!z)
        return "0";
    else
        return "?";
}

int main(){
    int x = 2;
    int y = 0;
    int z = 2;
    cout << solve(x, y, z) << endl;
}

入力

2, 0, 2

出力

?

計算量

このアルゴリズムは単純な条件分岐のみで構成されているため、時間計算量・空間計算量ともに O(1) で動作します。投票者数がどれほど多くても、定数時間で結果を判定できるのがポイントです。