頁面無法載入？點擊這裡可能會修復。
Placeholder

#8444
子任務

K-비둘기 1s 512MB

問題

전깃줄 위에 일렬로 N마리의 비둘기가 앉아 있다. 왼쪽에서부터 1, 2, 3, \dots , N번 비둘기이다.

각 비둘기는 오른쪽 또는 왼쪽을 바라보고 있다.

비둘기는 특정한 규칙에 따라 운다.

  • i번 비둘기가 왼쪽을 바라보고 있다면, 자신보다 왼쪽에 있으면서 오른쪽을 바라보는 비둘기의 수만큼 운다.

  • i번 비둘기가 오른쪽을 바라보고 있다면, 자신보다 오른쪽에 있으면서 왼쪽을 바라보는 비둘기의 수만큼 운다.

정올이는 모든 비둘기가 우는 횟수를 다 더하고 싶은데, 머리가 좋지 않다.

그래서, 연속된 K 마리의 비둘기만 고려할 수 있다.

예를 들어, N=6,~ K=4 이고, 비둘기의 방향이 RLRLLR ( L : 왼쪽, R : 오른쪽) 이라고 하자.

정올이는 연속된 4 개의 비둘기만 고려할 수 있다.

1번째 ~ 4번째 비둘기 : RLRL 이고, 이 때 모든 비둘기가 우는 횟수는 2 + 1 + 1 + 2 = 6 회다.

2번째 ~ 5번째 비둘기 : LRLL 이고, 이 때 모든 비둘기가 우는 횟수는 0 + 2 + 1 + 1 = 4 회다.

3번째 ~ 6번째 비둘기 : RLLR 이고, 이 때 모든 비둘기가 우는 횟수는 2 + 1 + 1 + 0 = 4 회다.

연속된 K 마리 비둘기의 구간은 총 N-K+1 개 존재한다.

각 구간 별로, 모든 비둘기가 우는 횟수를 구하여 출력하자.


輸入

첫 줄에 N 과 K 가 입력된다. ( 1 ≤ N ≤ 200,000 , 1≤K ≤ N ~~)

두 번째 줄에 N 마리의 비둘기들이 바라보는 방향이 L 또는 R 로 주어진다. ( 길이 N 의 문자열 )


輸出

i = 1,~~ 2,~~ ...~, ~~N-K+1 에 대하여,

i 번째 비둘기부터 시작하여 연속된 K 마리의 비둘기만 고려했을 때,

모든 비둘기가 우는 횟수의 합을 공백으로 구분하여 출력한다.


子任務

編號 分數 條件
#120分

입력되는 문자열은 항상 RLRL... 형태다.

( R 부터 시작하여 번갈아 나타나는 형태 )

#220分

1 ≤ N ≤ 100

#320分

1 ≤ N ≤ 1,000

#440分

제약 조건 없음


範例 #1

6 4
RLRLLR
6 4 4

範例 #2

10 5
LRLRLRLRLR
6 6 6 6 6 6

範例 #3

10 6
RLRLRLRLRL
12 6 12 6 12

範例 #4

10 4
RLRRLLRRLR
2 4 8 4 0 4 4


來源

againalgo
需要登入才能撰寫程式碼。