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