Codejam 2021 Round 2

• Preperation
• Preliminary & Round 1
• Problem 1 : Minimum Sort
• Problem 2 : Matrygons
• Problem 3 : Hidden Pancakes
• Round 총평

올해 Codejam의 (나한테 있어) 사실상 마지막 round이므로 (R3 는 재밌게 하겠지만 competition으로써는 얻을게 없다) Hashcode 때처럼 prep과 과정을 좀 적어보려고 한다. 앞으로 메이저한 대회는 이렇게 적어볼 생각이다.

Preperation

그렇게 말하긴 했지만 준비할수 있었던건 딱히 없다. 올해는 CP에 쓰기에는 너무 할일이 많다.

방학때면 모를까…학기중에 PS/CP에 많은 시간을 투자하기에는 아무래도 어려움이 많다. 그래도 작년 코드잼과 지금 비교했을때 (PS적인 측면에서) 어떤 점들이 나아졌는지 / 나아지지 않았는지 비교해보면 준비를 되새기는 측면에서 조금은 도움이 될것 같기도 하다.

• Courses. Problem solving은 결국 아이디어와 지식이 둘 다 필요한데, 몇몇 내용들 - 작년 1학기에 들은 알고리즘, 지금 듣고있는 정수론 등 - 은 도움이 되는건 사실이다. 대충 다 아는 내용이긴 했지만 혼자서는 절대 하지 않을 revisit을 다시 해보는건 분명히 의미가 있다. General하게, 정수론 같은 파트들은 지식적인 측면보다는 그냥 고민해보는 시간을 갖는게 의미가 있다고 생각한다.

• C++ 구현능력은 오히려 작년만 못하다. 2학기 소개원실이 분기점이 되어서 그런거 같은데, 돌아오려면 아직 멀었다고 생각한다. 2019년 ICPC 때 팀원들이 굉장히 구현을 힘들어해서 아니 멀쩡했던 사람들이 왜이러나 싶었는데, 대충 왜그런지 알거 같기도 하다.

• 그동안 CF rating은 답보를 거듭했는데, 한문제 잡고 푸는 능력은 작년에 비해 나아졌다고 생각한다. dhdroid 같은 경우에는 빠른 코딩 실력을 갖추지는 못했지만 어려운 문제를 고민하면 나보다 훨씬 체계적으로 관찰을 쌓아나가는 능력이 있는데, 같이 공부하면서 이런걸 많이 배웠다.

Preliminary & Round 1

• Preliminary는 30점 절대평가 형식이므로 카페에 앉아서 그냥 대충 앞 몇문제만 내보고 던졌다. 그때 꽤 바쁜 일정들이 있었기 때문에…
• Round 1은 뭔가 항상 R1B를 치게 되는 기분이다.

Problem 1 : Minimum Sort

Easy. 바로 떠오르는 Naive 풀이를 그냥 구현하면 된다.

[1, 100] 중 가장 작은걸 뽑고, 맨 앞으로 보낸 다음, [2, 100] 중 가장 작은걸 뽑고…. 이렇게 하면 소모하는 코인 수는 $1/2 + 1/3 + \dots 1/100$ 개 정도이고, 이 값은 6보다 작으므로 이대로 짜서 내면 된다.

Problem 2 : Matrygons

$K$가 주어질 때, <조건>을 만족하는 distinct한 수열 $x_1, x_2, \dots x_N$ 중 $N$이 최대인 수열을 찾는 문제.조건>

• $\sum_{i = 1}^{N} x_i = K$ 여야 하며
• $x_1$ 이 $x_2$의 약수, $x_2$가 $x_3$의 약수…. $x_N$ 까지 이를 만족해야 한다.

먼저, $K$ 가 $x_1$ 의 배수임을 쉽게 관찰할 수 있다. 또한, $K - x_1$ 은 $x_2$의 배수이고… 이를 반복할 수 있다는 것이 첫번째 관찰이다.

두번째로, $N$이 reasonable하게 작음을 관찰하자. $2x_i \leq x_{i+1}$ 임을 확인할 수 있는데 (배수여야 하고, 같으면 안 되므로) 이를 보면, $N$은 많아야 $\log K$, 30 정도이다.

이 두가지를 이용하면, $f(k, t)$ 를 “현재 $x = t$, $K = k$일 때 $x$ 부터 시작해서 수열을 만들어서 $k$를 만들고자 할 때, 최대의 $N$값” 으로 정의하면 $f(k, t)$ 를 재귀적으로 꽤 빠르게 계산할 수 있다. 설명하기가 굉장히 까다롭지만 코드는 매우 간단하므로 아래 코드를 참고하자.

주의할 점은, 1각형이나 2각형은 없으므로 처음에는 3각형 이상으로 시작해야 함을 주의하자. (이걸로 1틀했다…)

라운드가 끝나고 dhdroid 와 discussion했는데 역시 DP황답게 나보다 훨씬 좋은 DP 솔루션을 가져왔다. :fan:

Problem 3 : Hidden Pancakes

이 문제의 경우, 주어진 문제 상황을 잘 이용하면 “$i$ 번이 $j$번보다 크다/작다” 형태의 정보를 많이 얻을 수 있다. 이러한 정보들이 consistent 하다면, transitivity에 의해 imply되는 정보들을 제외함으로써 Directed tree를 만들 수 있다.

예를 들어, 예제 2는 1 1 2 인데, 이를 다음과 같이 볼 수 있다.

• 처음에는 <1> 이 보이는 상황이다.
• 1 다음에 1이 온 시점에서, 보이는게 1개이므로 현재 보이는 것은 <2> 이다. 2번이 1번을 스택에서 쫓아냈으므로, 2번이 1번보다 크다.
• 그다음 2개가 보이므로 <2, 3> 이다. 3번이 2번을 쫓아내지 못했으므로 2번이 3번보다 크다.

이를 트리로 그리면 2번이 루트가 되고, 1번과 3번이 2번의 child node인 트리가 된다.

같은 방법으로, 예제 1인 1 2 2 1 을 보자.

• 처음에는 <1> 이 보이는 상황이다.
• 두번째 시점의 스택은 <1, 2> 이므로 1이 2보다 크다.
• 세번째 시점의 스택은 <1, 3> 인데, 스택에서 3이 2를 쫓아냈으므로 3이 2보다 크다. 또한, 3이 1보다는 작다.
• 마지막 시점에서 <4> 가 모두 쫓아냈으므로 4가 1보다 크다.

따라서, 4 > 1 > 3 > 2 임을 알 수 있다. 이를 트리로 그리면 한 줄로 쭉 이어진 트리가 된다.

이렇게 트리를 그리고 나면, 이 “트리가 제공하는 partial order”를 깨지 않으면서 $n$개의 팬케익 크기를 정하는 문제가 되는데, 이는 다시 말하면 1, 2, … $n$을 각 트리 노드에 써넣되 topological order를 깨지 않는 permutation의 개수를 찾는 문제가 된다.

이는 즉, 현재 주어진 트리의 적법한 topological order의 개수를 세는 문제와 같다. 이 문제는 나름대로 well-known 이므로, 약간 구글링해보면 Tree DP 로 이를 해결하는 방법을 찾을 수 있다. 앳코더에 문제로도 나온 적 있다. 문제 링크

분명 저 앳코더 문제를 풀때는 생각을 해서 ($O(n \log n)$이긴 했지만 이걸 혼자 찾아냈었는데, 왜인지 모르겠지만 라운드 때는 저런 생각을 전혀 못했다. :( Tree DP는 항상 너무 어려운듯…)

Round 총평

올해의 첫 메이저 대회인데 나름 재밌었다. 작년이나 재작년 Round 2에 비하면 조금 쉬워진듯한데, 어차피 상대평가니까 큰 의미는 없을 수도…

1000등이라는 커트를 정해놓고 시작하는 라운드다 보니 66점을 받은 시간으로 갈릴수밖에 없는데, 그래도 다행히 막 첫 태스크 빨리푼 시간 이런식으로 갈린 speed중심의 대회는 아니라서 약간 다행이다. 간단한 아이디어 / DP / 트리 DP 라는 첫 3문제의 세팅도 reasonable했다고 보고…

R3도 재밌게 치고 후기정도는 올릴 계획이다 :P