Team study session : NCPC 2018
알고리즘 문제풀이/Team Swift Turtwig 2020 2020. 10. 4. 17:42병특에 들어가서 작년 팀원들이 휴학을 하게 되었기 때문에, 과 후배들과 함께 새 팀을 만들게 되었다.
작년 팀이랑 맞다이를 위해 (...) 상성을 맞춰 팀명을 swift turtwig으로 지었는데, 4세대 포켓몬은 스타팅들 간에 역상성이라서 (세심하게 맞추지 않는다는 가정하에, 초염몽이 엠페르트를 생구 A252 인파이트로 OKO, 토대부기가 초염몽을 지진으로 OKO, 엠페르트가 토대부기를 눈보라나 냉동빔으로 OKO한다) swift를 박기로 했다 (구애스카프 공보정 토대부기는 지진으로 간당간당하게 OKO낼수 있다). ㅋㅋ!!!
팀원) Gratus907 / Heatz123 (Heatz) / New_sprout
첫 팀연습으로 NCPC 2018을 돌기로 했다. 리저널이라 5시간짜리 셋이지만 우리는 인예준비 중이므로 3시간만 잡고 돌았는데, 그럭저럭 나쁘지 않은 것 같다. 개인별 실력은 큰차이 없이 비슷비슷한듯..
NCPC는 브실골플다 순서대로 21152 구성으로, 한국 인예랑 비슷한 난이도로 구성되어 있다. ABC / DEFG / HIJK로 나눠서, 앞부분을 Sprout, 중간을 Heatz, 끝을 내가 잡고 일단 읽었는데 결과적으로는 Heatz가 어려운 구간을 혼자 받아서 고생했다 (...)
B. Baby Bites (B3) 00:19 AC
Sprout이 그냥 바로 코딩 들어갔다. 툴에 안 익숙해서 시간을 약간 날려먹었지만 이건 금방 해결될 문제고...
파이썬으로 쉽게 코딩할수있는 단순 구현 문제였다고 한다.
I. Intergalactic Bidding (G4) 00:27 AC
수열 $a_n$ 이 주어진다. $a_n$ 은 $a_{i+1} > 2a_i$ 를 만족한다. 이때 subset sum이 $S$가 되는 집합을 찾는 문제.
크기에 관한 저 성질 때문에, Greedy Approach가 성립한다. 숫자를 큰 것부터 보면서, 만약 지금까지의 합이 $C$이고 남은 sum $S - c$ 의 값이 지금 보고 있는 원소 $a_j$ 보다 크다면, $a_j$를 넣지 않으면 $a_i > \sum_{i = 1}^{j-1} a_i$ 를 만족하므로, 채울 방법이 없다. 따라서 Greedy하게 뒤에서부터 넣을지 말지 정하면서 가면 된다.
수가 최대 $10^{1000}$ 까지라서 파이썬을 써야 하는데 익숙하지 않다. 파이썬 코딩을 별로 안 해서..
C. Code Cleanup (B1) 00:41 AC
구현 문제 2. 쉽게 맞아 왔다.
이쯤해서 나는 J와 K (J가 더 쉬워 보였고, 비슷한 문제를 푼 적 있다고 생각했지만 K가 더 재밌어 보였다), Heatz는 G를 잡고 있었다. G번 설명을 잠깐 들었는데 Heatz는 뭔가 그리디하게 잘 construction할 수 있지 않을까 하는것 같았고, 나는 시도했던 가정이 망해서 바로 G를 버리고 K로 돌아왔다. H번은 결과적으로는 매우 쉬웠는데 빡구현인거같다는 잘못된 판단으로 던져버렸다.
K. King's Colors (P3) 00:56 AC
트리가 주어지고, 트리를 정확히 $k$색으로 (안 쓰는 색 없이) 칠하는 경우의 수 찾기. 당연히 그래프 색칠 문제의 일반적인 원리를 따라서, 이웃한 정점 간에 같은 색을 칠해서는 안 된다.
$k$ 색 *이하로* 찾는 문제를 생각해 보자. 루트를 $k$색 중 하나로 고정하고 나면, 각 정점의 색은 parent와 다르기만 하면 되므로, $k$색 이하로 찾는 문제의 답은 $k(k-1)^{n-1}$ 이다. 이 값을 $f(k)$ 라고 하자. 이제, 포함-배제 원리로부터, 우리가 원하는 답은 $f(k) - f(k-1) + f(k-2) - \dots$ 형태로 나올 것이다. 다만, 어떤 색들을 쓸것인지를 골라야 하기 때문에, 실제 답은
$$\sum_{i = 0}^{k-2} (-1)^{i} \binom{k}{i} (k-i)(k-i-1)^{n-1}$$ 위 식이 된다. 실제로 트리를 받을 필요도 없다.
E번을 고민하던 Heatz가 뭔가 코딩을 해보려고 했지만 실수가 있었던 듯 잘 안 된다는 말과 함께 컴퓨터를 넘겼다. 이떄 코딩 큐가 꽤 오래 비었는데, 문제 난이도상 어쩔수 없었던것 같기도...
J. Jumble String (P4) 01:46 AC
정수 $a, b, c, d$ 가 주어진다. 0과 1로 이루어진 string을 만들되, 이 string $S$에 subsequence 00이 $a$번, 01이 $b$번, 10이 $c$번, 11이 $d$번 등장해야 한다.
Codeforces Round 640 F 랑 비슷하다고 생각했는데, 저 문제는 substring이라 셋업이 비슷하지만 풀이가 아에 다르다.
먼저, $a$와 $d$로부터 $n_0$와 $n_1$ (0과 1의 개수) 를 확정할 수 있다. $n_0$ 개의 0이 있으면 subsequence 00은 무조건 $\frac{n_0 (n_0-1)}{2}$ 개이기 때문. 따라서, 이들을 적당히 배치해서 01과 10만 맞추면 된다.
0000...0 1111...11 은 01과 10의 개수가 각각 $(n_0 n_1, 0)$ 개이다. 여기서, 1 한개를 왼쪽으로 넘겨서 000...010111...1을 만들면 01이 하나 줄어들고, 10이 하나 늘어나게 된다. 이런식으로 하나씩 넘기면 01이 하나씩 10으로 바뀌므로, 가능한 모든 $(b, c)$는 (개수가 valid 하다면) 잘 만들 수 있다. 따라서 (1 * p, 0 * q, 1 * r, 0 * s, 1 * t) 로 문자열을 인코딩한다음, 이들에 대한 조건 ($r = 0$과 $r = 1$ 두가지밖에 없고, $pn_o + rs = b$ 같은 식들) 을 모두 만족하는 p q r s t를 찾으면 된다. 실제로는 $r = 0$과 $r = 1$을 분리해서 생각하고, $p$ 의 값을 0부터 $n_1$ 까지 돌면서 판단했다 ($n_1 \leq 50,000$)
이렇게 풀어도 매우 많은 예외가 있는데, 예를 들어 0 0 0 1 은 '11' 로 가능하고, 0 0 0 0 도 '1' 로 가능하고, 0 1 0 0 도 '01' 로 가능하다. $n_0 = 0$ 또는 $n_1 = 0$에 관련된 예외들을 수없이 처리해야 하는 매우 귀찮은 문제.
H. House Lawn (S4) 01:54 AC
'평균' 이라서 매우 간단해지는 문제. 평균적으로 각 기계가 분당 어느정도 성능인지를 판단할 수 있으면 된다.
남은 1시간 동안 heatz와 sprout이 E번에 대한 의논을 끝내고 sprout이 코딩을 잡았고, 나는 D를 풀어보려고 했는데 한참 뒤에 E번에서 communication의 문제로 문제 이해가 잘못되었음을 알게 되면서 라운드가 끝났다. 이런 부분들은 조금 고쳐나가야 할 것 같고, 실제로는 코딩큐가 많이 비는 등 문제들도 해결해야 한다. 첫 팀연습 치고는 그럭저럭 나쁘지는 않았던 듯...
