240204 팀 연습 (World Final 2018)

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

 

셋 : https://codeforces.com/gym/102482 (https://www.acmicpc.net/category/detail/1859)

 

 

이 때 한국 WF 참가 팀 성적은

서울대 molamola - 7/719 (5등)

KAIST Deobureo Minkyu Party - 6/867 (20등)

UNIST MDMA - 5/962 (49등)

이었다. 

 

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

 

~1:13

월파셋 답게 바로 풀 수 있는 문제 따위는 없었다. petamingks는 A, B를 읽은 후 A는 그래프 DP, B는 구현이라는 이유로 각각 나와 kwoncycle에게 문제를 넘기고 본인은 물리 문제인 E를 처음부터 잡았다. 나는 F를 좀 보다 풀이가 나온 것 같아서 kwoncycle이 B를 짜는 동안 A 풀이를 고민해보았다. DP를 밑에서부터 돌리려 하니 식이 잘 나오지 않아 거꾸로 생각해 보았더니 되는 것 같아 D 코딩이 끝날 때까지 기다렸다. kwoncycle이 1시간쯤 걸려 D 구현을 끝냈고, 다행히 1번에 맞을 수 있었다. 

 

~2:04

F, A를 차례로 짜 모두 맞았다. A는 답지 않게 int를 써서 1번 틀렸다. 이후 petamingks의 E와 kwoncycle의 K 풀이가 모두 나왔고, 코딩이 짧은 K 먼저 잡기로 했다. 나는 H, I를 한 번씩 훑은 후 I를 보기로 했다.

 

~2:28

kwoncycle이 K를 1번에 맞았고, 컴퓨터는 E로 넘어갔다.

 

~3:05

petamingks가 E를 1번 틀리고 맞았다. 이는 무려 본대회+virtual 통틀어서 퍼솔이었다. 그 사이 kwoncycle의 H와 내 I 풀이가 모두 완성되었고, I는 손코딩을 좀 하고 들어가는 것이 좋아보여서 H에게 컴퓨터를 먼저 넘겼다.

 

~3:52

I를 위한 전초 작업이 끝난 후, kwoncycle의 H 코딩이 빠르게 끝나지 않을 것 같아 컴퓨터를 뺏어서 짜기 시작했다. 역방향 삼각형을 생각하지 않아 잠시 컴퓨터를 넘기는 일이 있었지만 손코딩 덕에 빠르게 완성할 수 있었고, 제출을 했으나 5분 넘게 채점이 되지 않았다. 이를 확인하고자 제출도 1번 더 하고, 대회 도중 백준에 내는 추태를 부리기도 했다. 아무튼 맞은 것을 확인한 이후 H로 다시 컴퓨터를 넘겼다. 

 

~5:00

kwoncycle이 고통스러워 하며 H 코딩을 이어나갔으나 안타깝게도 마무리하지 못했다. 나와 petamingks는 더 풀 수 있는 문제가 없었기에 그냥 있었는데, 대면이었다면 어떻게든 도움을 줬어야 했을 것 같다.

 

문제별 요약

A (P2, solved by leo020630) : DAG가 아니지만 버스의 출발 시간대로 정렬하면 마치 DAG같이 DP를 할 수 있다. 여기서 중요한 것은 DP 정의인데, (여기까지 도착하기 위한 확률)로 세우면 식이 어렵고 뒤집어서 생각해 (여기서 출발해 얻을 수 있는 최대 확률) 로 정의하면 비교적 쉽게 나온다.

B (P4, solved by kwoncycle) : 구현이 더러운 문제라고 한다.

C (R3, Not solved) : 이 문제 상위호환 느낌이 났다. 당연히 손대지는 못했다.

D (R5, Not solved) : petamingks가 알던 문제라고 한다. 어차피 스코어보드를 보고 손대지 않았을 거라 큰 의미는 없다.

E (D3, solved by petamingks) : 복잡한 물리 문제라고 한다. 시작부터 잡더니 잘 풀어주었다. 

F (P4, solved by leo020630) : width로 가능한 경우가 \(O(80N)\) 정도이고, 각 단계에서 DP를 \(O(N)\)에 해결할 수 있다.

G (R5, Not solved) : 그림 보고 걸렀다. 보로노이 같은 것을 사용하면 된다고 한다.

H (D4, Not solved) : X자로 그으면 항상 가능하므로 답이 1 혹은 2인데, 우리 팀은 1 판별을 상당히 복잡하게 생각해서 시간 내에 짜지 못했다. 솔브 수를 보면 아마 짜기 쉬운 풀이도 존재하는 것 같다.

I (D4, solved by leo020630) : 예제를 애써 무시한 채 풀이에만 집중하면 웰노운 세그 스위핑으로 해결할 수 있다. 풀이 자체 난이도는 P1~2라고 생각한다. 다만 입력이 아래와 같이 주어지는 까닭에 코딩이 좀 오래 걸렸다.

J (R1, Not solved) : 어디서 많이 들어본 문제다. 당연히 거들떠도 보지 않았다. 

K (P4, solved by kwoncycle) : 문제를 제대로 읽지 않았다.

 

 

느낀 점 + 피드백

월파 문제는 더럽다.

 

우리 팀이 풀이는 참 잘 내는데, 나는 잘 틀리고 나머지는 코딩이 약간 느린 듯 하다. 코딩 연습을 열심히 하자.

 

대회장 가서는 코딩 끝났다고 놀지 말고 뭐라도 하자.

 

연습을 열심히 하자. 

 

+팀연습 같이 하실 팀 연락주세요