明らかにtoo muchな解法ですが、考え方としては悪くないのでこれを記します。
題意
- a,b,c からなる n文字の文字列があります。
- 次の条件を満たす"2文字以上の"最短の連続区間の長さを答えてください。存在しない場合は-1を答えます。
- その区間のaの数は、その区間のb および cの数と厳密に大きい
例 および 一般的な答え O(N)
実は、以下の文字列が存在するかを答えればよいです。
- 2文字
aa - 3文字
abaaca - 4文字
abcaacba - 5文字
abacaacaba - 7文字
abbaccaaccabba
自分の考え方 O(NlogN)
まず、題意からして、始点終点がaである文字列が最短の区間だとします。なぜなら、始点終点がaでない文字列が答えだとするなら、両端のb, cを削った文字列も必ず条件を満たしそれが答えになります。
以下のような図を描き、じっと睨みます。
CountA,B,Cは最初からそこまでに出現した文字の数。a-bなどはそれぞれ、aからb,cを引いた文字です。すると、成立する区間とは、ある始点を決めてa-b, a-cを得たとき、次の文字以降で両者がそれ以上になるとき、に条件を満たします。
- 例えば: index[0,3]の区間は
1,1からスタートし、index3の1,1の区間で条件を満たします。index12,14,20,21,22も条件を満たしますが、index3までが最短の区間です。 - 例えば: index[14,20]の区間は
1,2からスタートし、index20の区間で条件を満たします。
あらかじめ、累積和を取っておくことで、ある始点と終点を決めたときに条件を満たすかは上記のようにa,b,cの数をカウントしておくことでO(1)で可能です。そこで、すべての文字の"a"の区間を探索すれば答えが出そうですが、それでは$O(N^2)$になってしまいます。
二分探索が使えないかを考えてみます。まず、存在の可能性は線形に変化しません。例えば、
[a]bababba[a]{a}{a}bbbbbabbbaaa{a}{a}...
という文字で、最初の[a]から成立する区間を求めたい場合、次の[a]の区間を求めたいですが、他に{a}の区間でも成立します。が、括弧のないaでは成立しません。つまり、成立する区間が離れているため、二分探索ができません。
そこで、SparseTableを用いることにします。これは、事前計算$O(NlogN)$でmaxやminのクエリを$O(N)$でできるデータ構造です。持たせるテーブルは、a-bとa-cで、maxをとります。
これにより、二分探索を用いたクエリが可能になります。あるaを始点として、そのあとに答えがあるかを確認したいとします。そのa+1の位置から、二分探索で今のa-bとa-c以上の値となる区間を探します。もし、クエリでこの条件を満たす場合、区間のmaxを取っているため、その位置、あるいは、それよりも短い場所で条件を満たす可能性があります。
さて、条件を満たす可能性があるといったのには理由があります。次の場合を考えます。
今、index0にいたとして、(index1から)index8までのクエリをするとa-bはindex1で, a-cはindex5,6でmaxとなる1です。ところが、この区間において、初期位置のa-bとa-c以上の値を同時に満たしている区間はありません。このため、区間のMaxはあくまで可能性があるは分かるものの、あるとは言えません。
しかしながら、これでO(NlogN)で答えを得ることができました。
実装
void solve(){
// O(NlogN * k) : kは出現しうる文字の種類。今回は2固定。
int n; cin >> n;
string s; cin >> s;
vector<int> diffb(n), diffc(n), posa;
int numa = 0, numb=0, numc=0;
REP(i, s.size()){
if(s.at(i) == 'a') {
++numa;
posa.emplace_back(i); // トリガとなる位置は覚えておく
}
else if(s.at(i) == 'b') ++numb;
else if(s.at(i) == 'c') ++numc;
diffb.at(i) = numa - numb; // ここまでに出現した a - b を配列に入れる
diffc.at(i) = numa - numc;
}
// SparseTableで、ある区間[l, r)に対する"a -b"などの maxをクエリできるようにする
auto op = [] (int a, int b) {return max(a,b);};
SparseTable<int> stb(diffb, op);
SparseTable<int> stc(diffc, op);
int ans = 1e9;
// 全てのlを始点として
REP(l, posa.size()) {
int mid;
int ng = l;
int ok = posa.size(); // そのあとの全てのaに対して
while (abs(ok - ng) > 1) {
mid = (ok + ng) / 2;
// 少なくとも、選んだmidまでの間に答えの候補があることが考えられて
// lからmidの間に、lの瞬間のb,cの差分以上のaのポイントがあるなら希望をもって二分探索したい
if (stb.query(posa.at(l)+1, posa.at(mid) + 1) >= ( diffb.at(posa.at(l)) ) &&
stc.query(posa.at(l)+1, posa.at(mid) + 1) >= ( diffc.at(posa.at(l)) ) ){
ok = mid;
// mid自身がこれを満たす場合は答えとする
if(diffb.at(posa.at(mid)) >= diffb.at(posa.at(l))&&
diffc.at(posa.at(mid)) >= diffc.at(posa.at(l))){
ans = min(ans, posa[mid] - posa[l] + 1);
}
}
else ng = mid;
}
}
if(ans == 1e9) ans = -1;
cout << ans << "\n";
}