2022 IGRUS Newbie Programming Contest 운영 후기

INPC가 3회까지 올 줄은 몰랐는데... 아무튼 열렸다!

이런저런 내부 사정으로 굉장히 서두르며 준비했지만, 운영진 및 검수진 분들이 정말 많이 고생해주신 덕분에 본 대회는 물론이고 오픈 콘테스트까지 무사히 마무리되었다.

 

운영 : tyoungs, panda959595 및 동아리 내부 운영진

출제 및 운영 : 39dll, aym506, yuja, 나

검수 : chlwnsgud7, gumgood, wjdclgns12

 

본 대회는 3인 1팀, 총 7팀이 참가했다.

이번 대회는 현장에서 지켜볼 수 있었는데, 거두절미하고 말하자면 꽤 북적거리고 분위기도 화기애애해서(중요) 정말정말 만족스러웠다.

 

그냥 학교가는 길에 찍은 사진 ㅎㅎ

출제 기조

문제 형식과 유형은 기존 INPC와 크게 다르지 않다. 그런데...

죄송합니다.

작년 INPC가 굉장히 불필요하게 어려웠다.

 

이번엔 알고리즘 입문자분들이 주말에 학교까지 와서 멍때리다 가는 불상사를 막기 위해 많이 노력했다.

제한은 충분히 쉬운 풀이를 기준으로 설정하고, 지문은 문제에 접근하기 용이하도록 작성했다.

 

본 대회 스코어보드

대회에선 12문제 중 11문제가 풀렸고, 중위권도 절반은 풀었기 때문에 꽤 이상적이라고 생각한다.

 

간략한 해설

A. 포인터 공부

지문에 좋은 내용이 있지만, PS관점에서 보면 그냥 별 찍는 문제다.

검수할 때 틀렸다. (부끄럽다)

 

B. 출석 이벤트

사용할 수 있는 쿠폰을 전부 적용해보고, 그 중 최적값을 출력하면 된다.

출석 도장을 최대한 소모하는 게 반드시 최적이진 않다는 점에 유의하자.

 

C. 돌림판 문자열

돌림판에 필요한 문자가 한 개라도 없다면 불가능하다.

모두 있다면 한 칸씩 돌리면서 추가하려는 문자가 등장할 때마다 무조건 추가하면 된다.

많아야 NM 번 회전시키게 되므로 특별한 최적화 없이 구현해도 좋다.

 

D. 자전거 묘기

DP 점화식이 문제에 적혀있다(!) 실제로 DP는 잘 모르지만 푼 팀이 있다고 들었다.

DP[i] = ( 1 + DP[i + A[i] + 1] ) if ( i + A[i] + 1 <= N ) else ( 1 )

 

E. 팔찌 만들기

구슬을 아무렇게나 나열한 뒤 식 |a1 - a2| + |a2 - a3| + ... + |an - a1| 를 잘 관찰해보자.

어떻게 나열해도 제일 큰 수는 두 번 더하게 되고, 제일 작은 수는 두 번 빼게 되므로 답은 적어도 2*max(a) - 2*min(a) 이다.

 

그런데 "잘" 나열하면 나머지 수들을 전부 소거해 0으로 만들 수 있다. 재밌으니까 한 번 생각해보자.

 

F. 만남의 광장

각 행과 각 열의 아름다움의 합을 미리 구해두면, 브루트포스 O(N^4) 에 문제를 해결할 수 있다.

 

G. 1 빼기

"1"을 지우면 자릿수가 하나 이상 줄어들고, -1을 하면 자릿수가 많아야 하나 줄어든다.

-1을 한다고 없던 1이 두개이상 생기지도 않으므로 "1"이 있으면 무조건 지우고 없으면 -1을 하는 그리디가 성립한다.

사실 그냥 BFS해도 된다. (BFS를 통과시키기 위해 제한이 굉장히 작다)

 

놀랍게도 재미있는 O(자릿수) 풀이가 있다.

 

H. 점수 계산

수가 10만개 주어지지만, 그 종류는 최대 999개이다 -> 비둘기집의 원리에 의해 같은 수가 엄청나게 많음을 알 수 있다.

각 수가 몇 번 주어졌는지 세면 브루트포스 O(999^4) 에 문제를 해결할 수 있다.

 

I. 인경산

INPC 전통의 누적합 문제다.

왼쪽 산장에서 오른쪽 산장으로 이동할 때의 누적합, 오른쪽 산장에서 왼쪽 산장으로 이동할 때의 누적합 두개를 구하면 된다. 실수 오차는 double만 사용해도 스페셜저지 오차범위를 넉넉히 만족할 수 있다.

 

내가 작성한 문제 초안은 아무도 구현하고싶지 않아할 그런거였는데, 멋진 39dll님이 재창조해주셨다.

 

J. 인경강

N은 엄청나게 크고 M은 납득 가능하며 열 정보의 길이는 매우 작다는 점을 이용하자.

결국 각 열마다 최대 10개의 구간이 있는 셈인데, 이 구간들은 왼쪽 열에서 올 수 있는것과 아닌 것으로 구분할 수 있다.

• 있는 것 : 오른쪽 열의 어떤 구간들이 도달 가능한지 여부를 결정한다
• 아닌 것 : 아무 쓸모가 없다

따라서 각 열마다 왼쪽 열에서 올 수 있는 구간들이 무엇인지 체크하면 O(M) 에 문제를 해결할 수 있다.

 

K. 괴도 인하

괴도 인하가 아래 또는 오른쪽으로만 이동할 수 있다는 점에 주목하자.

어떤 CCTV 감시영역에 들어선다면, 영역의 맨 왼쪽 열(오른쪽으로 이동) 또는 맨 위쪽 행(아래로 이동)을 반드시 거치게 된다.

그래서 감시영역이 가로로 N칸 세로로 M칸일 때, 실제 필요한 정보는 N*M 칸이 아니라 N+M 칸이다.

 

개인적으로 이번 대회에서 가장 좋은 문제라고 생각한다.

 

L. 점프 쇼다운

풀이가 꽤 다양했는데, 제한이 의도한 바는 상수가 잔뜩 붙은 조합론 풀이를 통과시키는 것이다.

 

사라지지 않을 판을 3개 고르면, 서로 독립된 컴포넌트 3개의 크기가 정해진다.

크기가 k인 컴포넌트에서 제일 먼저 사라질 판을 고르면, 나머지 k-1개는 사라질 때 이미 사라진 판과 시계방향 또는 반시계방향으로 인접해야 한다.

 

다르게 말해 처음 사라지는 것을 기준으로 시계방향 / 반시계방향을 k-1번 정하면 그렇게 판이 사라지는 방법은 유일하다.

예를들어 k = 4고 (시계, 반시계, 시계)로 정했다면, 그 방법은 (2, 3, 1, 4)뿐이다. (수가 커지는 방향이 시계방향)

 

세 컴포넌트의 크기가 a, b, c라면 2^{max(0, a-1)} * 2^{max(0, b-1)} * 2^{max(0, c-1)} * (떨어질 판 N-3개를 세 집합에 분배하되 크기가 각각 a, b, c가 되게 하는 경우의 수) 가지 경우의 수에서 억울한 플레이어가 발생하지 않는다.