2021 ICPC Shanghai Site 연습

두번째 팀 연습

  • 시간: 2021-03-17 13:15 ~ 18:15
  • 장소: 안산 랭스터디 카페

오늘은 날을 잡아서 5시간짜리 셋을 돌기로 하였다.

대회는 2020 ICPC Shanghai Site로 정했다.

확실히 저번보다는 어려웠다. 퍼포먼스도 사실 남들한테 보여주기 부끄러울정도다.

연습 타임 라인

13:15 ~ 13:24

G번이 제일 먼저 많이 풀려있는걸 보고 Lemonade255가 G를 읽고 바로 짰다. 끝나고 보니깐 그렇게 어려운 문제는 아닌것 같고 한번에 잘 풀었다.

13:24 G solve

~ 13:35

나는 시작하자마자 B를 읽었는데 문제는 읽고 constructive 하다고 생각이 들었다. 일단 직관적으로 -1을 출력하는 경우는 없을거라 판단했다.

dtc03012님이 이제 절반만 바꾸는 거니깐 홀수줄/짝수줄은 그대로 두고 한쪽 줄만 바꾸는걸로 만들어보자고 했다. 뭔가 될것 같기도한데 잘 안되었다.

Lemonade255가 “그냥 A로 만들던가 A의 반전으로 만드는걸 시도 해보면 된다.” 얘기했고 들어보니 맞는말이어서 바로 짜서 맞추었다.

B solve

~ 14:17

dtc03012님이 M번을 읽고, 나는 D번, Lemonade는 C번을 읽었다. dtc03012님이 해석을 도와달라 해서 gitignore 를 원래 써본 나는 실제 동작이랑 얘기하면서 설명해주고 그냥 dfs 돌리면 된다고 얘기했다.

근데 RTE를 계속 내었다. 간단한문제라고 생각했는데 뭔가 고생을 하고 계셨다. RTE면 막 사이클을 돌아야하는데 A폴더가 B폴더를 참조하고 B폴더가 A폴더를 참조하는 경우는 있을수 없으니 의문이었다.

~ 14:39

D번은 삼분 탐색으로 쉽게 될 것 같아서 내가 짜서 제출을 해봤는데 틀렸다.

~ 15:03

M번도 수정하고 D번도 수정을 하는 작업을 했다. 나는 D번을 보고 있었는데 처음엔 삼분탐색을 잘못짰거나 정확도 문제인가 의심을 했는데 코드를 열심히봐도 딱히 그런부분이 없었다.

D번은 dtc03012님이 p1, p2가 서로의 방향으로 쭉가는게 최선이 될수도 있다 해서 그걸 넣었더니 맞았다.

D 4번 틀리고 Solve

~ 16:13

M이 왜틀렸는지도 알아냈다. 경로가 unique 하지 파일 이름 자체는 unique하지 않을 수 있다는 거다. 내가 해석해서 설명을 할때 파일 이름이 다 unique하다고 얘기했는데 나의 의도는 실제 OS처럼 path가 unique(같은 경로내에 같은 파일이 없다)한걸 얘기한거였고(그냥 원래 폴더/파일 구조가 그러니깐) dtc03012님은 어떤곳에서도 디렉토리나 파일 이름이 unique하다고 생각하고 코딩을 한거였다.

M번도 그냥 이제 너무 많이 틀리다보니깐 새로 짜는게 낫다 판단해서 내가 새로 짜기로 했다. 근데 확실히 생각보다 이게 정확하고 빠르게 짜기가 쉽지 않았다. 알고리즘 자체는 딱히 뭐 없는데 구현이 나도 힘들었다.

그래도 어떻게 느리긴하지만 짜긴해서 M을 풀었다.

M 8번 틀리고 Solve

~ 17:03

내가 M을 짜고 있는 사이 E,H,C,I의 풀이를 준비했다고 했다.

E는 dtc03012님이 DP식을 만들었는데 시간이 조금 애매할것 같다 얘기했다. H는 그냥 이분탐색 + 이분매칭하면 된다 했고.

C,I는 수학적인 문제라서 Lemonade255가 짤 수 있다고 했다. 중간 중간 코딩을 하는데 뭔가 잘 안되어서 다시 노트를 들고 정리했다.

dtc03012님이 E를 짰는데 시간 초과가 났다.

~ 17:55

나는 이미 풀이를 다 준비했다고 해서 코딩이라도 해야지 하고 H번을 이제 옛날에 풀었던 범죄 파티라는 문제가 생각나서 그것처럼 코딩을 했다.

근데 틀렸다고 나왔다.

~ 18:15

다시 디버깅 + 코딩의 시간이 되었다. 얘도 이분탐색이나 이분매칭(호프크로프트-카프)에서 잘못된 부분이 있나 찾아봤는데 없어서 그래프를 만드는 부분이 조금 이상한것 같아서 그부분을 수정했고, dtc03012님은 E번을 좀 더 빠르게 돌릴 생각을 하고 있었다. Lemonade255는 C번 식을 다시 정리하고 있었다.

H번 의심 가는 부분을 다 수정하고 dtc03012님이 짜보기도 했는데도 안되길래 이제는 알고리즘이 틀렸나 의심이 갔다. 그리고 의심하자 마자 반례가 떠올랐다. 그걸 얘기했고 풀이도 완전 이쪽 방향이 아니고 그냥 $O(K^2)$으로 풀수 있는 풀이 스케치가 떠올랐지만 너무 늦은 시간이었다.

그렇게 대회가 종료되었다.

이후

18:31분에 dtc03012님이 E번을 시간 줄여서 맞췄다.

결과

555페널티 4솔브로 275등이다. C,I의 진행상황은 잘 모르지만 E, H는 맞추고 6솔은 했어야 했다.

H번은 나도 바로 의심없이 코딩하지말고 풀이가 맞는지 검증을 거쳤어야 했다.

M번이 시간을 많이 먹었는데 그걸 생각하더라도 후반 퍼포먼스가 너무 안좋았다.

그래서 다음 연습에서는 그냥 따로따로 문제 읽고 풀지 말고 무조건 3명이서 같이 한문제씩만 보고 코딩하는 걸로 정했다. 아마 이러면 좀 더 잘 풀 수 있지 않을까 생각한다.

미래의 팀연습

아마 앞으로도 5시간 셋을 돌 것 같다. 장소는 팀원이 살고 있는 왕십리-안산-인천을 한번씩 번갈아가면서 모일것 같다. 2주에 한번 정도 모여서 다음번 모임은 3/31 예정