第二回PAST I - トーナメント
問題原文
問題要旨
人でトーナメントをおこなう。 番目の人の強さは で、これらは相異なる。
トーナメントでは隣の人と戦って、より強い方が勝ち残る。これを最後の1人になるまで行う。
各人について何回戦うかを求めよ。
解法
シミュレーションをします。終わりです。(???)
半分の半分の。。。となっていくので、計算量は余裕です。
実装
優勝者がもう一度闘争を求め出してしまったで特別に処理をしました。
N = int(input()) A = list(map(int, input().split())) A = [(a, i) for i, a in enumerate(A)] ans = {} for n in range(N): winners = [] for i in range(2 ** (N - n - 1)): xa, xi = A[2 * i] ya, yi = A[2 * i + 1] if xa > ya: ans[yi] = n + 1 winners.append((xa, xi)) else: ans[xi] = n + 1 winners.append((ya, yi)) winners.sort(key=lambda x: x[1]) A = winners[:] winner = A[0][1] for n in range(2 ** N): if n == winner: print(N) else: print(ans[n])
感想
I <<<<<<<<<<< H だと思うんです。
いや別に必ずしも難易度順というわけではないんですが、 Hを一旦パスしてめっちゃ身構えて I をみたので世界が好きになりました。