まず、条件(3)が無ければ、答えは $S$ に含まれる（Rの個数）×（Gの個数）×（Bの個数）で求められる。
また、条件(3)の候補となるindexの組はたかだか $O(|S|^2)$ しかないので、全て調べられる。
間隔が同じ $i,j,k$ について、条件(1)(2)を満たしているものがあれば、答えから引けばよい。
from collections import Counter
n = int(input())
s = input()
cnt = Counter(s)
ans = cnt['R'] * cnt['G'] * cnt['B']
for i in range(n):
l = 1
si = s[i]
while i + l * 2 < n:
if si != s[i + l] and si != s[i + l * 2] and s[i + l] != s[i + l * 2]:
ans -= 1
l += 1
print(ans)
こういうの苦手……に加え、実際の計算量と直感的な計算量が合わない。
数列のGCDが1以外の値（$g$ とする）を取るというのは、以下の2つを共に満たしているときである。
さらに全ての項を $g$ で割った時、そこに存在しうる数字は、$1～\dfrac{K}{g}$ のいずれかである。（切り捨て）
ということは、$K$ について以下のような関数を定義すれば、何となく再帰的に求められそう。
$f(k) = $ 各項が $1～k$ の長さ $N$ の数列で、GCDが1になるものの個数
答えは、$f(\dfrac{K}{1})+2f(\dfrac{K}{2})+3f(\dfrac{K}{3})+...+Kf(\dfrac{K}{K})$ となる。
また、個数の帳尻を合わせると $k^N = f(\dfrac{k}{1})+f(\dfrac{k}{2})+f(\dfrac{k}{3})+...+f(\dfrac{k}{k})$ となる。
つまり、$f(k) = k^N - f(\dfrac{k}{2}) - f(\dfrac{k}{3}) - ... - f(\dfrac{k}{k})$ で求められる。
ただし、$f(1)=1$ とする。
さて、$\dfrac{k}{2},...,\dfrac{k}{k}$ だが、$k$ が大きくなるにつれ同じ値が相当数含まれる。特に、$\dfrac{k}{k/2}$ 以降に関しては必ず1となる。
K=14
割る数 1 2 3 4 5 6 7 8 9 10 11 12 13 14
14 7 4 3 2 2 2 1 1 1 1 1 1 1
なので、一度求めた $f(k)$ についてはメモ化しておくことで、$f(k)$ を再帰的に求めていっても、そこまで大した計算量にならないで済む。
具体的には、最大ケース $N=10^5,K=10^5$ で、下記get()が呼ばれるのが390754回、さらにその中でcntに存在せずに具体的な計算に進むのが630回。
def solve(n, k):
if k == 1:
return 1
MOD = 10 ** 9 + 7
ans = (k // 2 + 1 + k) * (k - k // 2) // 2 % MOD # k/2～k の和
cnt = {1: 1}
def get(d):
if d in cnt:
return cnt[d]
result = pow(d, n, MOD)
result -= d - d // 2
for i in range(2, d // 2 + 1):
result -= get(d // i)
result %= MOD
cnt[d] = result
return result
for i in range(1, k // 2 + 1):
ans += i * get(k // i)
ans %= MOD
return ans
n, k = map(int, input().split())
print(solve(n, k))
偶数の時は簡単。
先頭から1つおきに取っていき、どこかで2つ間を空け、そこからまた1つおきに取っていく、という方法しかない。（先頭、末尾の長さが0の場合も含める）
3 1 4 1 5 9 2 6 ~ ~ ~ ~
「先頭から1つおき」「末尾から1つおき」に取ったときの累積和を求めておき、切り替える箇所を全探索すればよい。
3 1 4 1 5 9 2 6
先頭から 0 3 7 12 14
末尾から 17 16 15 6 0
↓
0 3 7 12 14
+ 17 16 15 6 0
--------------------
17 19 22 18 14 → 最大値は22
奇数の時が困る。
たとえば $N=11$ なら5個だけ選べばよいので、間を2つ空けてよい場所が2つ（または間を3つ空けてよい場所が1つ）ある。
3 1 4 1 5 9 2 6 5 3 5 ~ ~ ~ ~ ~
間を空ける場所全探索は、$O(N^2)$ かかるので厳しそう。DPで解けないか考える。
ここで、問題の条件は「取らない数を最小化する」ことでも達成できる。よって、問題を以下のように言い換える。
こうすると、以下のDPで求めることができる。2つ以上連続で取らないことが無いので、2つ前までの状態があればよく、多少、遷移もわかりやすくなる。
INFは、その条件が不可能なことを示す。
各遷移、INFの次は1個空けて取る操作、その次は連続して取る操作を示す。
最終的に、$DP[N-1][1]$ または $DP[N-2][0]$ の小さい方が答えとなる。（$DP[N-2][2]$ は取る数が足りてない）
3 1 4 1 5 9 2 6 5 3 5
j 0 - - - 4 - 5 - 14 - 15 - 17 - ←┬ 17,19の小さい方が答え
1 - - 3 - 5 - 7 - 9 - 14 - 19 ←┘
2 - 0 - 1 - 2 - 11 - 17 - 20 -
各遷移のイメージ
x → min(x,y)+Ai
- y ↗
元の問題の答えは、$A_1～A_N$ の総和から、言い換えた問題の答えを引くことで求められる。
from itertools import accumulate
def solve_odd(n, aaa):
INF = 10 ** 18
p0, p1, p2, a0, a1, a2 = INF, INF, INF, INF, INF, 0
for a in aaa:
n2 = min(INF, p2 + a)
n1 = min(INF, a2 + a, p1 + a)
n0 = min(INF, a1 + a, p0 + a)
p0, p1, p2, a0, a1, a2 = a0, a1, a2, n0, n1, n2
return sum(aaa) - min(p0, a1)
def solve_even(n, aaa):
fwd = [0] + list(accumulate(aaa[::2]))
bwd = [0] + list(accumulate(aaa[::-2]))
bwd.reverse()
return max(f + b for f, b in zip(fwd, bwd))
n = int(input())
aaa = list(map(int, input().split()))
if n % 2 == 0:
print(solve_even(n, aaa))
else:
print(solve_odd(n, aaa))