ARC059 - D

D - アンバランス / Unbalanced

問題ページ

ぱっと見てしゃくとりか累積和っぽいなと思ったけど，
よく考えたら高々連続する 3 文字に着目すればいいっぽい

abcaab

という文字列において a が過半数となる場合があるか調べたいとき，しゃくとりの要領で

a
ab
abc

のように区間を広げていくと，

abc

で a の個数をそれ以外の個数が上回るが，
この時点でこの区間を調べる区間に含める意味はなくなる

全然うまく説明できる気がしないので，
似た考え方をする最大部分列和の解説を貼っておく

結局幅 3 の区間をスライドさせて，ある文字が
2 文字以上現れるような区間が存在するかどうかを調べればいい
(|S| = 2 の例外に注意)

int main() {

    cin.tie(0);
    ios::sync_with_stdio(false);

    string S;
    cin >> S;
    int n = S.size();
    
    if (n == 2) {
        if (S[0] == S[1])
            cout << 1 << " " << 2 << endl;
        else
            cout << -1 << " " << -1 << endl;
        return 0;
    }

    vector<vector<int>> v(26, vector<int>(n, 0));
    for (int i = 0; i < 26; i++)
        for (int j = 0; j < n; j++)
            if (S[j] == i + 'a')
                v[i][j]++;

    for (int i = 0; i < 26; i++) {
        for (int j = 0; j < n - 2; j++) {
            int s = v[i][j] + v[i][j + 1] + v[i][j + 2];
            if (s >= 2) {
                cout << j + 1 << " " << j + 3 << endl;
                return 0;
            }
        }
    }
    cout << -1 << " " << -1 << endl;
    return 0;
}

Submission #2623266 - AtCoder Regular Contest 059