240125 팀 연습 (Jakarta 2018)

동일하게 원격 1컴 체제로 진행했다.

 

셋 : https://codeforces.com/gym/102001 (https://www.acmicpc.net/category/detail/1965)

 

 

petamingks가 앞, 내가 가운데, kwoncycle이 뒤를 보고 시작했다. 순서를 고정하자는 의견을 내 보았지만 묵살당했다.

 

~0:03

주르륵 풀리기 시작한 I를 kwoncycle이 잡고 풀었다. 나는 E~H를 훑어봤지만 지문이 다 길어서 슬펐다.

 

~0:16

petamingks가 A 풀이를 찾았다고 하길래 스코어보드에 WA가 깔렸다고 전해주었다. 사풀인 것 같다며 돌아갔다가 진짜 풀이를 찾았다며 짜더니 풀었다. 나는 H, G를 읽었다. H는 얼마 전 공부한 System of Difference Constraints 문제인 것 같아서 신났는데 \(N\)이 십만이길래 일단 넘기고 G를 봤다. 

 

~0:21

kwoncycle이 L을 풀었다. 나는 G를 쭉 잡았다.  G는 \(N=500\)인데 쉬운 세제곱로그 풀이가 있었다. 이걸 그대로 짜다가 어떤 아이디어를 얹으면 세제곱으로 줄일 수 있다는 것을 깨닫고 밀고 다시 짰다. 끝나고 보니 세제곱로그도 시간 안에 잘 돈다는 것 같다.

 

~0:39

G를 완성 후 사소한 코딩 미스로 1번 틀리고 맞았다. 이후 나는 D, petamingks는 H, kwoncycle은 K를 잡았다.

 

~1:06

케웤 문제인 D를 내가 2번 틀리고 맞은 후 혼났다. D를 짜고 나서는 petamingks가 준 H 풀이를 코딩하기 시작했다. 이후 둘은 K 풀이에 대한 토론을 했던 것 같다. 

 

~1:27

다행히 H는 한 번에 맞았다. 이후 복잡한 K를 kwoncycle이 코딩하려던 중, J를 봤더니 쉬워서 먼저 짜고 주겠다고 했다. petamingks는 C로 넘어갔다.

 

~1:55

TLE의 위험이 좀 있었지만, J도 다행히 한 번에 맞았다. 이후 kwoncycle에게 진짜 컴퓨터를 넘긴 후 F를 보러 갔다.

 

~2:23

kwoncycle이 코딩이 복잡한 K를 빨리, 한 번에 맞아왔다. 이후 kwoncycle은 petamingks와 같이 C를, 나는 F 풀이가 대충 나와 코딩에 들어갔다.

 

~2:40

F 풀이가 정말 대충이었다는 것을 깨달았다. C는 constructive였는데 구성적 장인 두 명이 붙어도 빨리 안 풀리길래 어렵구나 했다.  이 과정에서 오일러 회로 같은 걸 물어보길래 대답해줬다.

 

~3:52

F를 5번 더 틀리고 맞았다. 컴퓨터가 비어 있었기에 망정이지 아니었으면 개트롤이 따로 없었을 것이다.

 

~5:00

B는 읽었으나 링크컷이 필요하다는 사실을 깨닫고 버렸으며, 모두 C에 열심히 도전했으나 끝내 해결하지 못했다.

 

문제별 요약

A (G2, solved by petamingks) : 코포식 문제라고 한다.

B (D1, Not solved) : 링컷 쓰면 된다고 한다. 티어가 기본 문제와 똑같은 것을 보면 그렇게 어렵지는 않은 것 같다. 업솔빙 예정

C (D5, Not solved) : 문제를 오일러 회로로 reduction시킬 수 있다. 한 명은 오일러 회로를 떠올렸으나 모델링을 잘못 했고, 한 명은 맞는 모델링을 했으나 오일러 회로를 풀 줄 몰랐다. 그냥 후반부라 심신 미약에 의한 의사소통 부재로 해결하지 못한 것 같다.

D (G2, solved by leo020630) : 세팅이 이거랑 비슷해서 쫄았지만, 그냥 애드혹+케웤 문제이다. 핵심 아이디어 관찰은 쉬울 수 있는데, 예외를 대충 찾아서 좀 틀렸다.

E (D2, Not solved) : 문제를 읽지 않았다. 그림을 보니 대충 어려운 기하 같다.

F (P3, solved by leo020630) : 그리디 문제인데, 생각보다 뻔하지 않았다. 생각을 충분히 하자.

G (P2, solved by leo020630) : \(K\)가 정해져 있는 경우 BFS 비슷하게 \(O(N^3)\)에 해결할 수 있다. 여기에 이분 탐색을 얹으면 \(O(N^3logN)\)이며, 이 역시 시간 안에 돌아가는 것 같다. 나는 \(O(N^3)\)에 해결하였는데, \(K=2N-2\)에서 시작해 설치할 수 있는 간선이 없으면 \(K\)를 줄인 후 설치할 수 있는지 모든 간선에 대해 확인해주면 된다. 이 과정이 최대 \(2N-2\)번 일어나기 때문에 \(O(N^3)\)이다. 쉽게 풀었는데 티어가 높아서 놀랐다.

H (P2, solved by petamingks, leo020630) : 까다로운 그리디 문제이다. petamingks가 풀이를 내 주었고, multiset이 필요했기에 내가 짰다. 모든 0을 1로 둔 후 -1로 최대한 바꾸어 주면 된다. 나는 multiset+pq로 해결하였고, 세그를 쓰는 방법도 있는 듯하다.  

I (B1, solved by chanu0808) : 쉬운 문제인 듯 하다.

J (P3, solved by leo020630) : 제한이 작아 모든 subsequence를 뽑아 정렬해줄 수 있다. 이후는 그냥 \(dp[i][j]\) = \(i\)번째 단어의 \(j\)번째 subsequence까지 사용했을 때의 답으로 두면 된다. dp 전이는 투 포인터 느낌으로 해 주면 된다. 이것 역시 쉽게 풀었는데 티어가 높아서 좋았다.

K (P1, solved by kwoncycle) : 재미있는 DFS Constructive 문제인 듯 하다. 구현이 까다로웠다고 한다. 업솔빙 예정

L (G4, solved by kwoncycle) : 문제를 읽지 않았다.

 

 

느낀 점 + 피드백

C를 못 푼 것이 좀 아쉽다. B 역시 고오급 자료구조 기본형이라 예습이 필요할 것 같다.

 

나 개인으로 보자면 까보니 어려웠던 G, H, J를 잘 풀었지만 더 쉬운 D, F같이 예외 핸들링이 까다로운 문제에서 뇌절한 것이 문제라고 할 수 있다. 이런 문제는 그냥 팀원들 주자.

 

초반은 역시 괜찮은데 후반은 여러모로 집중력을 좀 잃는 것 같다. 집중을 잘하자.

 

연습을 열심히 하자.

 

+팀연습 같이 하실 팀 환영입니다