ABC162 D - RGB Triplets - あっとのTECH LOG

問題原文

問題要旨

R, G, B のみからなる長さ $N$ の文字列 $S$ が与えられる。
$i ＜ j ＜ k$ であって、 $S_i$ , $S_j$ , $S_k$ が全て異なり、 $j - i != k - j$ であるようなものの通り数を求めよ。

$1 \leq N \leq 4000$

解法

全体からカウントしてはいけないものを取り除く 方針を取る。
まず答え全体は明らかに、 (Rの数) × (Gの数) × (Bの数) である。
そしてこの中には、 $j - i = k - j$ となるものが混じっているので、「 $j - i = k - j$ であって $S_i$ , $S_j$ , $S_k$ が全て異なるもの」を引けばよい。
これは $i, j$ を固定して $O(N^{2})$ で数えられる。

実装

N = int(input())
S = input()

ans = S.count('R') * S.count('G') * S.count('B')
for i in range(N):
    for j in range(i + 1, N):
        if (j + j - i < N) and ({S[i], S[j], S[j + j - i]} == {'R', 'G', 'B'}):
            ans -= 1

print(ans)

感想

本番は「こういうのは真ん中固定！w」をした結果累積和を３本持ち、それだけならまだしも無駄にsetの演算を取り入れてTLEし、破滅した。
最近のDは方針間違えた結果強引に通すみたいことが多くて結構かなしい。