問題一覧 > 通常問題

No.805 UMG

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 421
作問者 : sinsincoscos / テスター : tempura_pp
お気に入りにしたユーザー ProblemId : 2839 / 自分の提出
問題文最終更新日: 2019-03-22 02:27:41
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 209 (順位表) の他の問題:

Problem Statement

There is a string $S$ of length $N$ in which only the three kinds of characters 'U', 'M', and 'G' appear. Let $s_i$ be the $i$-th character from the beginning (1-indexed). Find the number of tuples $(i,j,k)$ satisfying both of the following conditions 1 and 2.
　1. $1\le i\lt j \lt k\le N$ and $j-i=k-j$
　2. $s_i=$'U', $s_j=$'M', $s_k=$'G'

Note

Python users are recommended to submit with PyPy3.

Input

$N$
$S$

$3\le N \le 5000$
$|S|=N$
$S$ is a string consisting of 'U', 'M', and 'G'.

Output

Output the number representing the answer on one line. Print a newline at the end.

Sample

Sample 1
Input
5
UUMGG
Output
2

　$(1,3,5),(2,3,4)$ satisfy the conditions.

Sample 2
Input
4
UUUU
Output
0

　There is no 'M' or 'G' in the first place.

Sample 3
Input
10
UUMMGGGUMG
Output
4

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。