Codeforces Round 889 (Div. 1)

오랜만에 코포를 쳤다.

A1. Dual (Easy Version) (0:14, +)

A가 1/2로 나뉘어 있길래 1부터 풀었다. 횟수가 넉넉해서 대충 하나를 좀 키우고 2배씩 커지도록 만들면 될 것 같았다. 그대로 짜서 AC를 받았다.

 

A2. Dual (Hard Version) (0:50, +2)

2는 1의 접근법을 사용할 수 없었다. 우선 한 가지 관찰이 필요하다: 모든 수가 0 이상이거나 모든 수가 0 이하이면 \(N-1\)번의 연산으로 단조 수열을 만들 수 있다. \(N=20\)이므로 우리는 12번 안에 모든 수를 0 이상 혹은 이하로 만들어야 한다. 이제 주어진 수열에서의 양수의 개수를 \(a\), 음수의 개수를 \(b\), 양수 중 최댓값을 \(x\), 음수의 절댓값 중 최댓값을 \(y\)라 하겠다. 편의상 \(a \leq b\)로 가정한다. 만약 \(y \leq x\)라면 모든 음수에 \(x\)를 더하는 것으로 조건을 만족할 수 있다. \(y \leq 10\)이므로 이 경우 필요한 횟수는 10번이다. 이제 \(x < y\)인 경우가 남았다. 만약 \(a \leq 12\)라면 모든 양수에 \(-y\)를 더하는 것으로 모든 수를 0 이하로 만들 수 있다. 남은 경우는 \(a > 12\)인데, 이 경우 \(b \leq 7\)이므로 1을 32로 만드는 데 필요한 횟수 5번 + 7번으로 총 12번 이내에 모든 수를 양수로 만들 수 있다. 이를 \(a<b\)인 경우에 대해서까지 고려해서 구현해주면 정답을 받을 수 있다.

 

B. Earn or Unlock (2:23, +7)

\(i\)번째 위치에 도달할 수 있는 경우에 대해 \(max{S_i-(i-1)}\)이 정답이다. 만약 \(i>n\)인 경우 \(S_n\)을 사용해주면 된다. \(S_i\)는 \(A_i\)의 누적합이다. 이제 도달 가능 여부를 판별하는 일만 남았는데, 제곱 미만의 풀이를 떠올리기 힘들다. 따라서 제곱으로 해결하자. 완성 가능 여부만 따지면 되는 냅색 DP의 경우 비트셋으로 해결할 수 있음이 잘 알려져 있다. 이를 그대로 사용하면 된다. 사풀을 2번, 비트셋을 사용한 이후에도 반례를 찾지 못해 5번을 틀린 후 겨우 찾아 맞을 수 있었다.

 

비트셋이 정해인 문제에 머리가 아득해졌다. 대회에서는 최대한 볼 일이 없었으면 좋겠다. 또한 SCPC에서도 그랬지만 대회 시즌인 만큼 제출을 신중히 하는 연습을 할 필요가 있을 것 같다.