AtCoder ABC128-F Frog Jump

k=A-Bを固定すれば大丈夫そうだったのですが、なぜかサンプルが合わず愚直解を書いてみる。一応出すも当然TLE。

N, = map(int, input().split())
xs = list(map(int, input().split()))
r = 0
for a in range(1, N-1):
    for b in range(1, N-2):
        if a <= b:
            continue
        if (N-1-a)%(a-b):
            continue
        n = (N-1-a)//(a-b)
        if a%(a-b) == 0:
            if a <= (a-b)*n:
                continue
        s = a
        t = xs[a]
        ps = [(a,xs[a])]
        for i in range(n):
            s -= b
            t += xs[s]
            ps.append((s,xs[s]))
            s += a
            ps.append((s,xs[s]))
            t += xs[s]
        print("k:%d, A:%d, B:%d"%(a-b,a,b))
        print(ps, t)
        r = max(r, t)
print(r)

k:3, A:4, B:1
[(4, 31), (3, -99), (7, -39), (6, -15), (10, 0)] -122
k:4, A:6, B:2
[(6, -15), (4, 31), (10, 0)] 16
k:2, A:6, B:4
[(6, -15), (2, 0), (8, 43), (4, 31), (10, 0)] 59
k:1, A:6, B:5
[(6, -15), (1, -4), (7, -39), (2, 0), (8, 43), (3, -99), (9, 18), (4, 31), (10, 0)] -65
k:3, A:7, B:4
[(7, -39), (3, -99), (10, 0)] -138
k:1, A:7, B:6
[(7, -39), (1, -4), (8, 43), (2, 0), (9, 18), (3, -99), (10, 0)] -81
k:2, A:8, B:6
[(8, 43), (2, 0), (10, 0)] 43
k:1, A:8, B:7
[(8, 43), (1, -4), (9, 18), (2, 0), (10, 0)] 57
k:1, A:9, B:8
[(9, 18), (1, -4), (10, 0)] 14
59

上を見るとやはりkを固定するので良さそう。kが同じ時に成り立つA候補で最小のものAmを計算する。 例えば上の例で、A-B=2の時 Am=6で

[(6, -15), (2, 0), (8, 43), (4, 31), (10, 0)] 59

並び替えると

[(6, -15), (4, 31), (8, 43), (2, 0), , , (10, 0)] 59

A-B=2, A=8では

[(8, 43), (2, 0), , , (10, 0)] 59

と先頭２つずつ除いていくとA'=A+1の場合も計算できるので、マイナスになるとゼロにする処理をしながら(k, Am)について処理すれば、(k,A)候補のうち最大の結果が得られる。 正解コード

N, = map(int, input().split())
xs = list(map(int, input().split()))
r = 0
for k in range(1, N):
    a = (N-1) % k
    for _ in range(1+(N-1-a)//k):
        b = a - k
        n = (N-1-a)//k
        if a <= b or a <= k:
            a += k
            continue
        if a%(a-b) == 0:
            if a <= (a-b)*n:
                a += k
                continue
    if a >= N-1:
        continue
    s1 = a
    s2 = n * (a-b)
    t = xs[s1]
    for i in range(n):
        s1 += a-b
        t += xs[s2]
        t = max(t,0)
        t += xs[s1]
        s2 -= a-b
    r = max(r, t)
print(r)

kからAmを出すのも少し大変だった。a = (N-1) % kでできるかと思ったら、b<0, b<a, a<=n-1の条件を満たす必要あり。 最後に葉が消えること考慮してあげないといけない。条件は(a%(a-b) == 0) and (a <= (a-b)*n)。 無駄にfor文回したが、a = (N-1) % k + hoge * kの形で書けそう。