Atcoder beginner contest125 [python]

C:GCD on Blackboard

atcoder.jp

数列があって、ある1つの要素を抜いた時のGCDの最大値を求める問題。
愚直に1個ずつ抜いて計算してTLEでした。小手先の高速化はしてみましたが、TLE。

解法

ある値を抜く時のGCDは、よりも左のGCDとより右のGCDのGCDを取れば良い。
全てのについてそれらを事前に計算しておくことで、高速に最大GCDを求めることができる。

import numpy as np

def gcd(a,b):    
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)
    
N = int(input())
A_list = list(map(int, input().split()))

# =====
# initialize L and R
# =====
L = np.zeros(N+1)
R = np.zeros(N+1)

for idx, element in enumerate(A_list):
    if L[idx] == 0:
        L[idx+1] = element
    else:
        L[idx+1] = gcd(L[idx], element)

for idx, element in enumerate(A_list[-1::-1]):
    idx = N-idx
    if R[idx] == 0:
        R[idx-1] = element
    else:
        R[idx-1] = gcd(R[idx], element)

ans = 0
for i in range(N):
    if L[i] == 0:
        M = R[i+1]
    elif R[i+1] == 0:
        M = L[i]
    else:
        M = gcd(L[i], R[i+1])
    if ans < M:
        ans = M

print(int(ans))

D : Flipping Signs

atcoder.jp

練習のため、dpで解く。
に対して、を、番目の要素の正負を確定した上で、i番目の要素をの時はそのまま(つまりi+1番目の要素もそのまま)、の時は反転させた(つまりi+1番目の要素も反転)とした時の最大値とします。

こういうdpの定義をスパッとできるようになりたい。

dpテーブルの初期条件は、

• (0番目の要素と1番目の要素を反転させる操作に相当し、1番左の要素を反転させることはできないため、有効な操作ではありません。)
• 

更新は、
https://img.atcoder.jp/abc125/editorial.pdf
の通り。

最終的にほしいのは、です。

import numpy as np
N = int(input())
A_list = list(map(int, input().split()))

dp = np.zeros((len(A_list)+1, 2))
dp[0][1] = - 10**5

for idx, a in enumerate(A_list):
    dp[idx+1][0] = max(dp[idx][0] + a, dp[idx][1] - a)
    dp[idx+1][1] = max(dp[idx][0] - a, dp[idx][1] + a)
print(int(dp[N][0]))