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

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

• ジャッジページへのリンク
• 問題へのリンク
• editorial

類題とか

drken1215.hatenablog.com

問題概要

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

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

制約

• 

考えたこと

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

こういうときは、文字の種類が少ないケースから考えると吉なことがあると思う。というわけで、"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 を用いることにすると、計算量は となる。

コード

#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;
}