第二回 アルゴリズム実技検定 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;
}