ABC 401-500/ABC458C - C Stands for Center - 競技プログラミング用 知識集積所

---

問題

ABC458C

必要知識

B以下レベルの内容は省略

• 特になし

考え方

開始位置と終了位置の組で全探索をすると、O(N^2)必要なのでTLEする。
ある程度うまくまとめながら数えていくことが必要。

ということで、同じCが中央にくるものごとに数える。
あるCに注目したとき、そこより前にx文字、そこより後ろにy文字あったとする。
この場合、そのCが中央に来る文字列はmin(x,y)+1個ある。

ということで、前から順にCの文字を探し、見つけるたびにそこを中央にする文字列数を足していけばよい。

解答例

解答例

注意点

long long型を使用する。

全部Cだった場合答えがN^2/4くらいになり、int型からはみ出る。
long long型を用いること。

別解