[AGC047] B - First Second
[Q] https://atcoder.jp/contests/agc047/tasks/agc047_b
苦労した。文字反転して、sortして、BIT。156ms。
1. 文字を反転させる。
"dcba" と、"xxxxdxxxxxcba" がペアになることから、ペアの条件は
1) お尻から先頭直前までの並びが等しく、("cba")
2) 先頭文字("d")が、"cba"以前に出現することがペアの条件と考察。
管理しにくいので、反転させる。
問題文を「文字列の終端2文字のうちどちらかを消す」に読み替える。
2. "abcd"とペアになるのは、
1) 先頭"abc"が等しく
2) abc以降のどこかに"d"が出現するような文字列。
"abc" = 必須文字列
"d" = 追加文字
に分けられる。
3. 必須文字列でsortする。
4. 追加文字の下準備
各文字列について。アルファベットa~zが、一番最後に出現するindexをおさえておく。ペア比較するときの「追加文字」の有無をO(1)で判断できる。
5. いもすっぽく数え上げ。
Q.
S0 = dcba
S1 = xxxdxxxcba
1. 反転。
S0 = abcd
S1 = abcxxxdxxx
3. sort。
S0 = abcd
S1 = abcxxxdxxx
4. 下準備。
S0 について、a~z のアルファベットの末端idをおさえておく。
V[0]['a'] = 0
V[0]['b'] = 1
V[0]['c'] = 2
V[0]['d'] = 3
V[0]['e'] = -1
...
V[0]['z'] = -1
S1 について、a~z のアルファベットの末端idをおさえておく。
V[1]['a'] = 0
V[1]['b'] = 1
V[1]['c'] = 2
V[1]['d'] = 3
V[1]['e'] = -1
... // 0123456789
V[1]['x'] = 9 // abcxxxdxxx
... ~
5. いもすっぽく見ていく。
1) S0
・まず生きている いもす の確認。いもす が何もないのでスキップ。
・数え上げ。いもす がないのでans = 0
・次に、S0 と今後ペアになるであろう追加文字を、いもすに入れておく。
S0: abcd
必須文字列: "abc"
追加文字: 'd'
追加index: 3
bits['d'][3] = +1しておく。要求BIT。
これは、S1 以降の文字列について、S0 の条件
必須文字"abc"を満たし、
かつ追加文字'd'が index3 以降に存在するなら、S0 とペアだから+1するいもす。
・stack に、生きている いもす をメモ。
stack<"abc", 'd', 3> // 必須文字列、追加文字、追加index
2) S1
・まず生きている いもす の確認。
stack に入っている必須文字列と、S1 の先頭必須文字列が完全一致してるか確認。
S1 必須文字列: "abcxxxdxx"
S0 stack: "abc"
abcxxxdxx は、abc の先頭一致なのでOK。
もしも、abdxxx と abc なら NG なので、pop()するし、いもす も減らす。
・数え上げ。
S1 は、5種類のアルファベットをもつ。
V[1]['a'] = 0
V[1]['b'] = 1
V[1]['c'] = 2
V[1]['d'] = 3
V[1]['x'] = 9
5種類の追加文字判定を行う。
ans += bits['a'][0]
ans += bits['b'][1]
ans += bits['c'][2]
ans += bits['d'][3] // +1
ans += bits['x'][9]
bits['d'][3] = 1 なので、S0 とペア認定され、ans = 1 になる。
・次に、S1 とペアになるであろう追加文字を、いもすに入れておく。
S1: abcxxxdxxx
必須文字列: "abcxxxdxx"
追加文字: 'x'
追加index: 9
bits['x']の[9] = +1しておく。要求BIT。
これは、S2 以降の文字列について、S1 の条件
必須文字"abcxxxdxx"を満たし、
かつ追加文字'x'が index9 以降に存在するなら、S1 とペアだから+1する いもす。実装
// BIT,index = 1 ~ (0を投げるととまる
// indexを+1して格納する。
// https://atcoder.jp/contests/abc174/submissions/21572028
template<ll BT>
struct Bit
{
ll dat[BT+10]{};
void add(ll i, ll x){
++i;
for(; i<BT; i += i&-i) dat[i] += x;
}
ll sum(ll i){
++i;
ll res = 0;
for(; i>0; i -= i&-i) res += dat[i];
return res;
}
ll rangesum(ll L, ll R){
return sum(R) - sum(L-1);
}
};
--------------------------------------------------------------------
ll N;
vector<tuple<string, char, ll>> V; // 必須文字列、末端文字、末端index
ll pos[200020][26]; // Sにあるアルファベットの末端id
stack<tuple<string, char, ll>> mand; // いもす対象
Bit<1000010> bits[26];
int main() {
cincout();
cin >> N;
rep(i, N) {
string S;
cin >> S;
reverse(all(S));
ll sz = S.size();
string ns = S.substr(0, sz - 1);
V.push_back({ns, S[sz - 1], sz}); // 必須文字、末端の1文字、何番目か
}
sort(all(V));
// 末端id入れ
rep(i, N) rep(j, 26) pos[i][j] = -1;
rep(i, N) {
auto &[S, c, sz] = V[i];
// 末端文字だけ
chmax(pos[i][c - 'a'], sz - 1);
// 必須文字
for (ll j = sz - 2; j >= 0; --j) {
chmax(pos[i][S[j] - 'a'], j);
}
}
// いもす。必須はstack
ll ans = 0;
rep(i, N) {
auto &[S, c, sz] = V[i];
// 今の必須が、stackの必須を満たさないなら除外
while (!mand.empty()) {
auto &[pre, prec, presz] = mand.top();
// strncmp
bool cmp_ok = true;
rep(k, presz-1) {
if (pre[k] != S[k]) {
cmp_ok = false;
break;
}
}
if (cmp_ok == true)
break;
else {
bits[prec - 'a'].add(presz-1, -1);
mand.pop();
}
}
// 今のSがこれまでの、いもすを満たす？
rep(j, 26) {
if (pos[i][j] == -1) continue; // ない
ans += bits[j].sum(pos[i][j]);
}
// Sの末端idを、ほしいリストに追加
bits[c - 'a'].add(sz - 1, 1);
mand.push({S, c, sz});
}
cout << ans << endl;
}https://atcoder.jp/contests/agc047/submissions/28656328