2021 IGRUS Newbie Programming Contest 운영 후기

오늘(3월 28일) 오픈 컨테스트까지 무사히 끝났다.

 

작년 대회를 여신 선배님이 출제자를 모집한다고 하셔서 지원했고, 결국 세 문제를 내게 되었다.

 

그 밖에 해설 PPT(비공개로 해야 하는 것 같다) 제작 등 자질구레한 일들을 했다.

 

 

대회는 백준 온라인 저지에서 비대면으로 진행하였다.

 

공지가 늦는 등 운영의 부족함과 일부 모호한 지문에 참가자 분들께 정말 죄송했다. ㅜㅜ

 

그래도 많은 학우분들이 대회 끝나기 직전까지도 열심히 참여해주셔서 정말 감사했다.

최종 결정된 수상권의 문제 해결 수 분포는 8솔 4명, 7솔 2명, 6솔 2명, 5솔 4명이다.

 

1등 10솔브 정도를 예상하고 출제하였는데 생각보다 많이 어려웠던 거 같다.

 

 

다음은 검수 단계에서 내가 풀었거나 시도한 문제들에 대한 간단한 설명이다.

 

 

A. 홀짝 칵테일

 

두 정수의 곱이 홀수이려면, 둘 모두 홀수여야 한다.

 

고유 번호가 1인 칵테일까지 고려하여 해결하면 된다.

 

 

B. 문어

 

내가 낸 문제(1) 이다.

 

환형으로 같은 수가 인접하지 않은 수열을 출력하면 된다.

 

문어가 홀수 마리일 때 1 2 1 2 ... 1 2 ? 꼴이 되므로, ? 자리엔 1과 2가 올 수 없다는 사실만 발견하면 된다.

 

 

C. 민겸 수

 

최댓값은 MM...MK 를 전부 50...00 으로 만들고, 마지막에 K로 끝나지 않는다면 남은 M을 모두 1로 만든다.

 

최솟값은 MM...MM 을 전부 10...00 으로 만들고, K는 5로 만든다.

 

대회 때 대부분 위 규칙은 쉽게 찾았지만, 숫자가 매우 크다는 사실을 놓친 분이 많아 안타까웠다. ㅜㅜ

 

 

D. 카드 섞기

 

문제에서 주어진 그대로 시뮬레이션 하면 풀린다.

 

구현 난이도 때문인지, 최상위권을 포함한 많은 학우분들이 손도 안대셨다.

 

오히려 시뮬레이션 대신 문제의 조건을 이용해 O(log N) 같은 풀이를 작성한 분도 계셔서 감탄했다.

 

 

E. 스피카

 

내가 낸 문제(2) 이다.

 

그래프 문제를 내고 싶어 + 선배님의 '알고리즘 몰라도 풀 수 있는 문제' 주문 으로 만들어졌다.

 

별을 정점 · 선분을 간선으로 바꾸고, 스피카만이 가지는 특징을 관찰하면 된다.

 

예를 들어 자신과 연결된 세 별의 degree 합이 6인 별은 스피카가 유일하다.

 

 

F. 징검다리 건너기

 

브루트포스가 가능한 문제이므로 재귀, BFS, DP 등 아무렇게나 풀어도 된다.

 

나는 큐에 (현재 위치, 에너지, 큰 점프 여부) 튜플을 넣고 메모이제이션 없이 브루트포싱 했다.

 

 

G. 피아노 체조

 

내가 낸 문제(3) 이다.

 

실수하는 악보를 1, 그 외를 0인 수열로 바꾸어 생각하면 구간합 구하기 문제이다.

 

누적합을 사용해도 되고, 원하면 세그먼트 트리를 써도 된다.

 

그 밖에도 실수하는 악보를 배열에 넣어 이분탐색하는 등, 단순 O(QN) 풀이만 아니면 모두 허용하는 선에서 시간 제한을 잡았다.

 

 

H. 챔피언 (Easy)

 

중복된 전투력은 모두 무시하고, 시뮬레이션 하면 된다.

 

단, N명에 대해 모두 하는것이 아니고 이분탐색으로 결정해야 시간 안에 돌아간다.

 

 

I. 순간이동 여행

J. 클레이 사격 게임

 

DP를 잘 못해서 모르겠다 ㅎㅎ

 

 

K. 격자 돌리기

 

크게 회전시키는 쿼리에 대해 진짜 회전시키지 않고, 얼마나 회전하였는지만 기록하여 두면 된다.

 

구현하기 생각보다 까다로운 거 같다.

 

 

L. 챔피언 (Hard)

 

각 선수들은 양 옆 몇명까지 이길 수 있는지에 대한 구간을 가지고 있다.

 

임의의 두 구간 A와 B의 교집합은 A 또는 B (또는 공집합)이다.

 

이를 이용한 최적화로 풀 수 있다고 한다.