240207 팀 연습 (CERC 2023)

동일하게 원격 1컴 체제로 진행했다. 원래 전북대의 2 3 5 8 14 팀과 진행해야 했으나 조금 밀려서 연세대의 Cookie팀과 같은 시간에 진행하였다. 

 

셋 : https://codeforces.com/gym/104871 (https://www.acmicpc.net/category/detail/4073, 백준에는 G까지만 업로드)

 

 

petamingks가 앞, 내가 가운데, kwoncycle이 뒤를 보고 시작했다.

 

~0:13

가운데 문제를 슬쩍 본 결과 kwoncycle이 잡아야 할 것 같아 문제를 통째로 바꿨다. kwoncycle은 E가 쉽다고 하며 코딩을 시작했고, 나는 뒤 문제들을 읽던 도중 petamingks가 던진 B를 읽었다.

 

~0:16

B는 조건을 잘 읽으면 쉬운 문제였고, E가 맞자마자 짜서 AC를 받았다. 이후 원래 보던 I를 잡았는데 거의 바로 풀이가 생각났고, 컴퓨터가 비어 있어 바로 코딩에 들어갔다.

 

~0:37

I가 인터랙티브인 탓에 예제를 2개 정도 만들어 돌려본 후 맞았다. 빨리 잡아서인지 퍼솔을 먹을 수 있었다. 이 동안 petamingks는 기하 문제인 G, kwoncycle은 구현 문제인 H를 보고 있었다. G는 풀이가 잘 나오지 않았고, H는 kwoncycle이 지문 욕을 하며 보던 상태였는데 결국 H 해석이 먼저 끝나 컴퓨터를 넘겨주었다.

 

~1:43

H 코딩이 끝났고, 다행히 1번에 맞았다. 나는 그 동안 다음으로 많이 풀린 문제인 C를 열심히 생각하였다. 제한이 작아 플로우 쪽으로 생각하다 보니 다행히 쉬운 모델링으로 생각하면 min cut이 정답을 가져다줌을 깨달을 수 있었다.

 

~2:13

팀노트를 열심히 베낀 후 이상한 실수를 해 1번 틀리고 맞았다. 이후 kwoncycle와 petamingks는 G가 너무 많이 풀린 상황이었기에 G를 같이 풀었고, 나는 수학 문제로부터 자유로울 수 있었기에 적당히 풀린 D를 읽으러 갔다. D에는 냅색으로 풀어야 할 것만 같은 문제가 적혀 있었는데, N이 3만에 L이 30만이었다. 냅색에 이 요상한 제한을 보고 비트셋임을 알아차릴 수 있었고, 짜면 맞겠다는 생각으로 손코딩을 시작했다.

 

~3:30

kwoncycle이 G 코딩을 시작했고.. (중략) 맞았다. 이후 kwoncycle과 petamingks는 J를 보러 갔고, 나는 D를 짜기 시작했다.

 

~3:50

손코딩을 열심히 한 탓에 D 코딩이 빨리 끝났고, 다행히 1번에 맞았다. 이후 J 풀이가 나왔다고 해 컴퓨터를 넘겨준 후 K를 보러 갔다.

 

~5:00

J 코딩이 이루어지는 도중 K 풀이가 나왔지만, J를 1시간 안에 짤 수 있다고 해 또 손코딩을 열심히 했다. 하지만 J는 마무리되지 못했고, K 역시 공책에서 명을 다했다. 대회 종료 후 K를 짰는데, 30분 정도 걸린 후 1번에 맞은 점이 아쉬웠다.

 

 

문제별 요약

티어는 G까지는 solved.ac 티어(표본 적음), H부터는 추정입니다.

 

A (?, Not solved) : 문제를 읽지 않았다.

B (S2, solved by leo020630) : Strictly Convex 조건이 달려 있어, 그리디하게 매칭해줄 수 있음을 직관적으로 캐치하기 쉽다.

C (P1, solved by leo020630) : ingredient는 메뉴 자체의 비용으로 넘겨줄 수 있고, tool과 menu를 잘 연결해보자. tool-source 가중치는 도구의 가격, menu-sink 가중치는 메뉴의 가격, tool-source 가중치는 INF로 정한 후 그래프를 그려 min-cut을 구하면, (쓸 도구)+(만들지 않을 메뉴) 의 최솟값을 구할 수 있다. 우리가 구하는 것은 (만들 메뉴)-(쓸 도구)의 최댓값이므로, 메뉴 합에서 cut을 빼면 답을 구할 수 있다.

D (P1, solved by leo020630) : 우선 쿼리는 크게 중요하지 않고, \(t_{slow}\)순서대로 정렬한 뒤 하나씩 사용함을 발상하는 것은 쉽다. 문제는 이 다음인데, 반으로 나누는 최적해를 비트셋 냅색 DP로 계산하자. 이렇게 해를 다 구한 후 쿼리는 그냥 이분탐색으로 적절한 범위를 찾아 주면 된다. 조금 비효율적으로 짰는데 테케가 약한지 잘 돌았다. 별개로 백준 퍼솔을 이 문제를 통해 처음으로 먹어서 기분이 좋았다.

E (S4, solved by kwoncycle) : 쉬운 문제인 것 같다.

F (?, Not solved) : 문제를 읽지 않았다.

G (P4, solved by kwoncycle) : 케이스워크 후 삼분탐색 하면 되는 기하 문제라고 한다. 케웍을 몇 번 틀려서 페널티를 쌓았다.

H (G?, solved by kwoncycle) : 문제를 읽지 않았다.

I (P4, solved by leo020630) : 재미있는 인터랙티브 문제이다. 쿼리가 16개인데, \(2^{15} > 30000\)이므로 1개는 전체 1로 차수를 알아낸 후, 15개는 비트별로 봐서 켜져 있으면 1, 아니면 0을 날려주자. 이렇게 하면 차수가 1인 정점과 연결된 정점을 잘 찾을 수 있다. 이후는 이를 위상정렬처럼 밖에서부터 돌면서 리프를 순서대로 없애주면 된다.

J (D?, Not solved) : constructive 문제고, 풀이를 냈다고 하는데 짜지 못한 채로 끝났다.

K (P1, upsolved by leo020630) : 재미있는 그래프 문제이다. 몇 번 그려보면 1번 정점이 사이클에 포함되어 있어야 함을 알 수 있는데, 이를 잘 처리하는 방법이 재미있었다. 1번 정점을 루트로 하는 DFS 트리를 그리면 예외가 많이 사라지고, 4번 정도의 케이스워크를 하면 답을 찾을 수 있다. 재미있는 것과 별개로 요구하는 답의 형태가 복잡해서 구현은 좀 길었다.

L (?, Not solved) : 문제를 읽지 않았다.

 

 

느낀 점 + 피드백

스코어보드가 막 절대적이지는 않다. 특히 초반에는 리딩하고자 하는 마음도 먹어야 할 것 같다.

 

다른 팀원이 말렸을 때에는 문제를 더 많이 보자. K를 D 코딩 전에 봤으면 확실히 1솔을 더 했을 것 같다.

 

다른 두 명은 코딩 연습을 열심히 하고, 나는 제출을 신중히 하자.

 

연습을 열심히 하자.

 

+팀연습 같이 하실 팀 구합니다