Daily AtCoder # 3 in Python

Introduction

Last time It's the third day.

** Thoughts ** 1WA, 4TLE (WA submitted a mistake) The biggest enemy this time was TLE. I don't have an image of computational complexity, but I didn't know the internal implementation of Python. Looking at the problem, I got a habit of sorting the problem of finding the maximum and minimum values for the time being. At first, I thought that the minimum value would come out if I subtracted in order with for,

l = [10,15,11,14,12]
l.sort(reverse=True) #l = [15,14,12,11,10]
ans = l[0]
for i in range(n-1):
    ans = min(l[i+1] - l[i],ans)

I thought it would work with. However, it is necessary to find the minimum value among k selected from n. Therefore, it is necessary to extract k sorted inputs and max-min among them. When I thought about how to take k by k, I used slices because the Python list has slices. This was a big mistake. Apparently ** Python slicing takes ultra time when done on large objects **. If you know the reason, please let me know. Is it taking a long time to access the object? So, the one who TLE using slices

n, k = map(int,input().split())
h = [int(input()) for i in range(n)]
h.sort(reverse=True)

seed = h[0]
for i in range(0,n-k+1):
    high = h[i:i+k][0] - h[i:i+k][k-1] #here
    seed = min(high,seed)

print(seed)

I'm spending time slicing the comment part. Even if I mean it, tax_free that I want to slice has been TLEed 4 times. If you think about it now, you can specify it by index without slicing it separately.

It turned out that the slice was eating for a long time, so this is what I specified in the index

n, k = map(int,input().split())
h = [int(input()) for i in range(n)]
h.sort(reverse=True)

seed = h[0]
for i in range(0,n-k+1):
    high = h[i] - h[i+k-1]
    seed = min(high,seed)

print(seed)

Not sliced.

Summary

I didn't understand how Python feels. From now on, specify by index directly without using slices. see you