Official

D - ABC|ABC|ABC Editorial by cn449 Editorial for printing


尺取り法による解法と動的計画法による解法の 2 つの解法を解説します。

尺取り法による解法

\(S_1S_2\ldots S_L\) が A, B, C をすべて含むような最小の \(L\) および \(S_{R+1}S_{R+2}\ldots S_N\) が A, B, C をすべて含むような最大の \(R\) を取ります。ただし、そのような \(L, R\) が存在しない場合は答えは \(0\) です。

すると、\(S_1S_2\ldots S_i, S_{j+1}S_{j+2}\ldots S_N\) が A, B, C を含むことは \(L \leq i, j \leq R\) と同値です。

したがって、\(L \leq i, j \leq R\) なる整数組 \((i, j)\) であって \(S_{i + 1}S_{i + 2}\ldots S_j\) が A, B, C をすべて含むようなものの個数が答えとなります。

ここで、\(L \leq l \leq R\) なる整数 \(l\) に対して \(S_{l + 1}S_{l + 2}\ldots S_r\) が A, B, C をすべて含むような \(r \leq R\) なる最小の \(r\)(存在しなければ \(R + 1\))を \(f(l)\) とおくと、\(i = l\) のとき条件を満たす整数 \(j\) は \(f(l) \leq j \leq R\) であるようなものなので、\(R - f(l) + 1\) 個あります。

さらに、単調性 \(f(l) \leq f(l + 1)\) から尺取り法の要領で答えを求めることができるので、全体として \(O(N)\) 時間で答えが求められます。

動的計画法による解法

\(dp_{i, j, k}\) を先頭 \(i\) 文字を処理し、これまでの区切りの個数が \(j\) 個、現在処理している \(j + 1\) 個目の部分文字列の状態が \(k\) であるような方法の個数とします。

ここで、「部分文字列の状態」として管理するべきは A, B, C の各文字についてその文字がすでに部分文字列に含まれているかであり、\(2^3 = 8\) 通りの状態で表すことができます。

dp の各遷移では、まだ処理していない文字の中で最も先頭にある文字を現在見ている部分文字列に追加し、A, B, C がすでに部分文字列に含まれているときに限り区切りを入れる遷移を計算すればよいです。

dp の状態数は \(O(N)\) であり、時間計算量も \(O(N)\) となります。

実装例

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;

int main() {
	int n;
	cin >> n;
	string s;
	cin >> s;
	int x = 0, L = -1, R = -1;
	rep(i, n) {
		if (s[i] == 'A') x |= 1;
		else if (s[i] == 'B') x |= 2;
		else x |= 4;
		if (x == 7) {
			L = i + 1;
			break;
		}
	}
	x = 0;
	for (int i = n - 1; i >= 0; i--) {
		if (s[i] == 'A') x |= 1;
		else if (s[i] == 'B') x |= 2;
		else x |= 4;
		if (x == 7) {
			R = i;
			break;
		}
	}
	vector<int> c(3);
	ll ans = 0;
	int r = L;
	for (int l = L; l < R; l++) {
		while (r < R && (*min_element(c.begin(), c.end())) == 0) {
			c[s[r] - 'A']++;
			r++;
		}
		if (*min_element(c.begin(), c.end()) > 0) ans += R + 1 - r;
		c[s[l] - 'A']--;
	}
	cout << ans << '\n';
}
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;

int main() {
	int n;
	cin >> n;
	string s;
	cin >> s;
	vector dp(3, vector<ll>(8));
	dp[0][0] = 1;
	for (auto c : s) {
		vector ep(3, vector<ll>(8));
		rep(i, 3) {
			rep(j, 8) {
				int k = j;
				if (c == 'A') k |= 1;
				else if (c == 'B') k |= 2;
				else k |= 4;
				ep[i][k] += dp[i][j];
				if (i <= 1 && k == 7) ep[i + 1][0] += dp[i][j];
			}
		}
		dp = move(ep);
	}
	cout << dp[2][7] << '\n';
}

posted:
last update: