240131 팀 연습 (NWERC 2019)

동일하게 원격 1컴 체제로 진행했다. 연세대의 Cookie팀과 시간을 맞춰 진행하였다. 

 

셋 : https://codeforces.com/gym/102500 (https://www.acmicpc.net/category/detail/2121)

 

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

 

~0:14

I를 petamingks가 조금 헤멘 후 풀었다. 그 동안 kwoncycle은 F 풀이를 완성하였고, 나는 A~D를 모두 읽었으나 바로 풀 수 있는 문제가 없어 당황하였다.

 

~0:20

kwoncycle이 F를 맞았다. 이후 C를 petamingks에게 넘긴 후 A를 보러 갔다.

 

~0:31

kwoncycle은 F 이후 E로 넘어갔고, 1번 틀리긴 했지만 빠르게 맞았다. 이후 수학 문제인 G를 보러 갔다.

 

~0:49

이후 petamingks 역시 C를 한번 틀린 후 맞았다. 나는 이동안 A 풀이를 어떻게든 내기 위해 노력했다. 우선 사람과 순위를 곧바로 연결시키면 변화 횟수의 합이 $O(Nw)$라 불가능하다. 대신, 사람-점수와 점수-순위간의 변화 관계는 $O(T)$번이기 때문에 저장할 수 있다는 사실을 깨달았다. ($T$는 점수의 총합) 이걸 잘 저장해서 누적합을 만든 후 이분 탐색을 하면 될 것 같았다. 다만 구현량이 길었기에 G 이후에 짜기로 한 후 D를 잠깐 봤다.

 

~1:03

kwoncycle이 G를 한 번에 맞았다. 난 A 코딩에 들어갔고, kwoncycle과 petamingks는 각각 H와 J를 보러 떠났다.

 

~1:41

쉽지 않은 구현 끝에 A 예제가 나왔고, 코드가 복잡해서 틀리면 상당히 막막할 것 같아 걱정했지만 다행히 1번에 맞았다. kwoncycle이 H 풀이를 찾았다고 해 컴퓨터를 넘겼고, 나는 A를 짜면서 petamingks와 D 풀이에 대한 느낌을 대충 잡았기에 마무리 후 짜기로 했다.

 

~3:08

AC가 나온 시간은 아니지만 이 때까지의 경과를 살펴보자면
H - 2번 틀린 후 풀이 오류를 발견해 재구상 돌입

D - 풀이를 찾았지만 구현 후 WA

J - petamingks가 풀이를 찾았고, 내가 짜려 했으나 D가 틀려버려 petamingks가 짜는 것으로 함

우선 petamingks의 J가 컴퓨터를 잡고, 남은 둘은 풀이 오류를 찾는데에 집중했다.

 

~3:50

이때쯤 H는 다시 짰으나 WA on test 4에 갇혀버렸고, 나 역시 D의 명백한 오류를 찾았으나 WA on test 33에 걸렸다. 이후 역추적을 더 확실하게 하는 법을 찾아 냈지만, 63번에서 다시 틀리고 하나의 오류를 더 찾은 후에야 AC를 받을 수 있었다. 이후에는 할 수 있는 게 없었기에 C++에 익숙하지 않은 petamingks의 J 코딩을 도왔다.

 

~4:41

J와 H를 번갈아서 여러번 틀리다 J에서 먼저 AC를 볼 수 있었다.

 

~5:00

나는 J 코딩이 마무리되는듯 해 H를 도우러 갔다. H 풀이와 코드를 확인해 본 결과 1) 실수 출력 문제인데 setprecision이 없음 2) 풀이에 약간 모자란 부분이 있음 과 같은 2가지 오류를 발견하였다. 시간이 조금 남아 있었기에 이를 고치기로 했다. 여기서 원격 팀연습이기에 가능했던 참사가 발생하는데..

 

- 타임라인 -

setprecision 오류를 찾음 -> 이를 고쳐서 제출하나 WA

풀이 오류를 찾음 -> 이를 고쳐서 제출하나 WA

결과적으로 둘 모두 고친 코드가 없음 (?) -> 대회 종료 5분 후 모두 고쳐서 내니 AC

 

대면이었다면 컴퓨터 화면을 계속 보고 있었을 거라 아마 훨씬 일찍 맞았을 것 같다.

 

문제별 요약

A (P2, solved by leo020630) : 점수와 연결짓는다는 생각을 하면 풀이에 도달하기 쉽다. 나는 세그에 굉장히 복잡한 누적합에 이것저것 써서 구현이 복잡했는데 쉬운 풀이는 10분만에 짤 수 있을 정도로 간단한 것 같다. 실제로 10분만에 푼 팀들이 있어서 좀 쫄았다.

B (D1, Not solved) : petamingks가 읽었는데 어렵다고 한다.

C (G3, solved by petamingks) : 그리디 문제다. 바로 안 떠올라서 petamingks한테 넘겼는데 잘 풀어주었다.

D (D5, solved by leo020630, petamingks) : 우선 모든 간선에 $v$를 곱하면 간선에 더하는 변수를 1개($x$)로 줄일 수 있다. 이러면 DP를 통해 간선을 $a$개 써서 정점 $v$에 도달했을 때의 가중치 합의 최솟값 $b=dp[a][v]$를 구할 수 있다. 이제 $ax+b$꼴의 직선이 여러 개 있는 것으로 생각할 수 있는데, 우선 CHT에서 하는 것처럼 좋은 직선들만 남겨주는 것이 최적임은 자명하니 진행해주자. 또한 이때 $0 \leq x$인 곳에서 유효한 직선만 남겨야 한다. 이제 역추적을 해야 하는데, 나는 처음에 직선들이 구분되는 $x$를 직접 구해서 다익스트라를 $N$번 돌리는 풀이를 고안하였다. 다만 이 풀이가 정확하게 동작할 것이라는 보장이 없어서 (이것 때문은 아니었지만 1번 틀리기도 했고) 다른 방법을 찾아보았다. 유효한 직선들을 남겼으면, 이 $a$들에 대해 $dp[a][N]$들을 멀티 소스로 하는 BFS 비슷한 것을 돌려주어서 꼭 지나야 하는 정점을 체크해줄 수 있다. 좀 힘들게 풀긴 했지만 좋은 문제라고 생각했다.

E (S3, solved by kwoncycle) : 간단한 수학 문제 같았다.

F (G2, solved by kwoncycle) : Union Find 잘 쓰면 된다고 한다.

G (P5, solved by kwoncycle) : 확률 문제라고 한다.

H (D4, upsolved? by kwoncycle) : 풀이를 잘 냈지만 억까로 결국 대회 시간 내에는 풀지 못했다. 그래도 실전에서 겪지 않아서 다행이다. 풀이 난이도는 D4치고 쉽다고 한다. 

I (S1, solved by petamingks) : 문제를 읽지 않았다.

J (D5, solved by petamingks) : petamingks가 빠르게 풀이를 내었고, C++, 특히 set에 익숙하지 않은데 구현까지 해 풀어주었다. 관찰을 하나 하면 set으로 덩어리 여러개를 관리하는 유형으로 생각할 수 있다.

K (D2, Not solved) : 문제를 읽지 않았다. 어렵다고 한다.

 

 

느낀 점 + 피드백

우리 팀의 멤버 구성상 내가 쉬운 부분을 잡는 것이 효율적이라고 생각했는데, 내가 어려운 부분을 잡아서 초반에 기여를 거의 하지 못했는데도 스퍼트가 나쁘지 않아서 놀랐다.

 

한 명이 심하게 말렸는데도 남은 둘이 어떻게든 다이아 문제를 하나씩 풀어서 결과가 좋았던 것 같다.

 

말렸어도 제출을 신중히 하자..? but 쉽지 않음

 

 

+팀연습 같이 하실 팀 좋아요