ABC188 C - ABC Tournament を解いた

文章の通りやってみた。

abc188c.py

N = int(input())
A = list(map(int, input().split()))

dic = {}
for i in range(2**N):
    dic[A[i]] = i+1

lis = A[:]
if N == 1:
    print(dic[min(lis)])
    exit()
while True:
    nums = []
    for i in range(0,len(lis)-1, 2):
        nums.append(max(lis[i], lis[i+1]))
    lis = nums
    if len(lis) == 2:
        break

print(dic[min(lis)])

上記で通ると確証があったわけではない、計算量が不明だったから。。。
今回は数えてみた。
計算用に以下のコードを用意。

cal_On.py

N = 2**16  #入力最大値
score = 0  #計算量カウント

for _ in range(1,2**16+1):
    score += N//2#for 文では2 飛ばしてカウントするので計算量は N//2
    N//=2        #N を 1/2 倍に更新
print(score)

# result
# score = 65535

O(65535) だったら計算量としては余裕。
だから問題ないわけだ、納得。