Codeforces Round 909 (Div. 3)

Dashboard - Codeforces Round 909 (Div. 3) - Codeforces

 

 

B

방법 1 - backtracking

모든 n 약수 k에 대해 maximum absolute difference를 구한다.

약수의 개수는 대략 $ O(n^{\frac{1}{3}}) $ 이고 각각의 약수에 대해 O(n) 시간에 최대 무게 차이를 계산할 수 있다.
(물론 prefix sum으로 전처리해서 더 빨리 구할 수도 있음)

 

방법 2 - brute force

k를 1부터 n까지 증가해가며 최대 무게 차이를 계산하자. 이때 계산은 prefix sum을 이용해야 시간초과가 나지 않는다. 무게 차이를 계산 할 때는 k칸씩 뛰어가며 연산을 하므로 시간 복잡도는 harmonic serise를 통해 구할 수 있다. $ O(n  lg  n) $

 

C

Search the subsegment with the maximum/minimum sum - Algorithms for Competitive Programming

 

방법 1 - dp

dp[i] := 배열 A[1...i]에 대해, 조건을 만족시키면서 i번째에서 끝나는 subsegment의 최대 합.
이라고 하자. 

i) parity가 같을 때
   dp[i] = A[i]
ii) parity가 다를 때
   dp[i] = max(dp[i] + v[i], v[i])

 

방법 2 -