クルトンのプログラミング教室

Pythonの使い方やPythonを使った競技プログラミングの解法などを解説しています。

Pythonで理解する蟻本「2-2 Saruman's Army（POJ 3069）」(p.47)

Pythonで理解する蟻本（プログラミングコンテストチャレンジブック）

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の
「2-2 Saruman's Army（POJ 3069）」(p.47)
のコードをPythonで書き直したものとなっています。

入力

N\,R\\X_{1}\,X_{2}\,…\,X_{n}

入力例



6 10
1 7 15 20 30 50


解答

N, R = map(int,input().split())
X = list(map(int,input().split()))

X.sort()

i = 0
ans = 0
while i < N:
    # sはカバーされていない一番左の点の位置
    s = X[i]
    i += 1
    # sから距離Rを超える点まで進む
    while i < N and X[i] <= s + R:
        i += 1
    
    # pは新しく印を付ける点の位置
    p = X[i - 1]
    # pから距離Rを超える点まで進む
    while i < N and X[i] <= p + R:
        i += 1
    ans += 1

print(ans)