C++でトーナメント優勝者がプレイできる最大試合数を求める方法

問題文

N人のプレイヤーがトーナメントに参加しています。この問題では、優勝者がプレイできる最大の試合数を求める必要があります。ただし、このトーナメントには特別なルールがあり、2人のプレイヤーが対戦できるのは、それぞれがこれまでにプレイした試合数の差が1以内である場合のみです。

具体例

プレイヤーが3人の場合、優勝者を決めるには2試合が必要です。進行は以下のようになります。

第1試合：プレイヤー1 vs プレイヤー2

第2試合：プレイヤー3 vs 第1試合の勝者

アルゴリズムの考え方

• まず「優勝者がx試合プレイするためには、最低何人のプレイヤーが必要か」という逆向きの問題を考えます。本題はその逆を解くことになります。ここで、dp[i] を「優勝者がi試合プレイするのに必要な最小プレイヤー数」と定義します。
• dp値の間には、dp[i + 1] = dp[i] + dp[i − 1] という再帰的な関係が成り立ちます。これは、優勝者がi試合、準優勝者が(i − 1)試合プレイしており、彼らが対戦してきた相手がすべて重複しないと仮定すると、優勝者の試合に関わった総プレイヤー数がこの2つの集合の和になるためです。
• この再帰関係は dp[i] = dp[i − 1] + dp[i − 2] と表せます。これはまさにフィボナッチ数列と同じ漸化式です。したがって最終的な答えは、「入力として与えられたプレイヤー数以下となる最大のフィボナッチ数」のインデックスを求めればよいことになります。
• 初期値は dp[0] = 1、dp[1] = 2 となり、数列は 1, 2, 3, 5, 8, 13 … と増加していきます。フィボナッチ数列は指数的に成長するため、計算量は非常に効率的で、実質的にO(log n)程度のステップで答えが得られます。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
int getMaxGamesToDecideWinner(int n) {
   int dp[n];
   dp[0] = 1;
   dp[1] = 2;
   int idx = 2;
   do {
      dp[idx] = dp[idx - 1] + dp[idx - 2];
   } while(dp[idx++] <= n);
      return (idx - 2);
}
int main() {
   int players = 3;
   cout << "Maximum games required to decide winner = " << getMaxGamesToDecideWinner(players) << endl;
   return 0;
}

出力結果

上記のプログラムをコンパイルして実行すると、以下の出力が得られます。

Maximum games required to decide winner = 2

このように、プレイヤー数に対してフィボナッチ数列のインデックスを対応させることで、優勝者が経験できる最大試合数をシンプルかつ高速に求められます。