はじめに
前回
三日目です。
#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で指定します。
では、また