[ABC353] E - Yet Another Sigma Problem

[Q] E - Yet Another Sigma Problem

考察
0. Sが最大3e5文字の文字列が来るんだけど、なんと|S|の総和も3e5。
0. 1文字ずつ考えたとして、O(|S|log|S|)が間に合う。
1. とりあえず受け取った文字列を昇順にsortする
2. S="abcd"があった場合。
・1文字の"a"がどれだけ合致しているかを考える。
it = lower_bound("b")をとれば、[S, it)の数だけaが合致している。

・2文字の"ab"がどれだけ合致しているかを考えて、bの分だけ加算したい。
it = lower_bound("ac")をとれば、[S, it)の数だけbが合致している。

・3文字の"abc"がどれだけ合致しているかを考えて、cの分だけ加算したい。
it = lower_bound("abd")をとれば、[S, it)の数だけcが合致している。

・4文字の"abcd"がどれだけ合致しているかを考えて、dの分だけ加算…
it = lower_bound("abce")をとれば、[S, it)の数だけdが合致している。

といったことをやりたい。
3. 入力例2を考える

入力例2をsortする。
S[0]: a
S[1]: a
S[2]: aaa
S[3]: aaaba
S[4]: aabbb
S[5]: ab
S[6]: b
S[7]: baba
S[8]: babb
S[9]: bb
S[A]: bba

S[0] = "a"を考える。
1文字目がaなので、'a' + 1 = "b"でlower_bound("b")をとる。
S[6] = "b"が引っかかるので、S[1] ~ S[5]の5通りが答えに加算。

S[1]も4通り加算。

S[2] = "aaa"を考える。
1文字目のaは3通り加算。

2文字の"aa"を考える。"aa" + 1 = "ab"でlower_bound("ab")をとる。
S[5] = "ab"が引っかかるので、S[3] ~ S[5]の3通り加算。

3文字の"aaa"を考える。"aaa" + 1 = "aab"でlower_bound("aab")をとる。
S[4] = "aabbb"が引っかかるので、S[3] ~ S[3]の1通り加算。

これをS[A]まで求めると32通り

実装

int main()
{
  cincout();

  ll N;
  cin >> N;
  vector<string> S(N);
  rep(i, N) cin >> S[i];
  sort(all(S));
  ll ans = 0;
  rep(i, N)
  {
    string s;
    for (auto c : S[i]) // 1文字ずつ考える
    {
      s += c + 1; // lower_boundで1文字先を得るために+1する
      auto it = lower_bound(all(S), s); // このit自体は共通接頭辞を含まない
      if (it != S.begin())
      {
        --it; // 1つ下げたものは共通接頭辞を含む
        ll add = it - (S.begin() + i); // 自分自身を除いたものが加算対象
        if (add >= 0)
        {
          ans += add;
        }
        else
          break; // 加算対象がなくなった場合、以降を見ても加算対象ではない。
      }
      s.back()--; // 1文字進めたものを復元
    }
  }
  cout << ans << endl;
}

https://atcoder.jp/contests/abc353/submissions/53354257