Codeforces Round #636 (Div. 3) 참가 후기

Dashboard - Codeforces Round #636 (Div. 3) - Codeforces

일주일만에 돌아온 Div. 3. 이번에도 3문제 하한선을 지킬 수 있을지?

---

A. Candies

n이 주어질 때, $k>1$에 대해 $x(1+2+4+ \cdots + 2^{k-1})=n$을 만족시키는 임의의 $x$를 구해 보자.

 

주어진 식은 $x(2^{k}-1)=n$으로 정리할 수 있다. 이제 $x$가 자연수가 되도록 $k$를 조정하면 된다.

$n \leq 10^{9} \leq 2^{31}$이기 때문에 $k \leq 31$ 범위에서 항상 답을 구할 수 있다.

 

참 쉽죠?

 

B. Balanced Array

가장 쉬운 답안을 생각해 보면, $[2, 4, 6, \cdots, n, 1, 3, 5, \cdots, n-1]$ 정도가 되겠다. 그런데 오른쪽 절반의 합이 왼쪽보다 $\frac{n}{2}$ 작으므로 정리해 보면 $[2, 4, 6, \cdots, n, 1, 3, 5, \cdots, \frac{3n}{2}-1]$이 된다.

 

사실 예제만 잘 관찰했다면 위의 내용을 쉽게 추론할 수 있다. 나 같은 경우에는 최대한 간단한 답을 생각해 보려고 했던 건데, 예제를 보고 생각에 확신을 갖게 되었다.

 

여기까지는 꽤 쉬운 편이 아닌가? 하는 생각도 들었고..

 

C. Alternating Subsequence

어떤 수열 $a$에서 alternating subsequence는 $a$의 부분수열 중 모든 인접한 원소의 부호가 다른 수열이다. $a$의 가장 긴 alternating subsequence 중 원소의 합이 최대가 되는 수열을 구해야 한다(정확히는 합만 구하면 되지만, 합을 구하려면 어차피 수열을 구해야 하니까).

 

여기서 조금 어렵게 생각했다. 

최대 길이를 먼저 구한 다음, 최댓값이 되는 수열을 찾아야 한다. 최대 길이는 동적 계획법으로 구할 수 있고.. 그런데 최댓값은 어떻게 찾지? 인덱스로 추적해야 하나?

동적 계획법은 20분 걸려서 구현했는데, 아무리 생각해 봐도 이건 아닌 것 같다. 그래서 예제 답안을 관찰해 보기로 했다.

 

alternating subsequence의 길이가 최대니까, 부호가 같은 모든 구간에서 수를 하나씩 골라야 한다. 그런데 거기서 합이 최대가 되려면.. 부호가 같은 구간에서 최댓값을 찾으면 되는 것 아닌가?

 

예를 들어 다음의 입력이 주어진다고 해 보면, 아래처럼 구간을 나눈 후 각 구간의 최댓값을 찾으면 된다.

-2 | 8 3 8 | -4 -15 | 5 | -2 -3 | 1

그렇다면 동적 계획법으로 미리 길이를 구할 필요도 없겠다! 그냥 수열 한 번 훑어보면 답을 구할 수 있다.

 

이미 시간은 12시 47분, 한계에 가까운 시간이었지만 문제를 풀려고 하니까 버틸 만 했다. 다행히 빠르게 정답을 제출할 수 있었다.

D번부터는 시간도 실력도 모자란 관계로 잠을 청했다. Zzz...

---

1222 -> 1276

C번까지는 풀어야 한다는 마음으로 열심히 노력했고, 문제를 풀 수 있었다. Div. 3 문제들은 예제를 잘 관찰하면 힌트를 많이 얻을 수 있는 것 같다.

Div. 2 문제도 조금씩 건드려 보자.