AtCoder ABC 379 B - Strawberries (5Q, 灰色, 200 点)

ランレングス圧縮！

• 問題へのリンク

問題概要

文字 'O', 'X' からなる長さ の文字列 が与えられる。

「'O' のみからなる連続 個の文字をすべて 'X' に書き換える」という操作を最大で何回行えるか？

制約

• 

考えたこと

ランレングス圧縮が有効な問題。ランレングス圧縮はたとえば

"OOOOOOXXXOXXXX"

のような文字列を

('O', 6), ('X', 3), ('O', 1), ('X', 4)

のような情報に圧縮するアルゴリズムだ。これができれば、'O' からなる各区間について、その個数を で割った商を足していけばよい。

ランレングス圧縮のやり方は、下のコードを参照。計算量は となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, K;
    string S;
    cin >> N >> K >> S;

    int res = 0;
    for (int i = 0; i < N; ) {
        if (S[i] == 'X') {
            i++;
            continue;
        }

        int j = i;
        while (j < N && S[j] == 'O') j++;
        res += (j - i) / K;
        i = j;
    }
    cout << res << endl;
}