Codeforces Round 871 (Div. 4)

Dashboard - Codeforces Round 871 (Div. 4) - Codeforces

 

 

D

방법 1 - dp

n을 쪼개서 m이 될 수 있음?
i) n = m 이면 가능
ii) n != m 이면 3|n일 때 n/3 또는 2n/3로 m을 만들 수 있다면 가능
iii) 그 외에는 불가능

 

방법 2 - 관찰

 

F

 

G

방법 1 - dp

위 캔의 모양을 아래와 같이 변형하자. 그리고 dp를 다음과 같이 정의한다.

1
2	3
4	5	6
7	8	9	10

dp[r][c] := i를 쳤을 때 넘어지는 점수의 합
dp[r][c] := i² + dp[r-1][c-1] + dp[r-1][c] - dp[r-2][c-1]

ex) dp[9] = 9² + dp[5] + dp[6] - dp[3]

 

방법 2 - prefix array

캔의 모양을 2번째 사진과 같이 변형하고 2차원 누적합을 이용한다.

 

 

H

배열의 원소의 개수가 2 ⋅ 10⁵ 이고 각 원소는 0~63 까지의 값을 가질 수 있으므로 다음과 같이 dp를 정의하면 된다.

배열 A[1...N]에 대해 
dp[i][state] := A[1...i]를 활용하여 만들 수 있는 subsequence의 연산의 결과가 state 인 경우의 수