ソートすると、ある位置から右に距離Kにある木が差が最小値になることが保証される。 ので、これを0からN-Kまで動かせばよい。
def solve(N, K, Hs): Hs.sort() return min([b - a for (a, b) in zip(Hs[:], Hs[K - 1:])]) if __name__ == "__main__": N, K = tuple(map(int, input().split(" "))) Hs = [int(input()) for _ in range(N)] print(solve(N, K, Hs))
昔どこかでこれのもっと大きい数字の中で特定の小範囲に対して同じように計算をしたことがある。 今回は範囲が０から必ず始まる代わりに広範囲になる。
あるN番目のバーガーは、 P / (N-1) / B / (N-1) / Pという構造になる。 そこで、Xの位置を以下５通りに場合分けする。
一番左 左側の(N-1)の途中 真ん中のB 右側の(N-1)の途中 右側のP
そしてそれぞれで、再帰含めて考える。
一番左の時、N=0でなければ必ず0、N=0ならば1 左側の(N-1)の途中のときは、一番左側の分一つ引いて、N-1へ再帰を実行。 真ん中のBの時は、上と同様に再帰を実行したうえで、真ん中のBの分プラス１する。 右側の(N-1)の途中の時は左側の再帰、真ん中のBの分、そして右側の分の再帰。 右側のPまで言っていたらN-1２つ分と真ん中のB
全体の数はa(n+1) = 2a(n) + 3なので、漸化式。高校数学の知識でN番目のバーガの厚みは計算可能。 で、あとメモ化すれば、O(logN)でいける。
memo = {}
def solve(N, X):
if (N, X) not in memo:
l = (pow(2, N + 2) - 3)
l2 = (l - 3) // 2 + 1
if N == 0:
return 1
if X == 1:
return 0
elif X <= l2:
memo[(N, X)] = solve(N - 1, X - 1)
elif X == l2 + 1:
memo[(N, X)] = solve(N - 1, l2 - 1) + 1
elif X < l:
left = solve(N - 1, l2 - 1)
right = solve(N - 1, X - 1 - l2)
memo[(N, X)] = left + 1 + right
elif X == l:
memo[(N, X)] = solve(N - 1, l2 - 1) * 2 + 1
return memo[(N, X)]
if __name__ == "__main__":
N, X = tuple(map(int, input().split(" ")))
print(solve(N, X))
特定の小範囲でやっていた時には一つの場所を特定するためにある特定の位置だけ渡して、再帰を行ったが、 今回はカウントなのでそれをしてしまうとループカウントで時間切れになってしまう。 ので、大まかに再帰を切ってカウントにする。メモ化はNとXにしたがNだけでもこれよかったな。
境界値あたり、特に０や１が混じったり真ん中の数値あたりは頭の中で作るのが難しい。 かなり時間食ってしまった。
