公開日 :
更新日 :

一方を固定して数える

「(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 の形一発で数える方法例
範囲になる(◯以上△以下)引き算 △ ー ◯ + 1ABC485 D、 ABC247 E
「値が◯◯の i 」それまでの値の個数を map / 配列に記録ABC200 C、 ABC206 C、
ABC233 D
「値が◯◯より小さい i 」ソートして二分探索ABC077 C
「和が◯◯以下」など累積和 + 二分探索、しゃくとり法区間和の条件

どちらかを固定するか迷ったら、内側の条件がシンプルになるほう。
左から処理するなら、右側( j )を固定して左側( i )の情報を貯めておく形が多い。
3つ組なら真ん中を固定すると、左右が独立になって掛け算で数えられることが多い(ABC077 C)。

例1 : 3つに分けてそれぞれ ABC を全部含む

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\) を足す。

g(j) とは

真ん中の右端を j に決めたとき、真ん中が ABC を全部含むような i の最大値。

  • i を小さくするほど真ん中が左に伸びて文字が増える → 一度 OK になったら、それより小さい i はずっと OK (単調性)
  • 位置 j までで A、B、C が最後に出た位置を lastA、lastB、lastC とすると、真ん中の左端 + 1は 3 つの最小値以下でないといけない
    \(i + 1 \leq min(lastA, lastB, lastC)\) → \(g(j) = min(lastA, lastB, lastC)-1\)

例(入力例 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;
  • \(i < j\) は自動で満たされる : \(g(j) \leq j-1\) なので。

練習問題