Back to : cp-rounds
Contents

작년에 중앙대학교 프로그래밍 대회 (CPC) 의 검수를 맡았었는데, 올해는 같은 대학의 신입생용 대회인 Newbie Programming Contest, 줄여서 NPC의 검수를 맡게 되었습니다.
작년 CPC의 풀이는 링크 에 작성했는데, 최대 플래티넘 2까지의 상당한 고난도 문제가 출제되는 CPC와는 달리 NPC는 신입생들을 위해 쉽게 출제되는 대회이므로 약간 성격이 다릅니다. 올해 CPC도 검수에 참여할 수 있으면 재밌을것 같은데 불러주실지 모르겠네요

A. 이진 딸기

  • 검수 예상 난이도 : 브론즈 1
  • 패턴을 찾으면 되는 문제입니다. 패턴의 길이가 28개임을 (대충 종이에 써보면 어렵지 않게) 관찰합니다.

B. 주간 달력

  • 검수 예상 난이도 : 골드 4
  • ‘첫 날짜’ 가 며칠인지를 정하면, 나머지는 모두 자연스럽게 계산 가능하다는 것을 파악합니다.
  • 그런데, 그냥 브루트포스 계산에 얼마의 시간이 걸릴까요?
  • $[S, E]$ 를 알면 모듈러 연산을 통해 직접 다 돌아서 테이프를 자르는 횟수를 구하면 되므로, $O(M)$ 에 한번 계산해 볼 수 있습니다.
  • 가능한 시작일은 1일부터 50000일까지이므로 ($T$라고 하겠습니다. 그 이상은 어차피 일정이 없으므로 무의미합니다)
  • 50000 * 1000 시간에 브루트포스로 해결할 수 있습니다.
  • Sweeping, Segment Tree 등 여러 방법으로 복잡도를 더 줄일 수 있습니다. 스위핑으로는 $O(M + T)$, 세그먼트 트리로는 $O(M + T\log T)$ 같은 시간에 풀 수 있을텐데, 이 문제는 $O(TM)$ 을 허용하도록 출제되었습니다.

C. 교수님 계산기가 고장났어요!

  • 검수 예상 난이도 : 실버 3 (C++ 기준)
  • 가장 많은 논의가 있었던 문제입니다.
  • 그냥 곱셈인데, double의 정밀도를 넘어서는 계산을 어떻게 할 것인가? 를 요구하는 문제입니다.
  • python의 Decimal 라이브러리를 쓰면 다섯 줄로 풀 수 있습니다.
  • C++같은 언어로 풀기 위해서는, 실수의 곱셈을 문자열로 구현하거나, 큰 수를 곱해서 unsigned long long 같은 자료형에 집어넣은다음 다시 나중에 소숫점 위치를 정해서 찍어주면 됩니다.
  • 언어에 따라 난이도가 달라지는 문제가 출제되어도 되는가? 라는 논의가 있었는데, 주최측에서는 ‘문제에 적합한 언어를 판단하고 사용하는 것도 대회의 일부’ 라는 견해를 가지고 계셨습니다. 여기부터는 개인의 가치판단의 영역이라고 생각합니다.
  • 별개로, 원래는 16자리였는데 float128로 뚫림을 제보했더니 18자리로 늘어났습니다. 이것보다 정밀도를 더 많이 요구하면 C++가 unsigned long long으로 풀 수 없어서 너무 차이가 벌어진다는 이유로 정해진 아슬아슬한 정밀도입니다.

D. 백발백준하는 명사수

  • 검수 예상 난이도 : 브론즈 2
  • 고등학교 1학년 수학입니다. $R_1 + R_2$ 와 중심간의 거리 $D$를 비교하면 됩니다.

E. 쿠키크루

  • 검수 예상 난이도 : 실버 1
  • 구현 문제입니다. 집 1개, 네가지맛 과자가 3개, 도착점 1개가 있으므로 집->과자1->과자2->과자3->도착점 의 거리를 그냥 다 구하면 됩니다. 여기서, 각 과자 3개에는 순서를 부여해야 하므로 next_permutation같은걸로 6가지 경우를 모두 시도하면 됩니다.
  • 추가적인 제약이 있었으면 더 재밌었을것 같은데, 이 상황에서는 두 점의 거리는 $l_0$ 거리를 그냥 쓰면 됩니다.

F. 선형 연립 방정식

  • 검수 에상 난이도 : 골드 4
  • Gaussian Elimination.
  • 해가 있음이 주어져 있기 때문에, 구현상의 주의점 (0으로 나누는 경우 조심 등) 을 지키지 않아도 구현할 수 있습니다.
  • 별개로, 정수만 이용하여 가우스 소거법을 하도록 강제하는 (gcd, lcm을 이용하여) 문제였어도 좋았을 것 같은데 C번과 너무 컨셉이 겹치는것 같기도 하고… 지금은 제약이 작아서 실수연산해도 됩니다.

G. RPG 마스터

  • 검수 예상 난이도 : 실버 2
  • 예전에 코포 B번쯤에 꽤 많이 나오던 유형인데, 게임을 실제 시뮬레이션하면 시간상 통과하기 힘듭니다.
  • 단순한 스텝들 - 그러니까, 어차피 적의 체력이 $S$ 이상이고 내 체력도 충분한 - 을 묶어서 스킵하면 어렵지 않은 구현 문제입니다.
  • 경우를 침착하게 나누는 연습이 필요합니다.

후기

  • 브론즈 ~ 쉬운 골드 사이의 문제라서 전형적인 문제들도 많이 있었고, 막 멋진 문제가 있는것은 아니었지만 신입생의 프로그래밍 능력 향상이라는 본 목적에 충실한, educational round가 아닌가 싶습니다.
  • B번 (브루트포스의 복잡도 파악), C번 (실수오차에 대한 이해) 같은 문제들은 처음 PS를 시작하거나 할때 생각해볼만한 주제들을 던져주는 의미가 있을 것 같습니다.
  • A번 (패턴찾기), G번 (역시 일종의 경우 나누기) 또한 요즘 코포에서는 굉장히 트렌드로 밀고 있는 문제기도 합니다.
  • D번은 가장 쉬운 문제니까 하나 있어야 하고, E, F도 전형적인 테크닉 (2차원에서 이런거 구현하기, 가우스 소거법) 을 구현하는 문제지만 NPC의 본 목적에 부합한다고 생각합니다.
  • 재밌었습니다 :) CPC때 불러주세요~