ABC115 Christmas Eve Python 3

問題：https://atcoder.jp/contests/abc115/tasks/abc115_c

ランダムに並んだN個の整数列の内から、K個の整数を選び、選んだ整数の中での最大値と最小値との間の差が最小になる値を回答する問題。N,Kともに10^5オーダーなので、まともに組み合わせを全探索していてはとても間に合いません。

しかし数列をいったんソートしてから、先頭から順に1～K番目、2～K+1番目、3～K＋2番目、、、という具合に探索していけばO(N)で間に合います。

コード例

pythonでの実装例です。

N,K=map(int,input().split())
h=[int(input())for _ in range(N)]
h.sort()
ans=10**10
for i in range(N-K+1):
	tmp=h[i+K-1]-h[i]
	if tmp<ans:
		ans=tmp
print(ans)

for分で頭から順に、i番目の値と、i+K-1番目の値の差を求めていき、その中の最小値を回答すればOKです。

最小値を判定するfor文のコード

N,K=map(int,input().split())
h=[int(input())for _ in range(N)]
h.sort()
print(min(h[i+K-1]-h[i]for i in range(N-K+1)))

公式回答PDFでは、最小値を求めるコードが上記のように1行で書かれていました。競プロでは回答するまでの速度が重要なので、短くコーディングできる記法は覚えていきたいところです。