C++でどちらの数値が大きくなる確率が高いかを判定する方法

問題概要

2つのk桁の整数 m と n が与えられているとします。それぞれの数値の桁をランダムにシャッフルした上で比較を行い、どちらの数値が大きくなる確率が高いかを判定します。

例えば、入力が n = 231、m = 337、k = 3 の場合、出力は「Second」になります。これは、2番目の数値(m = 337)の方が大きくなる確率が高いことを示しています。

解法のアプローチ

この問題は、両方の数値を文字列として扱い、各桁を先頭から順番に比較することで解けます。具体的な手順は以下の通りです。

1. n と m をそれぞれ文字列 s1、s2 に変換します。
2. f(1番目の数値の桁が大きかった回数)と s(2番目の数値の桁が大きかった回数)を 0 で初期化します。
3. i = 0 から k-1 までループし、各桁を順に比較します。
4. s1[i] > s2[i] なら f を、s1[i] < s2[i] なら s をインクリメントします。
5. 最後に f と s の大小関係を比較し、「First」「Second」「Equal」のいずれかを出力します。

擬似コード

s1 := n を文字列に変換
s2 := m を文字列に変換
f := 0, s := 0
for i := 0 to k-1 do:
    if s1[i] > s2[i], then:
        f := f + 1
    else if s1[i] < s2[i], then:
        s := s + 1
if f > s, then:
    print("First")
else if s > f, then:
    print("Second")
else:
    print("Equal")

C++による実装例

理解をさらに深めるために、以下のC++プログラムを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
#define N 100
void solve(int n, int m, int k) {
    string s1 = to_string(n);
    string s2 = to_string(m);
    int f = 0, s = 0;
    for(int i = 0; i < k; i++){
        if(s1[i] > s2[i])
            f++;
        else if(s1[i] < s2[i])
            s++;
    }
    if(f > s)
        cout<<"First"<<endl;
    else if(s > f)
        cout<<"Second"<<endl;
    else
        cout<<"Equal"<<endl;
}
int main() {
    int n = 231, m = 337, k = 3;
    solve(n, m, k);
    return 0;
}

入力

231, 337, 3

出力

Second

動作の解説

n = 231 と m = 337 の場合、各桁を先頭から順に比較すると次のようになります。

• 1桁目:「2」対「3」→ 2番目の数値の桁が大きいため s をカウント
• 2桁目:「3」対「3」→ 同じ値のためカウントなし
• 3桁目:「1」対「7」→ 2番目の数値の桁が大きいため s をカウント

結果として f = 0、s = 2 となり、s > f であるため「Second」が出力されます。このように、桁ごとの勝敗を数えて優勢な方を判定するシンプルな手法で、確率的な問題を効率よく処理できます。

計算量

• 時間計算量: O(k) — 各桁を1度ずつ比較するだけです。
• 空間計算量: O(k) — 数値を文字列として保持するために必要となります。