【ABC188 C】「ABC Tournament」を解く【Python3】

コンテスト一覧へ

 

レートAiである2N人の選手がトーナメント形式のプログラミング対決をするとき、準優勝する選手の番号を求める問題です。

提出
import collections

n = int(input())
a = list(map(int, input().split()))

q = collections.deque(a)

while len(q)>2:
    k = q.popleft()
    l = q.popleft()
    q.append(max(k,l))

mn = min(q)
print(a.index(mn)+1)

collectionsモジュールの deque() を使うと、両端の要素を追加・削除する際に時間コストを短く済ませることができます。

popleft() で左端から要素を取り出します。

2つ取り出して、大きい方を q の右端に加えます。

これを q の長さが2以下になるまで続けることで、トーナメントのシミュレーションができます。

最後に二人残っているので小さい方のインデックスを出力します

 

このほか、トーナメント表を半分にして、左右の max() を取得して求める方法もあります。

提出
n = int(input())
a = list(map(int, input().split()))

num = min(max(a[:2**(n-1)]),max(a[2**(n-1):]))
print(a.index(num)+1)

トーナメント表を半分にして、左半分をα、右半分をβとします。

すると、決勝戦で戦うのは、α、βのそれぞれで最大レートである選手です。

2人の中で低いほうが準優勝するので、そちらのインデックスを出力します。

【ABC188】解説記事リスト

コンテスト一覧に戻る

コメントを残す

メールアドレスが公開されることはありません。