AtCoder Beginner Contest 188 C - ABC Tournament

問題

問題文へ

選手1から選手までの人の選手がトーナメント形式のプログラミング対決をします。

選手iのレートはです。どの2人の選手のレートも異なり、2人の選手が対戦すると常にレートが高いほうが勝ちます。

トーナメント票は完全二分木の形をしています。より正確には、このトーナメントは以下の要領で行われます。

• i=1,2,3,...,Nについて順に、以下のことが行われる。
  • 各整数j（）について、まだ負けたことのない選手のうち、盤面番号の小さい選手と番目に小さい選手が対戦する。

準優勝する、すなわち最後に行われる対戦において負ける選手の番号を求めてください。

制約

• 
• 
• は相違なる
• 入力に含まれる値はすべて整数である。

考えたこと

制約より、トーナメントをシミュレートしても間に合うと考えました。番号とレートをペアにして、結果を前に詰めていくことで配列を1つですませました。

コード

#define _GIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;


int main(void) {
    ll N;
    cin >> N;

    ll num = 2 << (N-1);
    vector<pair<int, int>> A(num);
    rep(i, num) {
        A[i].first = i + 1;
        cin >> A[i].second;
    }

    num /= 2;
    for (int i = 0; i < N - 1; ++i) {
        for (int j = 0; j < num; ++j) {
            if (A[j * 2].second > A[j * 2 + 1].second) {
                A[j].first = A[j * 2].first;
                A[j].second = A[j * 2].second;
            } else {
                A[j].first = A[j * 2 + 1].first;
                A[j].second = A[j * 2 + 1].second;
            }
        }
    }

    if (A[0].second < A[1].second) {
        cout << A[0].first << endl;
    } else {
        cout << A[1].first << endl;
    }
    
    return 0;
}

解説を読んで

トーナメントの前半と後半でわける、キューを使う。自分には発想することはむずかしいかもしれません。経験値を増やして思い出す形にしたいです。