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 쉽지 않음

 

 

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