C - Election
Source: atcoder
Difficulty: 600

Problem Statement
This year's AtCoder mayoral election has two candidates, A and B, and
N
voters have cast their votes. The voters are assigned numbers from
1
to
N
, and voter
i
(1 \leq i \leq N)
voted for candidate
c_i
.
Now, the votes will be counted. As each vote is counted, the provisional result will be announced as one of the following three outcomes:
Result A:
Currently, candidate A has more votes.
Result B:
Currently, candidate B has more votes.
Result C:
Currently, candidates A and B have the same number of votes.
There is a rule regarding the order of vote counting: votes from all voters except voter
1
must be counted in ascending order of their voter numbers. (The vote from voter
1
may be counted at any time.)
How many different sequences of provisional results could be announced?
What is a sequence of provisional results?
Let
s_i
be the result (
A
,
B
, or
C
) reported when the
i
-th vote
(1 \leq i \leq N)
is counted. The sequence of provisional results refers to the string
s_1 s_2 \dots s_N
.
Constraints
N
is an integer such that
2 \leq N \leq 1000000
.
Each of
c_1, c_2, \dots, c_N
is
A
or
B
.
Input
The input is given from Standard Input in the following format:
N
c_1 c_2 \cdots c_N
Output
Print the answer.
Sample Input 1
4
AABB
Sample Output 1
3
In this sample input, there are four possible orders in which the votes may be counted:
The votes are counted in the order of voter
1 \to 2 \to 3 \to 4
.
The votes are counted in the order of voter
2 \to 1 \to 3 \to 4
.
The votes are counted in the order of voter
2 \to 3 \to 1 \to 4
.
The votes are counted in the order of voter
2 \to 3 \to 4 \to 1
.
The sequences of preliminary results for these will be
AAAC
,
AAAC
,
ACAC
,
ACBC
from top to bottom, so there are three possible sequences of preliminary results.
Sample Input 2
4
AAAA
Sample Output 2
1
No matter the order of counting, the sequence of preliminary results will be
AAAA
.
Sample Input 3
10
BBBAAABBAA
Sample Output 3
5
Sample Input 4
172
AABAAAAAABBABAABBBBAABBAAABBABBABABABBAAABAAABAABAABBBBABBBABBABBBBBBBBAAABAAABAAABABBBAABAAAABABBABBABBBBBABAABAABBBABABBAAAABAABABBBABAAAABBBBABBBABBBABAABBBAAAABAAABAAAB
Sample Output 4
24

C++ solution:
// #pragma GCC optimize ("O3,unroll-loops")
// #include <bits/allocator.h>
// #pragma GCC target("avx,avx2,fma,sse4.2,bmi2,popcnt,lzcnt")

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>



using namespace std;
namespace atcoder {}; using namespace atcoder;
namespace __gnu_pbds {}; using namespace __gnu_pbds;

#if defined(LOCAL) && !defined(ONLINE_JUDGE)
#include "local/debug.h"
#include "local/stacktrace.h"
#else
#define dbg(...)
#define dbgArr(...)
#define trace(...)
#endif

void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); }

using sgd = signed;
using llong = long long;
__extension__ typedef __int128 int128;

istream& operator>>(istream& _in, int128& _i128) {
    long long _i64; _in >> _i64; _i128 = (int128) _i64; return _in;
}
ostream& operator<<(ostream& _out, const int128& _i128) {
    _out << (long long) _i128; return _out;
}

template <typename _T>
istream& operator>>(istream& _in, vector<_T>& _data) {
    for (auto& _x : _data) { _in >> _x; } return _in;
}
template <typename _T>
ostream& operator<<(ostream& _out, const vector<_T>& _data) {
    for (const _T& _x : _data) { _out << _x << ' '; } return _out;
}

istringstream _getline() {
    string _line; cin >> ws; getline(cin, _line);
    if (!cin) { cerr << "NOTHING TO READ" << endl; abort(); }
    return istringstream(_line);
}
template <typename... _Ts>
void _rt(_Ts&... _vars) {
    size_t _cnt = 0; constexpr size_t _expected = sizeof...(_vars);
    istringstream _iss = _getline();

    ((_iss >> _vars ? ++_cnt : _cnt), ...);
    size_t _dmp; while (_iss >> _dmp) ++_cnt;

    if (_cnt != _expected) {
        cerr << "READING INPUT: ";
        cerr << "EXPECTED " << _expected << " BUT GOT " << _cnt << endl;
        abort();
    }
}
template <typename _T>
void _ra(vector<_T>& _vec) {
    istringstream _iss = _getline();
    for (_T x; _iss >> x; ) _vec.push_back(x);
}
void _rs(string& _str) { cin >> _str; }

template <typename _T>
using max_queue = priority_queue<_T>;
template <typename _T>
using min_queue = priority_queue<_T, vector<_T>, greater<_T>>;
#pragma GCC poison priority_queue

#ifdef PB_DS_ASSOC_CNTNR_HPP
template <typename _T> using indexed_set =
tree<_T, null_type, less<_T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename _K, typename _V> using indexed_map =
tree<_K, _V, less<_K>, rb_tree_tag, tree_order_statistics_node_update>;
#endif

constexpr char nl = '\n';

using vs = vector<string>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvvb = vector<vvb>;
using vvvvb = vector<vvvb>;

#define all(_x) (_x).begin(), (_x).end()
#define rall(_x) (_x).rbegin(), (_x).rend()

#define make_unique(_x) \
sort(all(_x)), _x.erase(unique(all(_x)), _x.end()), _x.shrink_to_fit()

// ============================================================================

#define int long long

// ============================================================================

#define rep2(_i, _r) for (int _i = 0; _i < (int) (_r); _i++)
#define rep3(_i, _l, _r) for (int _i = (_l); _i < (int) (_r); _i++)
#define repR2(_i, _r) for (int _i = (_r) - 1; _i >= (int) 0; _i--)
#define repR3(_i, _l, _r) for (int _i = (_r) - 1; _i >= (int) (_l); _i--)
#define overload3(_a, _b, _c, _d, ...) _d
#define rep(...) overload3(__VA_ARGS__, rep3, rep2)(__VA_ARGS__)
#define repR(...) overload3(__VA_ARGS__, repR3, repR2)(__VA_ARGS__)

#define sz(_x) ((int) ((_x).size()))

#define ri(...) int __VA_ARGS__; _rt(__VA_ARGS__)
#define ra(_x) vector<int> _x; _ra<int>(_x);
#define rs(_x) string _x; _rs(_x);

constexpr int inf = numeric_limits<int>::max() / 2;

using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vvvvi = vector<vvvi>;

using pr = pair<int, int>;
using tup = tuple<int, int, int>;

// ============================================================================

template <typename _T> int sgn(_T val) {
    return (_T(0) < val) - (val < _T(0));
}

// ============================================================================

int32_t main() {
    fast_io(); trace(__FILE_NAME__);


    ri(n);
    rs(s)

    int ans = 1;
    int a = 0, b = 0;

    rep (i, n - 1) {
        int ainit = a + (s.front() == 'A');
        int binit = b + (s.front() == 'B');
        int sinit = sgn(ainit - binit);

        a += s[i+1] == 'A';
        b += s[i+1] == 'B';

        if (sinit != sgn(a - b)) ans++;
    }

    cout << ans << nl;

}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var (
	sc = bufio.NewScanner(os.Stdin)
	wt = bufio.NewWriter(os.Stdout)
)

const (
	inf = 1 << 60
	MOD = 998244353
)

func main() {
	/*** INIT ***/
	defer wt.Flush()
	sc.Buffer([]byte{}, inf)
	sc.Split(bufio.ScanWords)

	n := InputInt()
	c := InputString()

	s := make([]int, n+1)
	for i := 1; i <= n; i++ {
		if c[i-1] == 'A' {
			s[i] = s[i-1] + 1
		} else {
			s[i] = s[i-1] - 1
		}
	}

	ans := 0
	for i := 1; i < n; i++ {
		before, after := s[i], s[i]
		if c[0] == 'A' {
			if c[i] == 'B' {
				after -= 2
			}
		} else {
			if c[i] == 'A' {
				after += 2
			}
		}
		if Sign(before) != Sign(after) {
			ans++
		}
	}
	OutInt(ans + 1)

}

func Sign(x int) int {
	if x == 0 {
		return 0
	} else if x < 0 {
		return -1
	} else {
		return 1
	}
}

/*** I/O ***/
func InputInt() int {
	sc.Scan()
	val, _ := strconv.Atoi(sc.Text())
	return val
}

func InputString() string {
	sc.Scan()
	return sc.Text()
}

func OutInt(val int) {
	fmt.Fprintln(wt, val)
}

func OutString(s string) {
	fmt.Fprintln(wt, s)
}

Java solution:
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

public class Main {
	static InputStream is;
	static PrintWriter out;
	static String INPUT = "";
	
	static void solve()
	{
		int n = ni();
		char[] s = ns(n);
		int[] h = new int[n];
		for(int i = 1;i < n;i++){
			h[i] = h[i-1] + (s[i] == 'A' ? 1 : -1);
		}

		// ...O.X....
		// .X........
		// O!=Xで、rem+Oとrem+Xのsgnが違うときのみ

		int ret = 1;
		for(int i = 1;i < n;i++){
			int af = h[i];
			int be = h[i-1] + (s[0] == 'A' ? 1 : -1);
			if(Integer.signum(af) != Integer.signum(be)){
				ret++;
			}
		}
		out.println(ret);
	}
	
	public static void main(String[] args) throws Exception
	{
		long S = System.currentTimeMillis();
		is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);
		
		solve();
		out.flush();
		long G = System.currentTimeMillis();

	}
	
	private static boolean eof()
	{
		if(lenbuf == -1)return true;
		int lptr = ptrbuf;
		while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false;
		
		try {
			is.mark(1000);
			while(true){
				int b = is.read();
				if(b == -1){
					is.reset();
					return true;
				}else if(!isSpaceChar(b)){
					is.reset();
					return false;
				}
			}
		} catch (IOException e) {
			return true;
		}
	}
	
	private static byte[] inbuf = new byte[1024];
	static int lenbuf = 0, ptrbuf = 0;
	
	private static int readByte()
	{
		if(lenbuf == -1)throw new InputMismatchException();
		if(ptrbuf >= lenbuf){
			ptrbuf = 0;
			try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
			if(lenbuf <= 0)return -1;
		}
		return inbuf[ptrbuf++];
	}
	
	private static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
//	private static boolean isSpaceChar(int c) { return !(c >= 32 && c <= 126); }
	private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
	
	private static double nd() { return Double.parseDouble(ns()); }
	private static char nc() { return (char)skip(); }
	
	private static String ns()
	{
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while(!(isSpaceChar(b))){
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	
	private static char[] ns(int n)
	{
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while(p < n && !(isSpaceChar(b))){
			buf[p++] = (char)b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}
	
	private static char[][] nm(int n, int m)
	{
		char[][] map = new char[n][];
		for(int i = 0;i < n;i++)map[i] = ns(m);
		return map;
	}

	private static int[][] nmi(int n, int m)
	{
		int[][] map = new int[n][];
		for(int i = 0;i < n;i++)map[i] = na(m);
		return map;
	}

	private static int[] na(int n)
	{
		int[] a = new int[n];
		for(int i = 0;i < n;i++)a[i] = ni();
		return a;
	}

	private static long[] nal(int n)
	{
		long[] a = new long[n];
		for(int i = 0;i < n;i++)a[i] = nl();
		return a;
	}

	private static int ni()
	{
		int num = 0, b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private static long nl()
	{
		long num = 0;
		int b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}

JavaScript solution:
let lines = require("fs").readFileSync("/dev/stdin","utf8").trim().split("\n");
let N = Number(lines[0]);
let c = lines[1].split("");
let d = [0];
for(let i=0;i<N;i++){
  if(c[i]=="A")d.push(d[i]+1);
  else d.push(d[i]-1);
}
let ans = 0;
for(let t=1;t<=N;t++){
  let before = d[t];
  let after = d[t];
  if(c[0]=="A"&&c[t]=="B")after -=2;
  else if(c[0]=="B"&&c[t]=="A")after +=2;
  if(after>0)after = 1;
  else if(after<0)after = -1;
  if(before>0)before = 1;
  else if(before<0)before = -1;
  if(before!=after)ans+=1;
}
console.log(ans+1);

Python solution:
n = int(input())
C = input()
X = [0] * n
for i in range(1, n):
    if C[i] == C[0]:
        X[i] = X[i - 1] + 1
    else:
        X[i] = X[i - 1] - 1

# ABB
#

ans = 1
for i in range(1, n):
    if X[i] > 0:
        continue
    if X[i] == 0 and X[i - 1] < 0:
        continue
    if X[i] < 0 and X[i - 1] < -1:
        continue
    ans += 1

print(ans)

Ruby solution:
# debug = true
debug = false
# 整数1つを受け取る(1行に1つ整数がある前提)
N = gets.to_i
C_BYTES = gets.chomp.bytes
A_BYTE, B_BYTE = 'AB'.bytes
s = [0]
C_BYTES.each do |c_byte|
  s << ((c_byte == A_BYTE) ? (s[-1] + 1) : (s[-1] - 1))
end
p s if debug
timing_change = 0
# i票目を開票。一人目未開票の場合cで言うとi + 1人目の票を開票しているので注意
N.times do |i|
  # 今回の開票者と一人目が同じ候補に投票していた場合文字列は変わらない
  next if C_BYTES[0] == C_BYTES[i + 1]

  before = s[i + 1] # 1の開票順 が t以下 のときの得票数の差
  # 得票数の差が大きすぎる場合は一人目を開票しようがしまいが文字列は変わらない
  next if before.abs >= 3

  after  = before # 1が未開票
  #  after += 0 if C_BYTES[0] == A_BYTE and C_BYTES[i+1] == A_BYTE
  after -= 2 if C_BYTES[0] == A_BYTE && C_BYTES[i + 1] == B_BYTE
  after += 2 if C_BYTES[0] == B_BYTE && C_BYTES[i + 1] == A_BYTE
  # after += 0 if C_BYTES[0] == B_BYTE and C_BYTES[i+1] == B_BYTE
  next if (before <=> 0) == (after <=> 0)

  p [i + 1, C_BYTES[i + 1], before, after] if debug
  timing_change += 1
end
puts timing_change + 1