Post

나는코더다 2024 송년대회 개최 및 운영 후기

Posted Updated
By
67 min read
나는코더다 2024 송년대회 개최 및 운영 후기

2024년 12월 26일에 본대회, 2025년 1월 4일에 오픈을 진행한 나는코더다 2024 송년대회를 개최 및 운영했습니다. 조금 늦었지만 후기를 작성합니다.

이번에는 반년대회 때처럼 열심히 글을 정리해서 쓸 자신도 시간도 의지도 없어서, 생각나는 이야기를 두서 없이 아무거나 던질 생각입니다.

문제 선정 이야기

  • 반년대회를 8월 말에 마치기 이전부터 송년에 출제할 문제를 많이 만들어둔 상태였습니다.

Problemset: 2408xx

  • 촛불과 그림자 2
    • ehlee0815가 출제한, 2023년도 1학기에 만들어진 기하 문제입니다. 촛불과 그림자보다는 비교적 쉬운 문제라고 합니다만, 저는 검수하지 않았습니다.
  • 그래프 곱셈
    • 제가 출제한, 2023년도 여름방학 때 만들어진 그래프 문제입니다.
    • 당시 미시건 대학교의 여름 캠프에 참가했고(블로그에서 내용을 찾아보실 수 있습니다), 강의 중에 그래프 간 적연산 몇 가지를 공부했습니다.
    • 이걸 기반으로 개학 무렵에 문제를 만들었습니다. 이 정도면 ‘골드 상위의, 송년대회 난이도 셋의 가장 쉬운 문제로 적당한 난이도’ 문제라고 생각했습니다.
    • 원래 섭테 문제로 내려고 했습니다.
  • 나는 애니메이션에 열정적인 사람이 아니야
    • ehlee0815가 출제한, 2023년 언젠가에 만들어진 문제입니다.
      • 이걸 알고 있는 이유는, 2024년 1월에 ‘송년 문제 아이디어 리스트’를 한번 정리했는데, 그때 이 문제가 있었습니다.
      • ehlee가 자신의 블로그에 적은 내용보다는 훨씬 오래됐습니다.
    • 원래 pbs를 의도했는데, 세그 셋질로 풀려서 이게 정해가 되었습니다. 어쨌든 좋은 문제인 것 같습니다.
  • (비공개 A)
    • ehlee0815가 출제하려고 했던, 2023 입부시험에 긴급 출제를 목표로 만들었다가 취소한 문제입니다.
    • 그래서 송년으로 가져오려고 했는데, 막판에 출제하지 않기로 했습니다.
  • 정기 모임 6
    • 송년대회에는 정기 모임을 내야 합니다. denniskim이 기장임에도 낸 문제가 없었기에 정기모임을 내겠다 선언했고, 12월이 되어서야 문제 구체화가 진행되었습니다.
  • (비공개 B)
    • gs22123이 출제하려고 했던, 2024년 2월 혹은 그 이전에 만들어진 문제입니다.
    • 세팅하기 너무 어려울 것으로 보여 출제를 포기했(던 것으로 알고 있)습니다.
  • 폭죽놀이
    • iccodly가 출제한, 2024년 3월 혹은 그 이전에 만들어진 문제입니다.
    • 너무 어렵거나 웰논이 아닐까 싶어서 난이도를 올리고자 하는 논의가 있었던 것으로 기억합니다.
    • 8월 중에 현재와 같이 문제가 구체화되었습니다.
  • 수열과 수열
    • 제가 출제한, 2024년 3월에 만들어진 문제입니다.
    • 당시 생각했던 솔루션은 지금보다 더 적은 연산을 사용하나 더 어렵습니다.
    • 이 솔루션을 생각만 해두고 증명하지 않았다가, 8월에 아이디어를 선정하면서 출제를 위해 증명했습니다.
  • 매우 간단한 문제
    • ehlee가 수학 시간에 만들었던 문제를 기반으로 한 문제입니다. 수학 버전의 문제는 2023년 2학기에 만들어졌습니다.
    • 쌩수학 문제가 하나쯤 있으면 좋겠다고 생각해서 2024년 중에 PS 문제로 바꾸어 출제하기로 했습니다.
  • 여기에 몇 문제를 추가해서, 9월 30일에 1차로 출제할 문제를 확정합니다.

Problemset: 240930

  • 위에 언급한 9문제
  • (비공개 C)
    • gs22123이 9월 말에 출제한, 논문에서 영감을 받은 어려운 문제입니다.
    • 높은 퀄리티의 좋은 문제라고 생각하나, 출제하기 너무 어려울 것 같아서 10월 중으로 포기했습니다.
  • 트리를 안 쓰는 트리 문제
    • 문제 셋을 확정하기 위해, 그리고 PS 실력이 높지 않음에도 수학적 지식과 능지가 좋은 경곽 학생들을 위해 애드혹을 내고 싶어서, 제가 9월 30일 자습시간에 출제했던 문제입니다.
    • 솔직히 마음에 드는 문제는 아닙니다, 이 얘기는 아래에서 하겠습니다.
  • (비공개 D)
    • 비슷한 목적으로, 쉽고 많이 풀릴만한 골드를 내기 위해서 gs22123이 9월 30일 자습시간에 출제했던 문제입니다.
    • 결국 출제되지 못한 이유는 10월에 등장한 <시설물 사용 신청> 문제가 더 좋(다고 gs22123이 주장했)기 때문입니다.
  • 의도 난이도를 기반으로 난이도커브를 그렸고, 다음과 같이 예측했습니다:
    • 22년도 송년대회와 난이도가 비슷
    • ICPC APAC보다 어렵고, ICPC WF보다 비슷하거나 조금 쉬운 수준
  • 10월 말일까지 문제 확정과 세팅 1차 완료를 목표로 잡았습니다. 그리고 그 뒤로 몇 가지 변화가 일어납니다.
  • 10월 5일, 제가 <유한평면 색칠하기> 문제를 출제합니다.
    • 모 IMO SL 문제에서 영감을 받아 제가 제시했던 문제입니다.
    • 다만 문제를 구체화하지 못해서 출제를 포기합니다.
    • 상술한 ehlee의 블로그에서 이 문제를 확인할 수 있습니다.
  • 10월 10일, 제가 <시설물 사용 신청> 문제를 출제합니다.
    • 어쩌다가 발상해낸 문제입니다. R&E 등에서 주구장창 써먹은 구간 그래프를 쓰는 문제입니다.
    • 이 문제 역시 마음에 드는 문제는 아닙니다.
  • 10월 중, <시설물 사용 신청> 문제가 비공개 D 문제와 태그나 난이도 등이 유사하나 <시설물 사용 신청>이 더 좋다고 판단하여, 비공개 D 문제를 삭제하고 <시설물 사용 신청> 문제를 셋에 추가합니다.
  • 10월 17일, gs22123이 <강 건너기> 문제를 출제합니다.
    • 어떻게 출제되었는지 구체적으로는 까먹었습니다.
    • 비공개 C 문제의 출제를 포기함에 따라 대체 문제로 출제했습니다.
  • 이렇게 해서 문제셋이 다음과 같이 변경됩니다.

Problemset: 241019

  • Problemset 2408xx의 9개 문제
  • Problemset 240930의 트리를 안 쓰는 트리 문제
  • 시설물 사용 신청
  • 강 건너기
  • 당연히 10월 말일까지 세팅이 끝나지 않았습니다. 연말의 고3은 일반적으로 한가하지는 않습니다만 경곽인이면 이때가 가장 한가한 게 정상이긴 합니다.
  • 그렇게 11월이 됩니다. 11월은 수능과 대학별고사가 있기 때문에 학기 내내 뭐가 많았습니다. 디스코드를 삭제한 기장을 비롯해 대부분의 친구들이 비는 시간이 없게 되었습니다.
  • 11월 중순을 근처로 제 문제들을 세팅했고, 그 외의 문제는 대부분 세팅되지 않았었던 걸로 기억합니다.
    • 저는 수능 전후로 매우 한가했습니다. 그 이유는 조금 슬픈 이야기입니다, 제 2024년 회고글을 참고하시면 되겠습니다.
  • 11월 20일, 검수진 모집을 완료하고 검수진을 디스코드에 초대합니다. 정확히는 기억나지 않으나 4~6개 정도 문제가 세팅되지 않은 상태였습니다.
  • 11월 중, 비공개 A 문제의 출제를 포기합니다.
    • 정확한 이유는 잘 모르겠습니다.
    • 작년 운영진이기도 했던 검수진의 ‘되도록 난이도를 낮추는 것이 좋다’는 조언에 따라 실버 문제를 목표로 새로운 문제를 출제하고자 합니다.
  • 11월 중, 비공개 B 문제의 출제를 포기합니다.
    • 세팅 난이도가 높아 포기한 것으로 기억합니다.
    • 높은 난이도의 문제의 부재로, 다이아 상위 혹은 루비 하위를 목표로 출제하기로 합니다.
      • 정기 모임 6 문제가 구체화되어있지 않았고, 다이아를 예상했었습니다. 수열과 수열 역시 제가 다이아 중위를 주장한 것 외에 예상 난이도가 없었기에, 최고 난이도 문제를 목표로 출제하게 됩니다.
  • 11월 27일, ehlee0815가 <데이브의 고민> 문제를 출제합니다.
    • <유한평면 색칠하기> 문제를 출제하고 나서 나온 논의에서 영감을 받아 출제되었습니다.
    • 제가 세팅하기로 했고, 당일 저녁에 빠르게 세팅을 완료합니다.
  • 같은 날, gs22123과 ehlee0815가 루비 문제를 만들어 오기로 합니다. 논문에서 영감을 받은 문제 두 개가 후보로 있었습니다.
  • 12월 1일을 전후로, gs22123이 제시했던 두 후보 중 하나인 <지하철 타고 가요> 문제를 출제하기로 결정합니다.
    • 원래는 세제곱이 통과하지 않는 것이 정해이고, 이때의 난이도는 다이아 상위 내외였습니다.
    • 이 제곱로그 솔루션이 꽤나 재밌습니다. 때문에 좋은 문제라 생각했습니다.
  • 12월 9일에 <정기 모임 6> 문제의 세팅이 완료되며 모든 문제가 출제되었습니다.
    • 무려 정해가 13000바이트입니다.
    • gs22006이 매우 고생하면서 세팅했습니다. 존경스럽습니다.

출제된 문제 이야기

  • 문제 번호로 구분했지만, 그냥 아무 얘기나 생각나는 대로 할 겁니다.

A. 촛불과 그림자 2

  • 첫 문제부터 무시무시하게 생긴 기하 문제를 배치해서 정말 죄송합니다.
  • 문제 배치는 전적으로 제가 담당했습니다. 문제 배치는 두 개의 목표를 잡고 진행했습니다:
    • 쉬운 문제를 제시하거나 특정 문제 퍼솔상 배치 등, 문제를 푸는 순서를 제시하는 모든 요소를 삭제
      • ICPC식 팀 대회의 묘미이자 요구되는 능력 중 하나가 쉬운 문제를 찾는 과정과 그 실력이라 생각했기 때문입니다.
    • 2인팀이나 3인팀에서 초기에 문제를 분배할 때, 난이도 배치의 균형을 유지
      • 이게 적절하지 않으면 재미가 없어질 수 있다 생각했고,
      • 예년보다 쉬운 문제가 많기에 모든 학생이 한 문제 이상을 잡으면 좋을 것 같았기 때문입니다.
  • 그렇게 하여 A번에 가장 쉬운 문제가 나오는 전통도 깨고 싶었고, A번이 쉬운 문제가 아님을 확실히 하기 위해 딱 봐도 어려워 보이는 기하를 배치했습니다.
  • 그 외에도 제일 일찍 출제됐다는 점도 있고요.
  • 저는 이 문제를 검수하지 않았기에 솔루션도 모릅니다. 그러나 좋은 문제라고 들었습니다.

B. 그래프 곱셈

  • 제가 낸 문제 중 가장 오래된 문제이고, 그만큼 가장 확실하게 구체된 문제이기도 했습니다.
  • 처음 출제할 때는 골드 중상위를 생각했지만, junwoojune과 gs22123이 플5를 주장했고, 최종적으로는 플4로 검수되었습니다. 처음 의도대로 이 문제를 가장 쉬운 문제로 두었다면 역대급 불셋이 될 뻔했습니다.
    • 사실 근 2~3년간 대회들이 모두 그 이전 대회들과 비교하면 불셋이었기에, 난이도가 더 높아지는 게 이상하지 않았을 수도 있겠습니다.
    • 그러나 저는 현재의 난이도커브에 대체로 만족하고 있습니다.
  • 예제 2의 반례는 원래 생각하지 못했었습니다. 검수진 대부분도 못 찾았다가 qwwrasdfzxcl이 제시해줘서 감사하게도 정해와 테케를 수정했습니다.
    • 이걸 줄지 말지 고민했는데, 저는 주자고 주장했으나 대부분의 운영/검수진이 주지 말자고 해서 안 주려고 했습니다.
    • 근데, 이 반례의 존재를 모르는 검수진에게 문제를 풀려보았고, 수많은 맞왜틀 이후 결국 못 찾았습니다. 그렇기에 주는 걸로 돌렸습니다.
  • 원래 꽤나 괜찮은 문제라 생각했으나, 이 반례 때문에 약간 재미가 떨어진 것 같아 아쉽습니다.

C. 강 건너기

  • 예상했던 것보다 난이도가 쉽게 찍힌 문제입니다.
  • 구간 그래프로 옮기면 degree에 꽤 큰 제약이 걸립니다. 때문에 대충 생각해서 풀 수 있습니다.
  • 별다른 할 얘기는 없습니다.

D. 시설물 사용 신청

  • 원래는 메모리 제한을 빡세게 걸어 O(N) 공간을 쓸 수 없게 하려고 했습니다. 그렇지 않으면 사실상 일반적인 회의실 배정 문제와 같은 문제가 되기 때문입니다.
  • 그러나 (2~3번째로, 골드 정도의) 쉬운 편의 문제를 의도했음에도 ML을 작게 주면 너무 무서워 보일 것 같았습니다.
  • 하여 찾은 대안으로, 답의 크기가 일정값 안쪽이면 솔루션을 출력하고 그렇지 않으면 답만 출력하게 하는 방법을 사용했습니다.
  • 여전히 회의실 배정으로 답을 찍는 방법이 매우 유효하고, 해당 솔루션이 정해와 비슷하거나 더 쉬운 난이도를 가질 것으로 보이나, 그냥 그렇게라도 해결하라고 놔두기로 했습니다.
  • ML을 줄이지 못해서 아쉽습니다만, 애초에 회의실 배정 문제의 특수한 케이스 하나를 구성하라는 문제라 그렇게 좋은 문제는 아니라고 생각합니다.
  • 그리고 답을 보이는 것에 비해 그냥 해를 찍고 구성하는 것이 쉬워서, 적어도 저는 별로 마음에 안 드는 것 같습니다.

E. 폭죽놀이

  • 좋은 문제라고 생각합니다. 어떻게 만들어진 문제인지는 모르겠지만, 저였으면 이런 문제 못 냈을 것 같습니다.
  • 폭죽이라는 컨셉을 낸 뒤에 넥슨 IP를 붙여서 냈습니다. 왜 여기 붙였는지는 기억이 안 나는데 그냥 폭죽이라는 컨셉이 IP를 붙이기 쉬워서 그랬던 것 같습니다.
  • 플상이라 생각했는데 다5가 박혀 있습니다. 다이아로 예상했던 문제들이 다 플레로 떨어지고 있는 와중에 다행입니다.

F. 나는 애니메이션에 열정적인 사람이 아니야

  • 문제가 생긴 첫 번째 문제입니다. 딱 봐도 제목이 정상적이지 않다는 느낌이 오죠?
  • 원래 제목은 ‘나는 씹덕이 아니야’였습니다. 씹덕이라는 단어가 부정적이기 때문에 제목과 지문을 대회 이후 수정했습니다.
  • 출제자 ehlee가 블로그에 충분히 설명해줘서 저는 검수진으로서의 얘기만 하자면, 저는 솔직히 변명의 여지가 없습니다. 그냥 이 문제를 연초부터 너무 오랫동안 ‘씹덕’이라고 불렀고, 때문에 제목이 문제가 될 것이라는 생각을 하지 못했습니다. 다시 한번 죄송하다는 말씀을 드립니다.
  • 지금의 지문도 ‘애니메이션을 보는 행위는 부끄럽다’는 주제를 가지고 있어서, 피드백받은 내용을 절반밖에 고치지 못했다고 생각합니다. 다만 현재 지문이 백준님이 직접 수정하신 내용이고 이에 대해 출제자도 추가적 변경을 할 것처럼 보이지 않기 때문에, 굳이 제가 수정하라고 이래라저래라 하진 않을 생각입니다.
  • 문제 자체는 괜찮다고 생각합니다. 세그 셋질으로 풀 수 있습니다. 출제자가 얘기한 대로 셋질의 묘미를 배우기 좋은 문제라고 생각합니다.

G. 지하철 타고 가요

  • 문제가 생긴 두 번째 문제입니다. 원래 세제곱이 뚫리지 않을 것이라 생각했는데, 너무 간단하게 뚫려서 본대회 때는 무려 H번에 이어 두 번째로 풀렸습니다.
  • 때문에 오픈 전까지 정해를 많이 최적화하고 제한도 늘려서 통과하기 어렵게 만들었는데, 그럼에도 세제곱으로 풀렸습니다. 아쉽습니다.
  • 저는 검수하지 않았습니다만, 와중에 제너레이터 짜고 세팅하는 걸 도와줘서 출제자로 이름이 들어갔습니다.
  • 다만 정해를 간략하게는 알고 있습니다. 구현하기는 정말 어려울 것 같지만 풀이 자체는 꽤나 예쁩니다.
  • 솔직히 소생 가능성은 없을 것 같습니다. 심드빗셋 박으면 세제곱이 제곱로그보다 더 빠릅니다. 물론 정해에도 심드빗셋을 박으면 되긴 하지만, 저도 차마 그런 걸 내라고 하기는 싫습니다.

H. 데이브의 고민

  • 11월 27일 자습시간에 ehlee가 제시하고 제가 세팅한 문제로, 가장 쉬운 문제였습니다.
  • 위에서 언급한 유한평면 색칠하기 문제가 제대로 만들어지기도 전에 상수 최적화 방안으로 나온 ehlee의 아이디어를 기반으로 만들어졌습니다. 아이디어만 해도 나쁘지 않은 문제가 될 수 있을 것 같다고 생각해서 출제했습니다.
  • 지금 생각해보면, WLOG 몇개 붙이고 일단 그리기 시작해보면 꽤나 쉽게 솔루션이 나오기 때문에 쉬운 문제인 것 같습니다. 실버까지도 갈 만한 것 같은데 어쨌든 지금은 골드입니다.
  • 그러나 꽤나 괜찮은 문제라 생각합니다. D, H, J가 모두 애드혹 구성적 골드인데, 그중에 제일 좋다고 생각합니다.

I. 수열과 수열

  • 문제가 생긴 세 번째 문제입니다. 분명 yuantiji 열심히 써가면서 비슷한 문제가 없는 것을 확인했는데, 코드포스에 사실상 같은 문제가 있다는 것을 대회 종료 후에 발견했습니다.
    • 정해가 제 정해와 다른데, (댓글을 통해) 제 정해가 별해로 제시되어 있었습니다.
  • 여러 검수진들도 칭찬했고 저도 지금까지 만들어본 문제 중에 제일 마음에 드는 문제였기에 좀 아쉽습니다.
  • 예전 정해는 솔직히 말해서 어떻게 하는지 까먹었고요, 지금의 정해는 (코포에 있는 그 문제의 정해보다도) 꽤나 예쁜 것 같습니다. 이 정해를 언제 만들었는지는 잘 모르겠는데, 발상 경로는 대충 이렇습니다.
    1. 어떤 순열에서 disjoint한 pair 여러 개를 뽑아서 모두 swap하는 것이 가능하다면, 그걸 두 번 하면 어떤 순열도 정렬할 수 있다는 것이 well-known입니다.
      • 라고 주장하니까 그딴 게 뭔 웰논이냐 그러더라고요. 코포같은 데에 정렬하는 문제가 나오면 한 번쯤 고려해보는 아이디어 아닌가요?
    2. 길이가 짝수인 순열을 N번의 연산으로 뒤집을 수 있습니다(라는 사실을 발견했습니다). 비슷한 방법으로 홀수 길이 순열도 뒤집을 수 있었습니다.
    3. 어떤 수열을, 인접한 원소 간의 swap만을 통해서, 뒤집는다면 무조건 어떤 두 원소를 잡아도 이 둘이 한 번은 인접하게 됩니다. 따라서, 2의 연산과 인접한 원소간의 swap만을 통해서 1의 연산을 할 수 있습니다.
    4. 따라서, 수열을 두 번 뒤집으면 정렬 역시 가능합니다.
  • 1도 알고 있지 않으면 발상하기 어렵지만, 난이도의 핵심은 2에서 오는 것 같습니다. 1을 사용하기 위해 2가 필요하다는 생각 자체가 어렵기 때문입니다.
  • 때문에 이 문제가 마음에 듭니다. 저는 다이아 중위권 난이도를 예상했으나 루비라네요.
  • 여담으로, 체커를 짜는 것이 상당히 어려웠던 문제입니다. 어쨌든 체커를 짜서 문제를 냈습니다.
  • 체커 구현 방법은 정해와는 관련이 거의 없습니다. 맨 아래, 문제들의 정해 직전에 적어 두었으니 궁금하시면 읽어보세요.

J. 트리가 안 나오는 트리 문제

  • 생각하고 나서 너무 다른 대회에 이미 출제되었을 만하다고 생각했는데, yuantiji 돌려도 안 나오길래 그냥 갖다 냈습니다.
  • D번도 그렇고 이 문제도 그렇고, 증명에 비해 최적값을 찍고 그에 맞게 답을 구성하는 것의 난이도가 너무 쉬워서 별로 좋아하지는 않는 문제입니다.
    • 2N-1의 해를 구성하는 것은 매우 쉽기 때문에, 코포 풀듯이 일단 내보고 바로 맞는 전략이 통합니다.
  • 증명이 꽤나 마음에 들어서 더 아쉽습니다. 사실 다른 증명도 많이 있을 것 같기는 한데, 일단 정해 증명은 근 1년동안 봤던 골드 중에서는 제일 마음에 듭니다.
    • 증명은 맨 밑에 간단하게 적어두겠습니다.
    • 사실 저 증명을 알고 생각하면, 머릿속에서는 훨씬 더 직관적인 설명이 생기거든요? 근데 이게 설명도 못하겠고 엄밀한지도 모르겠습니다.
  • 저는 예제 설명 같은 시각자료를 만들 때 컬러코딩을 해두는 것을 좋아합니다. 근데 이번에 만든 예시 그림은 색이 너무 마음에 들지 않았습니다.
  • 별개로, 지금 생각해보면 색을 쓰는 것이 좋지 않다고 생각해서 (이를테면 흑백 프린터를 사용해야 하는 상황이 생기면 정보 전달이 망합니다) 앞으로는 적어도 지문 쓸 때는 색을 안 쓸 것 같습니다.

K. 매우 간단한 문제

  • 제목처럼, 조합론에 약간의 조예가 있다면 실제로 어렵지 않은 문제입니다. 다만 식정리가 매우 복잡하고 각 식이 계산 시간복잡도와 전처리 시간복잡도를 얼마나 먹는지를 생각하면서 정리해야 하기 때문에 귀찮습니다.
  • 저는 검수할 때 두 시간 넘게 걸려서 풀었습니다. 정해와 달리 정점 기준으로 풀었기 때문에 출제자 ehlee도 제 식이 맞는지 틀린지 AC 전까지 알지 못했습니다.
  • 좋은 PS 문제인지는 잘 모르겠지만 좋은 수학 문제는 맞는 것 같습니다. 대회 참가자가 경곽 학생이기 때문에 출제한 문제라서 - 즉 수학 잘하는 비PS러들도 풀라고 낸 문제라서, 잘 냈다고 생각합니다.
  • 그럼에도 제목은 못 지었습니다.

L. 정기 모임 6

  • 지금까지 출제된 정기 모임 중 압도적으로 가장 어려운 문제이자, 제일 마지막으로 세팅된 문제이자, 정해가 13000B로 가장 긴 문제이자, 이번 셋에서 제일 어려운 문제이자, 기장이 낸 유일한 문제입니다.
  • 그리고 저는 풀어본 적도 없고 정해도 모릅니다.
  • 문제에 대해서는 잘 모르겠기에 할 얘기는 없고, 만 바이트가 넘어가는 정해와 수천 바이트를 넘나드는 각종 시간복잡도의 해를 짜고 디버깅하며 고생한 기장 denniskim에게 수고했다는 말만 하고 지나가겠습니다.
    • 대학교 가서는… 세팅은 미리미리 하세요…

본대회 이야기

  • 반년대회 때처럼 본교 본관 강당에서 대회를 진행했습니다. 반년대회 때보다도 많은, 무려 33팀 86명의 학생들이 참가 신청을 해줘서, 강당 옆 일반 교실까지도 대회장으로 사용했습니다.
  • 강당 들어가는 길에 공간이 좀 있어서, 여기에 프린터를 세팅했습니다. 프린터는 제가 집에서 들고 왔는데, 들고 옮기다가 그런 건지 컬러 인쇄가 아예 되지 않아서 프린터를 거의 쓰지 못했습니다.
  • 2/3인팀 중 희망하는 팀은 1컴을 쓸 수 있도록 했고, 그런 팀에 한해 지문 한 부와 코드 인쇄 요청 기능을 제공했습니다. 지문은 집에서 인쇄해왔고, 200장 가까이 뽑은 것 같습니다.
    • 백준 스택에서 대회 전날 (크리스마스) 오전까지 지문 검수를 완료받고, 오후에 인쇄했습니다.
    • 형식은 UCPC 2024의 지문 텍 파일을 얻게 되어서, 여기에 표지와 백그라운드를 새로 디자인하고 폰트를 바꿔서 썼습니다.
  • 풍선 스탠드는 반년대회 때 쓴 것을 그대로 써서 십만원 좀 넘는 금액을 아꼈습니다. 내년에도 가져다 쓰라고 학교에 두고 왔습니다.
  • 작년에 비해 훨씬 셋이 쉬워졌으므로 문제도 많이 풀릴 것이라 예상했고, 반년대회와 비슷한 분량으로 풍선을 준비했습니다.
  • 감사하게도, 넥슨에서 특별상과 참가상을 올해도 푸짐하게 지원해주셨습니다. 근데 참가상을 나눠주는 걸 까먹어버리는 바람에, 대회 다음날에 참가자들을 불러서 다시 나눠줘야 했습니다.
  • 대회 중간중간에 퀴즈도 주고 이것저것 특별상 주는 이벤트를 많이 준비했습니다. 송도고 코드마스터에서 영감을 받아서 진행했습니다. 감사합니다.
  • 송년대회 예산은 반년대회보다 좀 더 널널했고, 실제로 돈이 조금 남았습니다. 송년대회는 스폰서가 선생님을 거쳐서 오기 때문에, 감사하게도 피자도 그렇고 순위상이나 다양한 물품을 선생님이 구매해주셨습니다.
  • 이번에도 배경을 만들고 장패드를 뽑았습니다. 역시나 gs22123이 만들어줬습니다. 거의 40개쯤 뽑았던 것 같습니다.
    • 이번엔 블렌더로 3D 디자인을 했습니다.
    • 근데 거의 다 만들어놓고 파일을 날려먹어버려서, gs22123이 캡쳐본을 기반으로 열심히 따라 만들었던 기억이 납니다.
  • 이번에도 검수진 해주셨던 선배님들이 많이 오셨습니다. ibm2006, asdfsdf, mjhmjh1104, puppy, kim16, kizen, songc, jk410, 그리고 경곽도 아니고 검수도 안했지만 그냥 놀러오신(?) schur까지 9명이 찾아오셔서 현장 일을 도와주셨습니다.
  • 물론 이번에도 제일 많이 구른 것 같지만, 반년대회 때에 비해 다른 분들로부터 더 많은 도움을 받았던 것 같습니다. 이번에도 어김없이 함께 가장 많이 노력해준 gs22123, L번을 어떻게든 출제해내는 데 성공해준 denniskim, 유한평면 문제의 부활과 더불어 많은 고퀄리티 문제를 내준 ehlee0815, 폴리곤 처음 쓰는데도 깔쌈하게 넥슨 지문까지 써준 iccodly, 많은 문제를 검수했으나 아쉽게도 독감?으로 본대회에 오지 못한 junwoojune에게 감사합니다.
  • B의 예제 2번 예외를 발견해주신 qwerasdfzxcl님, 예제 2가 없는 B번을 5시간 넘게 잡고 폭사해주신(?) ibm2006님, 그걸 보고 예제 2 삭제를 열심히 주장해주신 puppy님, 저는 평생 못 풀 것 같은 L번을 검수해주신 flappybird님, lisifu님, songc님, 경기과학고 지문 검수의 1인자 mjhmjh1104님, F번을 재창조해주신 jk410님, 매우 빠르게 검수 코멘트를 남겨주신 gs20036님, 현장 오셔서 일만 하다가 제일 마지막에 가신 schur님께도 정말 대단히 감사하고 수고하셨고 사랑해요.
  • 대회 진행을 정말 많이 도와주신 tosang 정보 선생님과 대회를 후원해준 넥슨재단과 flappybird님께도 다시 한번 감사드립니다.
  • 앞으로는 송년대회 운영진 말고 검수진으로 뵙겠습니다.

I. 수열과 수열: 스페셜 저지

  • 수열을 짝수 인덱스 수열과 홀수 인덱스 수열으로 나누어 봅시다.
    • 이걸 문제 풀이 과정에 필요한 아이디어로 착각해서 헤맨 참가자들이 몇몇 있었습니다.
  • 그러면, 한 번의 연산은 결국 짝수 인덱스 수열과 홀수 인덱스 수열에서 같은 길이의 부분수열을 찾아 swap해주는 것과 동치입니다.
  • 스플레이 트리라던가 적당한 BBST를 이용하면 구현할 수 있습니다.
  • 제가 너무 게을러서 에디토리얼이 과연 나올지 모르겠습니다. 제 문제들이라도 여기 풀이를 적어두겠습니다.

B. 그래프 곱셈: 정해

  • 발상을 쉽게 하기 위해, G 위에 어떤 말이 있어서 이 말이 그래프 위에서 움직인다고 합시다. 그와 동치로, A와 B 위에 각각 말이 있어서 G 위의 이동에 대응되게 A와 B 위의 말을 움직입시다.
  • 데카르트적은 쉽습니다; A에서의 최단거리와 B에서의 최단거리의 합이 G에서의 최단거리가 됩니다.
    • 직관적으로, G에서 간선 하나를 이동하는 것은 A와 B 중 하나의 말을 한 번 이동하는 것과 같습니다.
    • A와 B가 모두 정해진 시작점에서 정해진 목표까지 이동해야 하므로, 두 최단거리의 합이 G에서의 최단거리입니다.
  • 강적 또한 쉽습니다; A와 B에서의 최단거리 중 더 큰 것이 G에서의 최단거리입니다.
    • 이번에는, G에서 간선 하나를 이동하는 것은
      • A에서 한 칸 이동하거나
      • B에서 한 칸 이동하거나
      • 둘 다에서 한 칸 이동하거나
    • 중 하나에 대응됩니다.
    • 따라서, WLOG A에서의 최단거리가 더 길다면, A에서 말을 이동하는 동안 B의 말도 목적지까지 보낼 수 있습니다. 따라서 이것이 최단거리입니다.
  • 텐서적은 어렵습니다.
    • 이번에는 G에서 간선 하나를 이동하는 것이 A와 B에서 무조건 동시에 한 칸씩 움직이는 것과 동일합니다.
    • 따라서, G에서 X번 이동하면 A에서도 X번 B에서도 X번 이동해야 합니다.
    • A에서 X번 이동하는 동안 B에서는 왔다갔다만 반복하고 있을 수 있기 때문에, A에서와 B에서 이동거리의 기우성만 맞으면 됩니다.
    • 따라서, A와 B에서 각각 홀수 길이의 경로 중 최단경로, 짝수 길이 중 최단경로를 각각 구해 둬야 합니다.
    • 그 다음에는 이거를 참고하면 되는데, 정점을 두 배 만들어서 다익스트라를 돌리면 홀수 짝수 최단경로를 각각 구할 수 있습니다.
  • 여기까지 짜면 예제 2에서 걸리게 되는데, 텐서적에서 A나 B 중 하나에서 시작 정점의 degree가 0인 경우 왔다갔다를 할 수가 없게 됩니다. 이 경우를 예외처리해주어야 합니다.
    • 근데, 이 처리를 안하고도 예제 2가 통과하는 코드가 있다고 하더라고요. 이것때문에 B번에서 시간을 많이 날린 친구들이 꽤 많았습니다.

D. 시설물 사용 신청: 정해

  • 일단 답의 크기를 잡아봅시다. 구간 그래프는 최대 클리크와 채색 수가 같기 때문에 답의 크기는 최대 클리크 크기와 같습니다.
  • N의 기우성으로 경우의 수를 나눠서,
  • N이 짝수인 경우…
    • 길이가 1인 구간은 N-1개, 2인 구간은 N-2개… N-1인 구간은 1개 나옵니다.
    • 구간 그래프의 최대 클리크를 잡아봅시다. 직관적으로 가운데 있는 단위구간 위에 최대 클리크가 잡히게 됩니다. 즉 (N/2, N/2+1)이 최대 클리크입니다.
    • 그 크기를 잡기 위해서는 그 단위구간을 포함하는 구간의 수를 세면 됩니다. 시작점을 위 구간의 앞에서, 종점을 뒤에서 잡으면 되므로, 크기는 N^2/4입니다.
    • 따라서 답의 크기는 N^2/4가 됩니다.
  • N이 홀수인 경우…
    • 길이가 1인 단위구간의 수가 짝수이므로, 그 정가운데에 있는 것을 잡을 수 없습니다.
    • 따라서 정가운데에서 가장 가까이 있는 것이 최대 클리크입니다. 위치는 ((N-1)/2, (N+1)/2)가 됩니다.
    • 그 크기는 (N-1)(N+1)/2가 되며, 이것이 답입니다.
  • 그럼 해 구성을 해봅시다.
    • (이 부분의 답은 여러가지입니다. 사실 그냥 회의실 배정 문제를 구현해서 해결해도 됩니다. 정해의 구성은 다음과 같습니다.)
    • (1, N)은 무조건 한 강의실을 혼자 써야 합니다.
    • 두 개의 구간의 합집합이 (1, N)이 되는 것이 N-2개 있습니다: (1, 2)와 (2, N), (1, 3)과 (3, N) 등. 이것들을 모두 강의실 하나씩에 배정합니다.
    • 두 과정에서 2N-1개의 구간을 사용했습니다.
    • 남은 구간들 중 (2, N-1)은 무조건 한 강의실을 써야 합니다. 이 구간에 붙일 수 있는 구간인 (1, 2)와 (N-1, N)을 모두 써버렸기 때문입니다.
    • 두 개의 구간의 합집합이 (2, N-1)이 되는 것이 N-3개 있습니다. 이것들을 각각 강의실 하나씩에 배정해 둡시다.
    • 이번에는 두 과정에서 2N-5개의 구간을 사용했습니다.
    • 반복합니다.
    • N이 짝수인 경우, 맨 마지막에 (N/2, N/2+1) 구간을 마지막으로 강의실에 배정하면 끝이 납니다.
    • 이때 강의실의 수를 세면 딱 N^2/4가 됩니다! 따라서 해 구성이 끝납니다.
    • N이 홀수인 경우, 맨 마지막에 ((N-1)/2, (N+3)/2) 구간을 세고 ((N-1)/2, (N+1)/2), ((N+1)/2, (N+3)/2) 구간을 같이 세면 끝이 납니다. 이때의 강의실 수를 세면 역시 (N-1)(N+1)/2입니다.

I. 수열과 수열: 정해

  • 어떤 순열이 주어지더라도 그 순열을 정렬할 수 있으면 문제를 풀 수 있습니다. 이걸 풀어봅시다.
  • 일단, 한 가지의 웰노운에서 시작합시다. A. 어떤 순열에서, 서로 겹치지 않도록 몇 개의 원소 쌍을 선택하고 이들을 swap하는 것을 한 번의 작업이라고 정의합시다. 작업 두 번이면 어떤 순열이던 정렬할 수 있습니다.
    • Constructive하게 증명해봅시다.
    • 순열을 사이클 분할합니다. 이때 길이가 3 이상의 홀수인 사이클과 4 이상의 짝수인 사이클만을 선택합니다.
    • 아무 원소나 잡고, 사이클에서 그 원소의 바로 앞 원소와 바로 뒤 원소를 swap해줍니다.
    • 그러면 길이 L의 사이클이 길이 2의 사이클과 L-2의 사이클으로 쪼개집니다. 이때, swap해준 두 원소는 길이 2짜리 사이클에 하나, L-2짜리 사이클에 하나가 있고, 처음에 골랐던 원소는 길이 2짜리 사이클에 있습니다.
    • swap해준 원소 중 길이 L-2짜리 사이클에 있는 것을 선택해서, 아까 했던 것처럼 그 앞뒤 원소를 swap합니다. 그러면 두 swap이 겹치지 않으면서 사이클을 다시 길이 2와 L-4의 두 사이클으로 분할했습니다.
    • 이걸 계속 반복하면, 한 번의 작업으로 모든 순열사이클을 크기 2 이하가 되도록 분할할 수 있습니다.
    • 이제 크기가 2인 순열 사이클만 가져다가 모두 한 번에 swap해줍니다. 그러면 두 번의 작업으로 순열이 정렬됩니다.
  • 이제 O(L)에 (되도록 2.5L 안쪽으로) 길이 L의 수열에 작업을 가하는 방법을 찾고 싶습니다.
  • 이것과 별 상관이 없어보이지만, 어쨌든 재미있는 사실을 하나 찾아보자면, B. L번의 연산으로 길이 L의 수열을 뒤집을 수 있습니다.
    • 길이가 짝수인 경우, (1, L), (2, L-1), (1, L), (2, L-1)… 연산을 도합 L번 반복하면 됩니다. (L이 짝수이므로 마지막 연산은 (2, L-1)입니다.)
      • 왜일까요?
      • 첫 번째 원소를 봅시다. 첫번째 연산에서는 2로, 두번째에서는 3으로, 세번째에서 4로… 이동합니다. L-1번째에 L으로 이동하면, L번째 연산은 L번째 칸에 영향이 없으므로 L번 연산 이후에 L번째 원소가 되어 있습니다.
      • 두 번째 원소는, 일단 첫번째 연산에서 1으로 이동한 뒤 두번째에서는 이동하지 않습니다. 세번째부터는 위와 똑같이 이동하므로, L번째 연산에서는 L-1번 칸에 가게 됩니다.
      • 세 번째 원소는 첫번째 연산에서부터 오른쪽으로 이동하여 L-3번째 연산에서 L번 원소가 됩니다. L-2번째 연산에서는 이동하지 않고, L-1번째와 L번째 연산에서 각각 왼쪽으로 한 칸씩 이동하므로 L-2번째 원소가 됩니다.
    • 길이가 홀수인 경우, (1, L-1), (2,L), (1, L-1), (2, L)을 도합 L번 반복하면 됩니다. (L이 홀수이므로 마지막 연산은 (1, L-1)입니다.)
      • 위와 같은 방법으로 생각해보면 됩니다.
  • 그런데 생각해보면, 한 번의 연산에서 한 원소는 그 자리에 가만히 있거나 왼쪽 오른쪽으로 최대 한 칸만큼만 이동할 수 있습니다.
  • 따라서, **C. 순열에서 어떤 서로 다른 두 원소를 선택해도, 그 순열에 B를 가하면 두 원소가 적어도 한 번 swap됩니다.
    • 순열에서 어떤 두 원소의 순서가 역전되기 위해서는 두 원소가 swap되어야 함은 자명합니다. (연산 한 번에서 각 원소가 최대 한 칸밖에 움직일 수 없으니까요.)
    • 근데 수열을 뒤집으면 어떤 두 원소를 잡아도 두 개가 swap됩니다.
    • 따라서 C가 성립합니다.
  • 그렇다면, A의 ‘작업’을 다음과 같이 할 수 있습니다.
    • B의 방법에 따라서 순열을 뒤집습니다.
    • 뒤집다 보면 어느 순간에는 ‘작업’에서 swap해줘야 하는 두 원소가 인접하게 됩니다.
    • 그 순간, 순열을 뒤집은 연산을 계속하기 전에 두 원소를 swap해 줍니다.
    • 한 번의 작업에서 swap해주어야 하는 원소의 쌍은 최대 N/2개입니다.
    • 따라서 한 번의 작업은 1.5N개의 연산 이하로 해결할 수 있습니다.
  • 그럼 이제 풀이가 가능합니다.
    1. 수열이 주어지면, 이 수열을 정렬하기 위해 가해야 하는 작업 두 개를 찾습니다. 그리고 각 작업에서 swap해주어야 하는 원소 쌍들을 모두 찾습니다.
    2. 수열을 B의 방법으로 뒤집으면서, 첫 번째 작업에서 swap해주어야 하는 두 원소가 인접하게 되는 순간 두 원소를 한 번의 연산으로 swap해줍니다.
      • 이걸 처리할 수 있는 방법은 여러 가지가 있습니다.
      • 임의의 두 원소가 언제 인접하게 되는지는 쉽게 찾을 수 있으므로 그냥 그때의 인덱스를 계산해서 어떤 연산을 언제 실행해야 하는지 미리 계산해두는 것이 가장 간단한 것 같습니다.
    3. 한번 더 수열을 B의 방법으로 뒤집으면서, 두 번째 작업에서 swap해주어야 하는 원소들을 같은 방법으로 swap합니다.
    4. 그러면 3N번의 연산으로 순열을 정렬할 수 있습니다!

J. 트리를 안 쓰는 트리 문제: 정해

  • 제목처럼, 트리랑은 아무 관련 없이 construction만 잘 하면 되는 문제입니다.
  • 일단 M=2N-1이 가능함은 어렵지 않게 찾을 수 있습니다. 여러 가지 해가 있는데, 정해는 여기서 확인해볼 수 있습니다.
    • N개의 행 중 하나만 그대로 냅두고 나머지 행은 모두 한 번만 자르는 걸 생각하면 쉽습니다.
  • 그게 최소임을 보여 봅시다. 초기 상태에서 최종 상태로 가는 것이 아니고, 최종 상태에서 초기 상태로 가기 위해 몇 번 더 잘라야 하는지를 확인해볼 겁니다.
  • 최종 상태는 N개의 조각이 있는 상태이고, 각 조각은 [1, 2, …, N], [2, 3, …, N, 1], [3, …, N, 1, 2], …, [N, 1, 2, …, N-1]입니다.
  • 어떤 정점 N개의 그래프를 생각합시다. [a, a+1, a+2, …, b-2, b-1]이 적힌 조각을 a번 정점에서 b번 정점으로 가는 유향 간선이라고 생각합시다.
    • 단 b-1이 N이면 b는 1이라고 생각합시다.
  • 그렇다면, 최종 상태는 1에서 1으로, 2에서 2로, …, N에서 N으로가는 self loop 간선이 N개 있는 상태입니다. 즉, 최종 상태에서는 그래프의 연결 요소가 N개입니다.
  • 초기 상태는, 몇 번이나 잘려있을 지는 모르지만, 어쨌든 a에서 b로 가는 간선이 있다면 그 다음 조각은 b에서 나가는 간선이 되기 때문에, 연결 요소가 1개인 사이클을 이룹니다.
  • [a, a+1, a+2, …, b-2, b-1]이 적힌 조각을 한 번 자르면, a에서 b로 가는 간선을, 어떤 새로운 정점 c에 대해 a에서 c로 갔다가 b로 가는 간선으로 만들 수 있습니다.
    • 예를 들어, [1, 2, 3, 4, 5] 조각을 [1, 2, 3]과 [4, 5]로 자르면, 1에서 1으로 가는 간선을 1에서 4로 가는 간선과 4에서 1으로 가는 간선으로 자른 꼴이 됩니다.
  • 따라서, 조각을 한 번 자를 때마다 연결 요소의 수를 최대 하나씩 줄여나갈 수 있습니다.
  • 최종 상태에는 연결 요소가 N개, 초기에는 1개이므로, 최종 상태에서 초기 상태로 가려면 조각을 적어도 N-1번은 더 잘라야 합니다.
  • 이미 최종 상태에서 N-1번이 잘려 있으므로 도합 2N-2번은 잘라야 합니다. 자른 횟수에 1을 더하면 조각 개수이므로, 최소 조각 개수는 2N-1입니다.
PS, others
cp gshs
This post is licensed under CC BY 4.0 by the author.