第二回 アルゴリズム実技検定 I - トーナメント 解説

問題

問題文は本家サイトにあります：第二回 アルゴリズム実技検定 I - トーナメント

問題概要

$2^N$ 人の人がトーナメントに参加しました。参加者には $1$ から $2^N$ までの番号がついていて、次のように戦いました。

1回戦：番号の小さい方から順に2人ずつペアを組んで、各ペア内で2人が戦う。勝った方だけが残る。
2回戦以上：残った人を番号順に並べ、番号の小さい方から順に2人ずつペアを組んで、各ペア内で2人が戦う。勝った方だけが残る。

番号 $i$ の人の強さは $A_i$ で表され、数字の大きい方が必ず勝ちます。それぞれの人について、その人が最後に戦ったのは何回戦か、答えてください。

制約

$1\leqq N \leqq 16$
$1\leqq A_i \leqq 2^N$
$i\ne j$ なら $A_i\ne A_j$

解説

強さが 2 4 3 1 の場合、1回戦は、強さで表すと 2対4 と 3対1 なので、2人目と3人目が残ります。2回戦でこの2人が戦い、2人目が勝ってトーナメントは終了です。なので、 1 2 2 1 と答えることになります。

勝った人を残していくので、誰が勝ったかを管理しておく必要があります。この管理方法は、配列を使うと少し大変になるかもしれません。それよりも、 $i$ 回戦で残っている人と $i+1$ 回戦へ進めた人を順番に更新していくほうが楽でしょう。番号の小さい方から順番に抜き出していくので、 queue で管理すると便利です。

C++で書けば、次のようになります。コードの下に、コードの説明が続きます。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {

  int N; cin >> N;
  int MAX = (1 << N);
  vector<int> ans(MAX, 0);

  queue<pair<int, int>> q;
  for (int i = 0; i < MAX; i++) {
    int a; cin >> a;
    q.push(make_pair(i, a));
  }

  for (int i = 0; i < N; i++) {
    queue<pair<int, int>> q2;
    while (!q.empty()) {
      pair<int, int> p1, p2;
      p1 = q.front(); q.pop();
      p2 = q.front(); q.pop();

      ans[p1.first] = i + 1;
      ans[p2.first] = i + 1;
      if (p1.second > p2.second) {
        q2.push(p1);
      } else {
        q2.push(p2);
      }
    }
    q = q2;
  }

  for (int i = 0; i < MAX; i++) {
    cout << ans[i] << '\n';
  }
  return 0;
}

人に $0$ から $2^N-1$ の番号をつけます。この番号と強さをペアにして、まずは queue q に入れていきます。

続いて、 $i+1$ 回戦 $(0\leqq i \lt N)$ での戦いを順番に見ていきます。 queue q から初めの2人を抜き出し、「 $i+1$ 回戦で戦った」と配列 ans に記録を残します。強い方は次に行けるので、別の queue q2 に追加します。

残ってる人がいなくなれば、次の回に進めていきます。 q2 には次に進めた人全員が入っているので、これを q に入れて繰り返していきます。

こうすれば、最終的に ans[i] には i 番目の人が何回戦まで行ったかがわかります。

queue を入れ替えなくても、人数を見れば今何回戦なのか把握することはできます。はじめに $2^4=16$ 人いたなら、1回戦では16人、2回戦では8人、3回戦では4人、4回戦では2人が残っていることになります。つまり、 $2^n$ の形になっていれば、次の回に進んだことがわかります。このことを利用して次のように書くこともできます。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {

  int N; cin >> N;
  int MAX = (1 << N);
  vector<int> ans(MAX, 0);

  queue<pair<int, int>> q;
  for (int i = 0; i < MAX; i++) {
    int a; cin >> a;
    q.push(make_pair(i, a));
  }

  int n = 0;
  while (q.size() > 1) {
    if (q.size() == (1 << (N - n))) n++;

    pair<int, int> p1, p2;
    p1 = q.front(); q.pop();
    p2 = q.front(); q.pop();

    ans[p1.first] = ans[p2.first] = n;
    if (p1.second > p2.second) q.push(p1);
    else q.push(p2);
  }

  for (int i = 0; i < MAX; i++) {
    cout << ans[i] << '\n';
  }
  return 0;
}