• 실행 시간 제한: 2초 / 메모리 제한: 1024 MiB
• 배점: 300점

문제

영대문자로 이루어진 문자열 $S$이 주어진다. 이하의 조건을 모두 만족하는 $S$의 부분문자열(연속하는 부분열)이 몇 개 존재하는지 구하시오.

• 홀수개의 문자로 이루어진다.
• 중앙의 문자가 C이다. 엄밀히 말하면, 추출한 부분문자열이 $l$문자로 이루어질 때, $(l+1)/2$번째 문자가 C이다.

제약

• $S$는 영대문자로 이루어진 길이 $1$ 이상 $5\times10^5$ 이하의 문자열

입력

입력은 아래의 형식으로 표준입력을 통해 주어진다.

$S$

출력

답을 출력하라.

입력 예제 1

ABCCA

출력 예제 1

5

이 입력에서 $S=$ABCCA이다. 문제의 조건을 만족하는 부분문자열은 아래의 $5$개이다.

• $S$에서 $1$번째 문자부터 $5$번째 문자까지 추출한 ABCCA
• $S$에서 $2$번째 문자부터 $4$번째 문자까지 추출한 BCC
• $S$에서 $3$번째 문자부터 $3$번째 문자까지 추출한 C
• $S$에서 $3$번째 문자부터 $5$번째 문자까지 추출한 CCA
• $S$에서 $4$번째 문자부터 $4$번째 문자까지 추출한 C

해설

• 문자열 $S$의 $i$번째 문자가 C일 때, 그 C가 중간에 위치하는 부분문자열이 몇 개 존재하는지 생각한다.
  • C의 좌측에는 문자가 $i-1$개, 우측에는 문자가 $|S|-i$개 존재한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		char[] s = br.readLine().toCharArray();
		long cnt = 0;
		for (int i = 0; i < s.length; ++i)
			if (s[i] == 'C')
				cnt += Math.min(i+1, s.length-i);
		System.out.println(cnt);
	}
}