面白かった

問題へのリンク

問題概要

文字列 $t$ がアンバランスであるとは、

$|t| \ge 2$
$t$ の中の文字のうち、過半数が同じ文字

であることを指すものとする。長さ $N$ の文字列 $S$ が与えられたとき、 $S$ の連続する部分文字列であって、アンバランスなものがあるかどうかを判定せよ。存在するならば具体的な区間を答えよ。

制約

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

考えたこと

まともに区間すべてを列挙して、それがアンバランスかどうかを判定したら $O(N^{3})$ かかってしまう (区間が $O(N^{2})$ 個で判定が $O(N)$ )。

そこで一つの手段として「累積和を使う」とかがあるんだけど、どうにも要領が掴めない。そこでもう一つの典型視点として

「各文字について考えてみる」

というのがあると思う。アルファベットは 26 文字しかないので、各文字についての問題が $O(N)$ や $O(N \log N)$ で解ければ十分だ！！

各文字についての問題

たとえば英小文字 'a' が、ある区間において過半数個存在するかどうかを判定する問題を考えてみよう。

まず 'a' が連続している箇所があったら確実に OK。"aa" がすでにアンバランスなので！！
次に 'a' が 1 文字空けて存在している箇所があっても確実に OK。"axa" とかがすでにアンバランスなので！！

ここまではすぐにわかる。そして実はこの時点ですでに核心を突いている。'a' が 2 文字以上間を空けて離れている文字列だと、'a' が過半数を占めることは絶対にないのだ！！！

"a??a??a??a??a..."

というふうにしたとき、'a' が過半数になることは絶対にない。というわけで、われわれはいきなり正解に辿り着いた。

文字列 $S$ において

同じ文字が連続している箇所
同じ文字が 1 文字間を空けて存在している箇所

が存在すれば Yes、存在しなければ No

計算量は $O(N)$ となる。

コード

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

int main() {
    string S;
    cin >> S;
    int l = -1, r = -1;
    for (int i = 0; i+1 < S.size(); ++i) {
        if (S[i] == S[i+1]) l = i+1, r = i+2;
        if (i+2 < S.size() && S[i] == S[i+2]) l = i+1, r = i+3;
    }
    cout << l << " " << r << endl;
}

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

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

AtCoder ABC 043 D - アンバランス (ARC 059 D) (水色, 400 点)

問題概要

制約

考えたこと

各文字についての問題

コード