The cow mega-city Bovinopolis is redistricting! -- always a contentious
political process between the two major cow breeds (Holsteins and Guernseys)
living there, since both breeds want to make sure they retain sufficient
influence in the Bovinopolis government.

The greater metropolitan area of
Bovinopolis consists of a line of \(N\) pastures (\(1 \leq N \leq 3 \cdot 10^5\)),
each containing a single cow, which is either a Holstein or a Guernsey.

The government of Bovinopolis wants to divide the greater metropolitan area into
some number of contiguous districts, so that each district contains at most \(K\)
pastures (\(1 \leq K \leq N\)), and every pasture is contained in exactly one
district. Since the government is currently controlled by Holsteins, they want
to find a way to redistrict which minimizes the number of Guernsey-majority or
tied districts (a district is tied if the number of Guernseys equals the number
of Holsteins).

A concerned coalition of Guernseys is trying to figure out how much damage might
be done by the government's redistricting. Help them figure out the worst-case
minimum number of districts which are either Guernsey-majority or tied.

Problem credits: Dhruv Rohatgi

Problem credits: Dhruv Rohatgi

The first line contains a two space-separated integers \(N\) and \(K\). The second
line contains a string of length \(N\). Each character is either 'H' or 'G', for
Holstein or Guernsey.

Please output the minimum possible number of districts that are
Guernsey-majority or tied.

riseoj 작성

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