No.805 UMG

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 282
作問者 : sinsincoscossinsincoscos / テスター : tempura_pptempura_pp
6 ProblemId : 2839 / 出題時の順位表
問題文最終更新日: 2019-03-22 02:27:41

問題文

長さ$N$の'U','M','G'の3種類の文字のみが現れる文字列$S$があります。先頭から$i$番目の文字を$s_i$とします(1-indexedです)。次の1,2の条件を満たす$(i,j,k)$ の組の数を求めてください。
 1. $1\le i\lt j \lt k\le N$かつ$j-i=k-j$
 2. $s_i=$'U',$s_j=$'M',$s_k=$'G'

注意

Python使いの人はPyPy3で提出することを推奨します。

入力

$N$
$S$

$3\le N \le 5000$
$|S|=N$
$S$は'U','M','G'からなる文字列である。

出力

答えを表す数値を1行に出力してください。最後に改行してください。

サンプル

サンプル1
入力
5
UUMGG
出力
2

 $(1,3,5),(2,3,4)$が条件を満たします。

サンプル2
入力
4
UUUU
出力
0

 そもそも'M'や'G'がありません。

サンプル3
入力
10
UUMMGGGUMG
出力
4

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