Sashiming String [灘校75回生中学卒業記念コンテスト]

https://www.hackerrank.com/contests/75th/challenges/sashiming-string

解説

https://www.hackerrank.com/contests/75th/challenges/sashiming-string/submissions/code/1321979741

まず、何かしらの全探索対象を探す。
特徴的なのは、Sとingの位置なので、この2つの場所を全探索する。
2つを全探索すると10¹⁰通りとなり、これは間に合わない。

これを工夫するが、何となく区間の列挙に全探索方法が似ている。
区間全探索の有名テクは「片方の歌詞を全探索して、もう片方を効率よく数える」というテクである。
今回は右端であるingを固定したときに有効なSの個数を数えよう。
ingを固定すると、有効なSはそれより前にあるSの個数なので、先頭から順番にingを確認しながら、
Sの個数を足し合わせていくと、ingを処理するときにそれまでのSの個数が数えられている。
それを足し合わせていくと答え。

string S;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S;
    int N = S.length();

    ll ans = 0;
    int s = 0;
    rep(i, 0, N - 2) {
        if (S[i] == 'S') s++;
        else if (S.substr(i, 3) == "ing") ans += s;
    }
    cout << ans << endl;
}