ステップ 1

まずは具体例として、\(8\) 人の投票者がおり、それぞれ候補者 A、A、B、A、B、B、B、B に投票する場合を考えてみましょう。このとき、開票結果の列としては何通りがあるのでしょうか。

• 投票者 \(1\) が \(1\) 番目に開票: 投票順は [A]ABABBBB なので開票結果の列は AAAAACBB
• 投票者 \(1\) が \(2\) 番目に開票: 投票順は A[A]BABBBB なので開票結果の列は AAAAACBB
• 投票者 \(1\) が \(3\) 番目に開票: 投票順は AB[A]ABBBB なので開票結果の列は ACAAACBB
• 投票者 \(1\) が \(4\) 番目に開票: 投票順は ABA[A]BBBB なので開票結果の列は ACAAACBB
• 投票者 \(1\) が \(5\) 番目に開票: 投票順は ABAB[A]BBB なので開票結果の列は ACACACBB
• 投票者 \(1\) が \(6\) 番目に開票: 投票順は ABABB[A]BB なので開票結果の列は ACACBCBB
• 投票者 \(1\) が \(7\) 番目に開票: 投票順は ABABBB[A]B なので開票結果の列は ACACBBBB
• 投票者 \(1\) が \(8\) 番目に開票: 投票順は ABABBBB[A] なので開票結果の列は ACACBBBB

となるため、開票結果の列のパターン数は \(5\) 通りになります。しかし、開票結果の列の変化に着目すると、もう少し簡単に解くことができます。

---

まずは開票結果の列をよく観察すると、投票者 \(1\) が開票する順番を \(i\) 番目とするとき、

• \(1\) 文字目: 全部 A
• \(2\) 文字目: \(i \leq 2\) のとき A、\(i > 2\) のとき C
• \(3\) 文字目: 全部 A
• \(4\) 文字目: \(i \leq 4\) のとき A、\(i > 4\) のとき C
• \(5\) 文字目: \(i \leq 5\) のとき A、\(i > 5\) のとき B
• \(6\) 文字目: \(i \leq 6\) のとき C、\(i > 6\) のとき B
• \(7\) 文字目: 全部 B
• \(8\) 文字目: 全部 B

となります。ここで「文字が変わるタイミング」は \(i = 2, 4, 5, 6\) の直後の \(4\) 回なので、開票結果の列が \(4 + 1 = 5\) 通りあるとわかります (注: 同じ場所の文字が \(3\) 回以上変わっていないことに注意してください)。でも、文字が変わるタイミングはどうやって求めるのでしょうか。

---

投票者 \(1\) が最初に投票した場合、A 候補と B 候補の得票数の差は \(+1 \to +2 \to +1 \to +2 \to +1 \to 0 \to -1 \to -2\) と推移します。したがって、投票者 \(1\) の開票順が変わったときの各段階での得票数の差は、次のように推移します。

• \(1\) 票目までの段階:
  • \(i \leq 1\) のとき、\(1\) 票目段階では投票者 \(1\) の票が入る
  • \(i > 1\) のとき、\(1\) 票目段階では投票者 \(2\) の票が入る
  • つまり \(i = 1\) の前後で投票者 \(1\) が消え、投票者 \(2\) が追加される
  • 投票者 \(1, 2\) が A, A に投票するので、得票数の差は常に \(+1\)
• \(2\) 票目までの段階:
  • \(i \leq 2\) のとき、\(2\) 票目段階では投票者 \(1, 2\) の票が入る
  • \(i > 2\) のとき、\(2\) 票目段階では投票者 \(2, 3\) の票が入る
  • つまり \(i = 2\) の前後で投票者 \(1\) が消え、投票者 \(3\) が追加される
  • 投票者 \(1, 3\) が A, B に投票するので、得票数の差は \(i \leq 2\) ならば \(+2\)、\(i > 2\) ならば \(+0\)
• \(4\) 票目までの段階:
  • \(i \leq 4\) のとき、\(4\) 票目段階では投票者 \(1, 2, 3, 4\) の票が入る
  • \(i > 4\) のとき、\(4\) 票目段階では投票者 \(2, 3, 4, 5\) の票が入る
  • つまり \(i = 4\) の前後で投票者 \(1\) が消え、投票者 \(5\) が追加される
  • 投票者 \(1, 5\) が A, B に投票するので、得票数の差は \(i \leq 4\) ならば \(+2\)、\(i > 4\) ならば \(+0\)
• その他の段階の場合も同様

このように考えていくと、各段階での得票数の差がどう変化するのかが計算量 \(O(N)\) でわかります。また、開票結果は得票数の差が正のとき A、負のとき B、ゼロのとき C となるため、文字が変わるタイミングも計算量 \(O(N)\) でわかります。

---

ステップ 2

それでは、ここまでの内容を一般化してみましょう。投票者 \(1\) から投票者 \(k\) までにおける A 候補と B 候補への投票数の差を \(S_k\) とします。このとき、\(t\) 票目の段階での得票数の差は、投票者 \(1\) の開票順 \(i\) が変わったとき次のように変化します。

• 投票者 \(1, t+1\) が A, A に投票する場合: 常に \(S_t\)
• 投票者 \(1, t+1\) が A, B に投票する場合: \(i \leq t\) のとき \(S_t\)、\(i > t\) のとき \(S_t - 2\)
• 投票者 \(1, t+1\) が B, A に投票する場合: \(i \leq t\) のとき \(S_t\)、\(i > t\) のとき \(S_t + 2\)
• 投票者 \(1, t+1\) が B, B に投票する場合: 常に \(S_t\)

そこで、開票結果は得票数の差が正のとき A、負のとき B、ゼロのとき C となるため、次のようなプログラムを書けば計算量 \(O(N)\) で答えを出すことができます。

---

実装例 (C++)

#include <iostream>
using namespace std;

int N;
int S[1000009];
char C[1000009];

// 正であれば A, 負であれば B, ゼロであれば C を返す関数
char GetSign(int x) {
	if (x > 0) return 'A';
	if (x < 0) return 'B';
	return 'C';
}

int main() {
	// Step 1. 入力
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> C[i];
	}

	// Step 2. S[i] を計算する
	S[0] = 0;
	for (int i = 1; i <= N; i++) {
		if (C[i] == 'A') S[i] = S[i - 1] + 1;
		if (C[i] == 'B') S[i] = S[i - 1] - 1;
	}

	// Step 3. 変わるタイミングが何回あるかを計算
	int TimingChange = 0;
	for (int t = 1; t <= N - 1; t++) {
		int before = S[t]; // i <= t のときの得票数の差
		int after = S[t];  // i >  t のときの得票数の差
		if (C[1] == 'A' && C[t + 1] == 'A') after += 0;
		if (C[1] == 'A' && C[t + 1] == 'B') after -= 2;
		if (C[1] == 'B' && C[t + 1] == 'A') after += 2;
		if (C[1] == 'B' && C[t + 1] == 'B') after += 0;

		// 得票数の差を文字に変換する
		char sign_before = GetSign(before);
		char sign_after  = GetSign(after);

		// 文字が変わるのであれば、TimingChange に 1 を加算
		if (sign_before != sign_after) {
			TimingChange += 1;
		}
	}

	// Step 4. 出力
	cout << TimingChange + 1 << endl;
	return 0;
}

実装例 (Python)

# 正であれば A, 負であれば B, ゼロであれば C を返す関数
def GetSign(x):
    if x > 0:
        return 'A'
    if x < 0:
        return 'B'
    return 'C'

# Step 1. 入力
N = int(input())
C = input()

# Step 2. S[i] を計算する
S = [0] * (N + 1)
for i in range(N):
    if C[i] == 'A': S[i + 1] = S[i] + 1
    if C[i] == 'B': S[i + 1] = S[i] - 1

# Step 3. 変わるタイミングが何回あるかを計算
TimingChange = 0
for t in range(1, N):
    before = S[t] # i <= t のときの得票数の差
    after  = S[t] # i >  t のときの得票数の差
    if C[0] == 'A' and C[t] == 'A': after += 0
    if C[0] == 'A' and C[t] == 'B': after -= 2
    if C[0] == 'B' and C[t] == 'A': after += 2
    if C[0] == 'B' and C[t] == 'B': after += 0

    # 得票数の差を文字に変換する
    sign_before = GetSign(before)
    sign_after  = GetSign(after)

    # 文字が変わるのであれば、TimingChange に 1 を加算
    if sign_before != sign_after:
        TimingChange += 1

# Step 4. 出力
print(TimingChange + 1)