나는코더다 2023 송년대회

2023년 12월 26일에 진행한 나는코더다 송년대회 후기입니다.

23. 12. 14. 팀 결정

• 작년에 junwoojune, yuseok0803과 팀을 이뤄 나갔었는데, yuseok0803이 PS를 접었습니다. 그래서 junwoojune을 만날 때마다 ‘팀원 누구함?’만 얘기했습니다.
• 영입 후보로는 iccodly나 yty2589, juwonhyme 등이 있었는데, iccodly는 개인 팀(존경…)으로 출전하기로 했고 나머지는 이미 팀이 있어서, 그냥 2인 팀으로 나가기로 했습니다.
• (Muzi being cute가 junwoojune입니다.) 그냥 별 생각 없이 2인팀을 하기로 했습니다.
• 그리고 팀명을 고르려 했습니다. 저는 ‘1인팀’, junwoojune은 ‘구뇌’를 제안했고 ‘구뇌’로 하기로 했습니다.
  • TMI: 팀명의 유래는 고입 학원입니다.

연습

• 송년대회는 그 해의 출제자들이 꼴리는 문제를 다 뱉어내는 대회이기 때문에 출제 경향 따위가 존재하지 않습니다.
• 와중에 모 출제자가 정보를 흘려주었습니다.
• 딱히 풀어볼 셋이 없어서, 출제자 4명이 역대 출제한 모든 문제를 모아 문제집으로 만들었습니다. 18문제가 되었는데, 셋 하나로 돌기엔 많고 둘로 쪼개기엔 적은 것 같았습니다. 그래서 12개를 랜덤으로 골라 셋으로 만들고 나머지 6개는 그냥 풀어보기로 했습니다.

23. 12. 21.

• 18개 중 언레 문제 하나를 제외하고 17개를 풀기로 했습니다. 17개를 다 풀고 들어갈 리 없어서, 7개는 같이 풀고 5개씩 각자 풀어보기로 했습니다.
• 같이 셋을 하나 돌 생각을 했습니다. UCPC 2020년도 셋을 잡았습니다. 작년 송년이랑 난이도는 대강 비슷했던 것 같습니다.

23. 12. 24

• UCPC 2020년도 셋을 두시간 좀 넘게 잡았습니다. 시간은 대충대충 잡았습니다.

  0:00~0:25

• 랜덤 정렬해서, 앞 6개를 제가 잡고 뒤 5개를 junwoojune이 잡았습니다.
• 문제를 읽고 태그를 정리하고 풀 만한 문제를 가려냈습니다.

  0:25~0:55

• 앞부분 문제는 다 어려웠습니다.
• 뒷부분 문제 중 던전 지도 문제 지문이 이해가 안 간다고 해서 읽어보았습니다.
• 생각보다 쉽게 풀릴 것 같아 잡았고 풀었습니다.
• 얼마 지나지 않아 junwoojune이 전단지 돌리기 문제를 풀었습니다.

  0:50~1:20

• 빛의 전사 크리퓨어 문제를 잡았습니다.
• 순환구간을 클리크로 나누는 문제였습니다.
• 스파스질을 해야 할 것 같다는 감상을 junwoojune에게 남기고 넘어갔습니다.

  1:20~2:00

• 피자 배틀 문제를 잡았습니다.
• 그냥 매우 큰 크기의 DP로 풀릴 것 같았습니다. 크기 2억짜리의 DP를 짰습니다.
• 디버깅을 20분 정도 했습니다. 맞았습니다.

  2:00~2:30

• 코포를 하기 위해 2시간 30분째에 끊기로 했습니다.
• junwoojune이 소가 길을 건너간 이유 2020이 CHT일 거라는 감상을 남겨서 봤습니다.
• 쩌는 발상을 하나 했습니다.
• 이걸 junwoojune에게 이야기했더니 junwoojune이 풀이를 만들어냈습니다.
• 풀 시간은 안 되어서 여기서 끝냈습니다.

  복기

• 생각보다 태그 예상은 잘해낸 것 같습니다. 특히 크리퓨어 문제가 스파스일 것이라는 생각은 잘 한 것 같습니다.
• 알고 보니 12개 중 한 문제(함수 복원)를 안 넣었습니다. 플레 5의 조합론 그래프 문제였는데, 제가 조합론과 그래프에 조예가 있어서 저든 junwoojune이든 풀 수 있지 않았을까 싶습니다.
• 여기서 junwoojune이 남은 두시간 정도를 그건 망고가 아니라 고양이에요 문제에 쏟고, 제가 함수 복원을 풀어냈다면 6개, 거기에 제가 크리퓨어를 잡아서 풀어났다면 최대 7개까지 풀어낼 수 있었을 것 같습니다. 하면 5~7솔 정도로 끝났겠습니다.
• 나름 잘한 것 같습니다.

21. 12. 25

• 팀노트를 만들었습니다.
• 이것의 팀노트들을 많이 참고했고, 그중 더불어민규당 팀노트를 템플릿으로 사용했습니다.
• 자구 섹션: 다이나믹 세그, 리차오, PST를 넣었습니다. junwoojune이 세그를 잘 쓰기 때문에 이 섹션은 대부분 junwoojune의 코드를 넣었습니다.
• 플로우 섹션: 이분 매칭(호프크로프트 카프), 디닉 최대유량, MCMF를 넣었습니다. 둘 다 플로우를 못 쓰기 때문에, koosaga code library와 jh05013님 블로그를 참고했습니다.
• 그래프: 다익, 센트로이드, 2-SAT, BCC, 스플레이/링컷, HLD, 오프라인 다이나믹 MST를 넣었습니다. 대부분 민규당 팀노트의 내용을 그대로 사용했고, 거기에 센트나 2샛, HLD 같은 것은 직접 추가했습니다.
• 문자열: KMP, 아호-코라식, 접미사 배열, 매내처를 넣었습니다. 이 정도를 넣긴 했지만 솔직히 문자열이 나오면 맞출 자신은 없습니다.
• 기하: 반평면 교집합과 PIP를 넣었고 거기에 일반적인 CHT를 하나 추가했습니다. CHT는 junwoojune이 추가했고, 나머지는 그대로 두었습니다.
• 수학: FFT/NTT, 가우스 소거, 밀러라빈 및 폴라드로, 약수 많은 수와 소수 리스트를 넣었습니다. 모두 원래 있던 것들입니다.
• 기타: 잡다한 수학 공식, 빠른 정수 입출력, 스택핵 등을 넣었습니다. 원래 있던 것에 앳코더 라이브러리의 CRT만 추가했습니다.
• 여기에 더해, ‘헤더’라는 이름으로 mt19937, 프라그마 명령어, 연산자 오버로딩, 커스텀 해시, 거듭제곱 로그시간, 조합/중복조합, ccw 등을 추가했습니다.

대회

• Open Contest가 끝나는 1월 6일 이후에 업로드합니다.