C++でトーナメントの対戦カードを出力する方法

n個のチームがあるとしましょう。コンテストをより面白くするために、常に強いチームと弱いチームを対戦させる戦略を採用します。たとえば、ランキング1位の最強チームと最下位のn位のチームを対戦させるといった具合です。この記事では、そのような戦略に基づいた最終的な対戦カード（マッチアップ）を文字列形式で求める方法を解説します。

問題の概要

各チームは初期ランキングを表す1からnまでの正の整数で与えられます。ランク1が最も強いチーム、ランクnが最も弱いチームです。対戦カードの表現には、括弧「(」「)」をペアのグループ化に、カンマ「,」を区切りに使用します。各ラウンドのペアリングでは、必ず強いチームと弱いチームを組み合わせるという戦略に従わなければなりません。

たとえば、入力が4の場合、出力は次のようになります。

((1,4),(2,3))

最初のラウンドで1位と4位、2位と3位が対戦し、その結果がさらに括弧でまとめられています。

解決アプローチ

この問題は、再帰を使って段階的にペアを作成していくことで解決できます。手順は以下の通りです。

• 関数 create() を定義します。引数として low、high、配列 v2、配列 v1 を受け取ります。
• low >= high の場合は何もせず return します。
• "(" + v1[low] + "," + v1[high] + ")" という文字列を作成し、v2 の末尾に追加します。
• create(low + 1, high - 1, v2, v1) を再帰的に呼び出し、内側のペアを順に作成していきます。

メインメソッド側では次のように処理を進めます。

• 文字列配列 v1 と v2 を定義します。
• i = 1 から n までループし、i を文字列に変換して v1 に追加します。
• v1 のサイズが 1 より大きい間、以下を繰り返します。
  • create(0, v1のサイズ - 1, v2, v1) を呼び出して一巡分のペアを作成します。
  • v1 = v2 として結果を引き継ぎます。
  • v2 をクリアします。
• 最後に v1 の末尾の要素（完成した対戦カード）を返します。

C++での実装例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    void create(int low, int high, vector<string>& v2, vector<string>& v1){
        if (low >= high)
            return;
        v2.push_back("(" + v1[low] + "," + v1[high] + ")");
        create(low + 1, high - 1, v2, v1);
    }
    string findContestMatch(int n) {
        vector<string> v1, v2;
        for (int i = 1; i <= n; i++) {
            v1.push_back(to_string(i));
        }
        while (v1.size() > 1) {
            create(0, v1.size() - 1, v2, v1);
            v1 = v2;
            v2.clear();
        }
        return v1.back();
    }
};
main(){
    Solution ob;
    cout << (ob.findContestMatch(4));
}

実行結果

入力

4

出力

((1,4),(2,3))

処理の流れのポイント

このアルゴリズムのポイントは、各ラウンドごとに配列の先頭（最強）と末尾（最弱）から順にペアを作っていく点です。1回の create() 呼び出しで全チームのペアが作成され、その結果が新しいチームの集合として扱われます。これをチーム数が1になるまで繰り返すことで、最終的なトーナメント全体の対戦カードが一つの文字列として得られます。計算量は O(n log n) 程度に収まり、効率的な実装となっています。