084.md

084 - There are two types of characters (★3)

解答

#include <iostream>
#include <vector>

// 1 ～ n の合計を計算
long long SumFrom1To(long long n)
{
	return (n * (n + 1) / 2);
}

int main()
{
	// 長さ N の文字列
	int N;
	std::cin >> N;

	// グループリスト
	//
	// S = "oooooxxxxooo" の場合,
	// groups = { 5, 4, 3 }
	// 
	// S = "ooxo" の場合,
	// groups = { 2, 1, 1 }
	//
	std::vector<int> groups;
	{
		char previous;

		// 最初の文字
		std::cin >> previous;

		// 現在のグループの文字数（1 個からスタート）
		int count = 1;

		for (int i = 1; i < N; ++i)
		{
			char ch;
			std::cin >> ch;

			if (ch != previous) // グループが終了した
			{
				// 直前までの文字数を追加
				groups.push_back(count);

				// 新しいグループの文字
				previous = ch;

				// 1 個からスタート
				count = 1;
			}
			else // 現在のグループと同じ文字
			{
				// 現在のグループの文字数を増やす
				++count;
			}
		}

		if (count)
		{
			groups.push_back(count);
		}
	}

	// 区間の選び方（条件を満たさないものも含む）のパターン数
	long long a = SumFrom1To(N);

	// 各グループについて
	for (const auto& group : groups)
	{
		// 現在のグループで完結するような区間のパターン数を引く
		a -= SumFrom1To(group);
	}

	// 解答を出力
	std::cout << a << '\n';
}