公開日 :
更新日 :
「(i, j) の組の個数」は、 j を1つ固定して「OKな i が何個あるか」を一発で数え、それを全部の j について足す。
全探索の二重ループの「内側のループ」を、計算1回に置き換えるのが本質。
\(O(N^2)\) → \(O(N)\)。
全探索の二重ループは、すでに「 j を固定して i を数える」形になっている。
for (int j = ...) { // 外側:j を 1 つ選ぶ(=固定)
for (int i = ...) { // 内側:その j に OK な i を 1 個ずつ数える
if (OK(i, j)) ans++;
}
}高速化 = 内側のループが数えている個数を、ループなしで出すこと。
| OK な i の形 | 一発で数える方法 | 例 |
| 範囲になる(◯以上△以下) | 引き算 △ ー ◯ + 1 | ABC485 D、 ABC247 E |
| 「値が◯◯の i 」 | それまでの値の個数を map / 配列に記録 | ABC200 C、 ABC206 C、 ABC233 D |
| 「値が◯◯より小さい i 」 | ソートして二分探索 | ABC077 C |
| 「和が◯◯以下」など | 累積和 + 二分探索、しゃくとり法 | 区間和の条件 |
どちらかを固定するか迷ったら、内側の条件がシンプルになるほう。
左から処理するなら、右側( j )を固定して左側( i )の情報を貯めておく形が多い。
3つ組なら真ん中を固定すると、左右が独立になって掛け算で数えられることが多い(ABC077 C)。
A、B、C だけの文字列 S を S[1…i] / S[i+1…j] / S[j+1…N] に分ける。
3つ全部が ABC を含む(i, j)の個数。
\(N \leq 3\times 10^5\)
(i, j) を選ぶ = 真ん中の区間 [i+1,j] を選ぶ。
両端は自動で決まり、その条件は単純な範囲になる。
| 部分 | 条件 | 求め方 |
| 1つ目 S[1…i] | \(lmin\leq i\) | 前から見て ABC がそろう最初の位置 |
| 3つ目 S[j+1…N] | \(j \leq Jmax\) | 後ろから見て ABC がそろう位置 – 1 |
| 真ん中 S[i+1…j] | \(i \leq g(j)\) | 下で説明 |
→ j ごとに、OK な i は \(lmin \leq i \leq g(j)\) の範囲。
個数 \(g(j)-Imin+1\) を足す。
真ん中の右端を j に決めたとき、真ん中が ABC を全部含むような i の最大値。
例(入力例 1 AABCCABCCBCA、j=8) : lastA=6, lastB=7, lastC=8 → g(8) = 5。 lmin = 4 なので i = 4, 5 の 2 個。
int N;
cin >> N;
string S;
cin >> S;
// 左端スタート位置を決める
int lmin = N + 1;
vector<bool> seenL(3);
int cntL = 0;
for (int i = 1; i <= N; i++) {
int c = S[i-1] - 'A';
if (!seenL[c]) {
seenL[c] = true;
cntL++;
}
if (cntL == 3) {
lmin = i;
break;
}
}
// 右端のゴール位置を決める
int rmax = 0;
vector<bool> seenR(3);
int cntR = 0;
for (int j = N; 1 <= j; j--) {
int c = S[j-1] - 'A';
if (!seenR[c]) {
seenR[c] = true;
cntR++;
}
if (cntR == 3) {
rmax = j-1;
break;
}
}
ll ans = 0;
vector<int> last(3);
for (int k = 1; k <= rmax; k++) {
last[S[k - 1] - 'A'] = k;
int g = min({last[0], last[1], last[2]}) - 1;
if (lmin <= g) {
ans += g - lmin + 1;
}
}
cout << ans << endl;