🐡

# ABC188 C - ABC Tournament

2021/01/11に公開

競技プログラミング

AtCoder

abc188

tech

ABC188 C - ABC Tournament

問題へのリンク

問題概要

$2^N$ 人の人選手がトーナメントを行う。選手 $i$ のレートは $A_i$ であり、どの２人の選手のレートも異なり、常にレートが高い方が勝つ。
準優勝する、すなわち最後に行われる対戦において負ける選手の番号を求めよ。

制約

$1 \leqq N \leqq 16$

ABC中の解答

トーナメントの準優勝者を見つける問題。 $1 \leqq N \leqq 16$ の制約だったので愚直にやっても TLE にはならないと判断して、以下の関数 $f$ を実装して最後の試合まですすめるために $N - 1$ 回繰り返した。
出力は選手の番号であり同じ値のレートの選手はいないので最後にindexを調べるために配列をなめて選手の番号を求めた。

import sys
import numpy as np

input = sys.stdin.buffer.readline
N = int(input())
A = np.array(list(map(int, input().split())))
_A = A


def f(arr):
    new_arr = np.zeros((len(arr) // 2), dtype='int')
    for i in range(0, len(arr), 2):
        new_arr[i // 2] = max(arr[i], arr[i + 1])
    return new_arr


for _ in range(N - 1):
    A = f(A)

second = min(A)
for i, a in enumerate(_A, start=1):
    if second == a:
        print(i)

解法2

evimaさんが内包表記を使えばより簡単にかけることを示していたのでメモ
後からindexを調べるために配列をなめる必要もないように $p$ にindexの情報も含めているところもうまいと思った。関数 max はデフォルトでは１つ目の要素が等しい時のみ２つ目以降の要素で比較するようだ。

N = int(input())
A = list(map(int, input().split()))
p = [(A[i], i + 1) for i in range(len(A))]
while len(p) > 2:
    p = [max(p[i * 2], p[i * 2 + 1]) for i in range(len(p) // 2)]
print(min(p)[1])

公式解法２

準優勝は 優勝者と反対の山で一番レートが大きい人 だそうだ。確かに！と思った。
したがって参加者を半分に分けてそれぞれの山の最大値をとり、その２つの値のうち小さい方が準優勝、大きいほうが優勝者となる。

N = int(input())
A = list(map(int, input().split()))
v = min(max(A[:2**N // 2]), max(A[2**N // 2:]))
for i, a in enumerate(A, start=1):
    if a == v:
        print(i)

evimaさんのようにindexを参照するなら以下のようになる。

N = int(input())
A = [(a, i) for i, a in enumerate(map(int, input().split()), start=1)]
v = min(max(A[:2**N // 2]), max(A[2**N // 2:]))
print(v[1])