Pythonでトーナメント戦の総試合数を求めるプログラムの書き方

ある数 n が与えられ、トーナメントには n チームが参加しているとします。このトーナメントには以下のようなルールがあります。

• チーム数が偶数の場合：各チームは別のチームと対戦し、合計 n/2 試合が行われます。勝った n/2 チームが次のラウンドに進みます。
• チーム数が奇数の場合：1チームが抽選により不戦勝（シード）となり、残りのチーム同士で対戦します。このとき合計 (n−1)/2 試合が行われ、(n−1)/2 + 1 チームが次のラウンドへ進みます。

このルールのもとで、優勝者が決まるまでに行われる試合の総数を求めるのが本問題です。

例：n = 10 の場合

入力が n = 10 のとき、出力は 9 になります。その過程は次のとおりです。

• まず 5 対 5 に分かれて対戦し、5チームが勝ち上がる（5試合）
• 1チームをシードとし、残り4チームを 2 対 2 で対戦させ、3チームが勝ち上がる（2試合）
• 再び1チームをシードとし、残り2チームを 1 対 1 で対戦させ、2チームが勝ち上がる（1試合）
• 最後に 1 対 1 で対戦し、優勝者が決まる（1試合）

合計 5 + 2 + 1 + 1 = 9 試合となります。

解き方のアルゴリズム

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

• 答えを格納する変数 ans を 0 で初期化します。
• n が 1 になるまで以下を繰り返します。
  • f ← n ÷ 2 の商（切り捨て）
  • remainder ← n を 2 で割った余り
  • ans ← ans + f
  • n ← f + remainder
• 繰り返しが終わったら ans を返します。

Pythonでの実装例

実際のコードは以下のようになります。

def solve(n):
    ans = 0
    while n != 1:
        f = n // 2
        remainder = n % 2
        ans += f
        n = f + remainder

    return ans

n = 10
print(solve(n))

入力

10

出力

9

補足：もっと簡単な考え方

実は、この問題には elegant な性質があります。トーナメントでは1試合ごとに必ず1チームが敗退するため、優勝者1チームを残すまでに敗退するチームは n − 1 チームです。つまり、ルールに関係なく総試合数は常に n − 1 となります。n = 10 の場合も 10 − 1 = 9 試合であり、上記のシミュレーション結果と一致します。計算量 O(log n) のシミュレーションに対し、この性質を使えば O(1) で答えを求められる点は覚えておくと便利です。