RiseOJ – 선거구 재획정

설명

소들의 거대 도시 보비노폴리스가 선거구를 재획정한다! -- 이곳에 사는 두 주요 소 품종 (홀스타인과 건지) 사이에서는 언제나 논쟁이 치열한 정치적 과정인데, 두 품종 모두 보비노폴리스 정부에서 충분한 영향력을 유지하고 싶어하기 때문이다.

보비노폴리스 대도시권은 한 줄로 늘어선 $$N$$ 개의 목초지 ( $1 \leq N \leq 3 \cdot 10^5$ )로 이루어져 있으며, 각 목초지에는 소가 한 마리씩 있고, 각 소는 홀스타인이거나 건지이다.

보비노폴리스 정부는 대도시권을 몇 개의 연속한 선거구로 나누되, 각 선거구가 최대 $$K$$ 개의 목초지 ( $1 \leq K \leq N$ )를 포함하고, 모든 목초지가 정확히 하나의 선거구에 포함되도록 하고 싶어한다. 현재 정부는 홀스타인이 장악하고 있으므로, 건지가 다수이거나 동수인 선거구 (건지의 수가 홀스타인의 수와 같으면 동수인 선거구이다)의 수를 최소화하는 재획정 방법을 찾고자 한다.

건지들의 우려 연합은 정부의 선거구 재획정으로 얼마나 큰 피해를 입을 수 있는지 알아내려 한다. 건지가 다수이거나 동수인 선거구 수의 최악의 경우 최솟값을 알아내도록 도와주자.

출제자: Dhruv Rohatgi

제약

출제자: Dhruv Rohatgi

입력 형식

첫째 줄에 공백으로 구분된 두 정수 $$N$$ 과 $$K$$ 가 주어진다. 둘째 줄에 길이 $$N$$ 의 문자열이 주어진다. 각 문자는 홀스타인을 뜻하는 'H' 또는 건지를 뜻하는 'G'이다.

출력 형식

건지가 다수이거나 동수인 선거구 수의 가능한 최솟값을 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 redistricting.in · 출력을 쓸 파일 redistricting.out

예제 1

입력

7 2
HGHGGHG

출력

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2018-2019 > January > Platinum

올림피아드 > USACO > 2018-2019 > January > Platinum

태그

JudgeUSACO

선거구 재획정

평가 및 의견

풀이 제출