ABC188 C問題 with python3

ABC188 C問題 ABC Tournament

ひとこと

リストでremove()を使ったせいでtleで不正解になってしまった。C問題からは計算量オーダーを意識したい。

正解コード

N=int(input())
A=list(map(int,input().split()))
survive=list(range(1,2**N+1))


for j in range(N-1):
    winner=[]
    for k in range(0, len(survive), 2):
        first=survive[k]
        second=survive[k+1]
        if A[first-1]>A[second-1]:
            winner.append(first)
        else:
            winner.append(second)
    survive=winner

first=survive[0]
second=survive[1]
if A[first-1]>A[second-1]:
    print(second)
else:
    print(first)

解説

まず全員分のデータを入れたリストを作る。そこからトーナメントで負けた人をリストから削除していき、残った二人のうちレートの低い方の番号を出力すれば良い。
ここで負けた人のデータを削除していくリストの作り方は２通り考えられる。
レートのデータを格納したリストを作るか番号のデータを格納したリストを作るかだ。

前者の場合出力したいデータが番号なのに対して残ったデータがレートになってしまうので番号順にレートを格納したリストを別にとっておいてレートのインデックスを調べる必要があり手間がかかる。
後者の場合残った番号をそのまま出力すればいいだけなので番号のデータを格納したリストを作ることにする。

リストから敗者の番号を消していく方法は単純にremove()を使うと消えた分データのインデックスがずれて面倒なので残っている人の番号を格納するsurviveリストと勝った人の番号を格納する空のwinnerリストを作り、surviveリストの内から勝った方だけwinnerリストに追加していく。処理が一周終わったらsurvive=winnerとする。これを繰り返すことで実装する。

この方法はリストから特定の条件を満たす要素を削除したい　かつ　削除する条件にインデックスが絡んでくる時に使うと上手くいく。

簡単な類題

リストA=[2,3,1,5,6,7,3]からインデックスが奇数の要素を削除したものを出力せよ

回答

A=[2,3,1,5,6,7,3]
ans=[]
for i in range(len(A)):
    if i%2==0:
        ans.append(A[i])
print(ans)
#ちゃんと答えが[2,1,6,3]になるはずです。

まとめ

・実装方法が２つ考えられるときはある程度先までシュミレートして楽な方を選ぶ
・リストから特定の条件を満たす要素を削除したい　かつ　削除する条件にインデックスが絡んでくる時は空のリストを用意してそこに生き残った要素を入れていけば良い