Atcoder解いてみた AtCoder Beginner Contest C - C Stands for Center

AtCoder Beginner Contest C - C Stands for Center

問題はこちら

回答

Cを中心とする部分文字列の文字数が奇数なため、Cの左右にはそれぞれ同じ文字数があることがポイント
以下の流れでO(|S|)で解いた
※|S| : 文字列Sの文字数

1. Cのインデックスを保持しておく
2. 各Cに注目し、文字列S内の最初の文字までの距離と、最後の文字までの距離を求める
3. 各Cに対して、文字列S内の最初の文字までの距離と、最後の文字までの距離の小さい方の値を求め、各Cを中心とする部分文字列がいくつあるのか求める

cIdxにわざわざ保存せず、その場で部分文字列数を求めていく方がスマート

#include <iostream>
#include <string>
#include <map>
#include <unordered_map>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <limits.h>
#include <bitset>
#include <list>
#include <set>
#include <numeric>
#include <tuple>

std::string S;


int main()
{
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);

	std::cin >> S;
	std::vector<int> cIdx;

	for (int i = 0; i < S.size(); i++) {
		if (S[i] == 'C') {
			cIdx.push_back(i);
		}
	}

	long long ans = 0LL;
	for (int i = 0; i < cIdx.size(); i++) {
		int center = cIdx[i];
		int left = center - 0;
		int right = (S.size() - 1) - center;
		int range = std::min(left, right);

		ans += static_cast<long long>(range + 1);
	}

	std::cout << ans << std::endl;

	return 0;
}