Zero-Sum Ranges の応用問題だけど、最初難しく考えてしまって「解けない...」となってました

類題とか

問題概要

"J" と "O" と "I" のみからなる長さ $N$ の文字列 $S$ が与えられる。 $S$ の連続する部分文字列であって、それに含まれる "J" の個数と、"O" の個数と、"I" の個数がすべて互いに等しいようなものを考える。

そのような部分文字列の長さの最大値を求めよ。

制約

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

考えたこと

累積和を使えば、 $O(N^{2})$ までは自明なのだけど、そこから先がすぐにはわからなかった。多分、平方分割とか、そういう飛び道具を使う感じではないのだろうけども...

こういうときは、文字の種類が少ないケースから考えると吉なことがあると思う。というわけで、"J" と "O" と "I" の 3 文字ではなく、"A" と "B" の 2 文字だけの場合を考えてみることにした。

2 文字だけの場合

この場合は考えやすい。次の配列を考える。

P[ i ] := 最初の i 文字についての、(A の個数) - (B の個数)

このとき、

「区間 [l, r) が条件を満たす」　⇔　 P[ l ] = P[ r ]

が成り立つのだ。あとは Zero-Sum Ranges とまったく同じ考え方で解ける。まず P の値で各 index (0, 1, ..., N) を分類してあげる。そして、次のように解ける。

各値 v に対して
P[ i ] = v となる最大の i を M、最小の i を m として
M - m の最大値を求める

3 文字になった場合

2 文字の場合とほとんど同様に解ける。

P[ i ] := 最初の i 文字についての、("O" の個数) - ("J" の個数)
Q[ i ] := 最初の i 文字についての、("I" の個数) - ("J" の個数)

とする。このとき

「区間 [l, r) が条件を満たす」　⇔　 P[ l ] = P[ r ] かつ Q[ l ] = Q[ r ]

となる！！！　よって、(P の値, Q の値) のペアで各 index (0, 1, ..., N) を分類してあげればよい。たとえば map を用いることにすると、計算量は $O(N \log N)$ となる。

コード

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

int main() {
    int N;
    string S;
    cin >> N >> S;
    long long a = 0, b = 0, c = 0;
    using pll = pair<long long, long long>;
    map<pll, vector<int>> ma;
    ma[pll(0, 0)].push_back(0);
    for (int i = 0; i < N; ++i) {
        if (S[i] == 'J') ++a;
        else if (S[i] == 'O') ++b;
        else ++c;
        ma[pll(b-a, c-a)].push_back(i+1);
    }
    int res = 0;
    for (auto it : ma) {
        auto v = it.second;
        if (v.size() < 2) continue;
        res = max(res, v.back() - v[0]);
    }
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

JOI 春合宿 2014 day3-1 JOIOJI (難易度 6)

問題概要

制約

考えたこと

2 文字だけの場合

3 文字になった場合

コード