루미 알고리즘

#1133플래티넘점프점프

KOI 2026 1차코딩고등부 3번출제 이유찬이 문제가 어렵다면 — 배우는 순서 보기

원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)

점프

원제: 점프

문제

이차원 좌표 평면에 11번부터 NN번까지 번호가 부여된 NN개의 발판이 있다. 각 발판은 좌표 평면 위의 한 점으로 표현할 수 있고, ii (1≤i≤N1 \le i \le N)번 발판의 위치 좌표는 (Xi,i)(X_i, i)이다.

두 정수 ii, jj (1≤i,j≤N1 \le i, j \le N)에 대해, 아래의 두 조건을 모두 만족할 때에만 ii번 발판에서 jj번 발판으로 이동할 수 있다.

  • i<ji < j
  • ∣Xi−Xj∣≤D|X_i - X_j| \le D

여기서, DD는 주어지는 상수이며, 양의 정수 값을 가진다.

각 발판에 대하여, 그 발판에서 시작해서 다른 발판으로 이동하는 것을 00번 이상 반복하여 도달할 수 있는 서로 다른 발판의 개수를 세는 프로그램을 작성하라. 이 개수에는 그 발판 자기 자신도 포함되어야 함에 유의하라.

제약 조건

  • 주어지는 모든 수는 정수이다.
  • 1≤N≤300 0001 \le N \le 300\,000
  • 1≤D≤1091 \le D \le 10^9
  • 정수 ii (1≤i≤N1 \le i \le N)에 대하여 1≤Xi≤1091 \le X_i \le 10^9

부분문제

  1. (12점) N≤300N \le 300
  2. (32점) N≤7 500N \le 7\,500
  3. (9점) X1≤X2≤⋯≤XNX_1 \le X_2 \le \cdots \le X_N
  4. (23점) 정수 ii (1≤i≤N1 \le i \le N)에 대하여 Xi≤30X_i \le 30
  5. (33점) D=1D = 1
  6. (41점) 추가적인 제약 조건 없음.

입력 형식

첫 줄에 두 정수 NN, DD가 공백으로 구분되어 차례대로 주어진다.

그다음 줄에 NN개의 정수 X1,X2,⋯ ,XNX_1, X_2, \cdots, X_N이 공백으로 구분되어 차례대로 주어진다.

출력 형식

첫 줄에 NN개의 정수를 공백으로 구분하여 출력한다. 이 중 ii번째 정수는 ii번 발판에서 시작해서 다른 발판으로 이동하는 것을 00번 이상 반복하여 도달할 수 있는 서로 다른 발판의 개수를 의미한다 (1≤i≤N1 \le i \le N).

예제

예제 1

입력
6 2
3 5 4 6 1 3
출력
6 4 3 1 2 1

각 발판에 대하여 해당 발판에서 시작해서 도달할 수 있는 발판은 다음과 같다.

  • 11번 발판: 11번 발판을 포함하여 모든 발판으로 도달 가능하다.
  • 22번 발판: 22, 33, 44, 66번 발판으로 도달 가능하다.
  • 33번 발판: 33, 44, 66번 발판으로 도달 가능하다.
  • 44번 발판: 44번 발판을 제외하고 도달할 수 있는 발판이 없다.
  • 55번 발판: 55, 66번 발판으로 도달 가능하다.
  • 66번 발판: 66번 발판을 제외하고 도달할 수 있는 발판이 없다.

예제 2

입력
6 3
1 4 8 9 10 15
출력
2 1 3 2 1 1

예제 3

입력
3 2
1 4 7
출력
1 1 1

자료

출처 표기

출처: 한국정보올림피아드(KOI) 2026년 1차 대회 · 원문 페이지 · 이용 조건 CC BY-NC-SA 4.0 · 원문 그대로 실었으며 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-비영리-동일조건변경허락 4.0 국제. 비영리 목적으로만 이용할 수 있습니다.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.