問題概要

"J" と "O" と "I" のみからなる長さ $N$ の文字列 $S$ が与えられる。ところで、レベル $K$ の JOI 文字列とは、"JJ...JOO...OII...I" (それぞれ $K$ 個ずつ) のことを指すものとする。

文字列 $S$ に以下の操作を施すことで、レベル $K$ の JOI 文字列となるようにしたい。そのための最小コストを求めよ。実現不可能である場合は -1 と出力せよ。

先頭の文字を削除する (コスト 0)
末尾の文字を削除する (コスト 0)
先頭と末尾以外の文字を削除する (コスト 1)

制約

$3 \le N \le 2 \times 10^{5}$

考えたこと

問題を言い換えると、次のようになる。

OJIJOIOIIJOOOOOJJOJIJI

のような文字列の連続する区間であって、

左から "J" が $K$ 個
その残りの左から "O" が $K$ 個
その残りの左から "I" が $K$ 個

がとれる「最小の長さの区間」を求める問題だと言える。上の例で言えばたとえば

O | JIJOIOII | JOOOOOJJOJIJI

のようにして、| で挟まれた区間が最小の長さになっている。

始点の "J" を固定する

始点の J を固定したとき、左から Greedy に解くことができる。このとき、各 i に対して、次の値が高速に求められたら嬉しい。

S[ i ] == "J" であるような各 i に対して、そこから "J" を $K$ 回繰り返したあとで最初に出てくる "O" の index
S[ j ] == "O" であるような各 j に対して、そこから "O" を $K$ 回繰り返したあとで最初に出てくる "I" の index

これは、二分探索 (lower_bound) やしゃくとり法で求めることができる。二分探索を用いると計算量は $O(N \log N)$ に、しゃくとり法を用いると計算量は $O(N)$ になる。

二分探索法

下のコードでは、

ij：S[ i ] == "J" となる i の集合
io：S[ i ] == "O" となる i の集合
ii：S[ i ] == "I" となる i の集合

を用意している。

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

int main() {
    int N, K;
    string S;
    cin >> N >> K >> S;
    vector<int> ij, io, ii;
    for (int i = 0; i < N; ++i) {
        if (S[i] == 'J') ij.push_back(i);
        else if (S[i] == 'O') io.push_back(i);
        else ii.push_back(i);
    }
    int res = N+1;
    for (int i = 0; i+K-1 < ij.size(); ++i) {
        int from = ij[i];
        auto j = lower_bound(io.begin(), io.end(), ij[i+K-1]) - io.begin();
        if (j+K-1 >= io.size()) continue;
        auto k = lower_bound(ii.begin(), ii.end(), io[j+K-1]) - ii.begin();
        if (k+K-1 >= ii.size()) continue;
        int to = ii[k+K-1] + 1;
        res = min(res, to - from - K*3);
    }
    cout << (res <= N ? res : -1) << endl;
}

しゃくとり法

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

int main() {
    int N, K;
    string S;
    cin >> N >> K >> S;
    vector<int> ij, io, ii;
    for (int i = 0; i < N; ++i) {
        if (S[i] == 'J') ij.push_back(i);
        else if (S[i] == 'O') io.push_back(i);
        else ii.push_back(i);
    }

    // J -> O
    vector<int> nextJO(ij.size(), -1);
    int right = 0;
    for (int left = 0; left+K-1 < ij.size(); ++left) {
        while (right < io.size() && io[right] <= ij[left+K-1]) ++right;
        if (right < io.size()) nextJO[left] = right;
    }
    // O -> K
    vector<int> nextOK(io.size(), -1);
    right = 0;
    for (int left = 0; left+K-1 < io.size(); ++left) {
        while (right < ii.size() && ii[right] <= io[left+K-1]) ++right;
        if (right < ii.size()) nextOK[left] = right;
    }

    // 集計
    int res = N+1;
    for (int i = 0; i+K-1 < ij.size(); ++i) {
        int from = ij[i];
        int j = nextJO[i];
        if (j == -1) continue;
        j = nextOK[j];
        if (j == -1 || j+K-1 >= ii.size()) continue;
        int to = ii[j+K-1];
        res = min(res, to - from + 1 - K*3);
    }
    cout << (res <= N ? res : -1) << endl;
}