Pythonで毎日AtCoder #3

はじめに

前回
三日目です。

#3

問題

考えたこと
1WA,4TLE (WAはミス提出)
今回最大の敵は、TLEでした。自分が計算量のイメージがついていないというのもありますが、Pythonの内部的な実装を知りませんでした。
問題を見て、最大値や最小値を求める問題はとりあえずsortするという癖が出てsortしました。最初は、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)

で動くと思いました。ですが、nからk本選んだ中の最小値を求める必要があります。
ですので、sortしたinputをk個ずつ抜いていって、そのなかでmax-minする必要があります。
どうやって、kずつ取るかを考えたときにPythonのlistはスライスがあるじゃんということでスライスを使いました。これが大失敗でした。どうやらPythonのスライスは大きなオブジェクトに対して行うと、ウルトラ時間がかかります。
理由分かる方は、教えてください。オブジェクトへのアクセスに時間がかかってる?
ということで、スライスを使ってTLEしたやつは、

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] #ここ
    seed = min(high,seed)

print(seed)

コメントの部分のスライスで時間を食っています。
意地でも、スライスしたいtax_freeは4回もTLEしました。今考えると、別にスライスしなくてもindexで指定すればいいじゃん

スライスが時間食ってるということが判明したので、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)

スライスしてません。

まとめ

Pythonの気持ちを理解していませんでした。今後はスライスを使用しないで直接indexで指定します。
では、また