2023 IGRUS Newbie Programming Contest 출제 후기

4회 INPC가 열렸고 또 출제를 했다!

이번 학기는 아쉽게도 IGRUS에 회원등록을 하지 않았는데, 출제 + 대회 개최 과정 인수인계를 조건으로 외주? 용역? 같은 걸 하게 되었다. 아마 내년에는 IGRUS 회원이나 운영진 분들이 출제를 하지 않을까?

 

운영 : nunebin, sonhy02, aym506 및 동아리 내부 운영진

출제 : 39dll, aym506, 나

검수 : chlwnsgud7, gumgood, wjdclgns12

 

대회는 개인전으로, 총 26분이 참가해 주셨다.

11월 20일 기준 solved.ac 티어

스코어보드

INPC의 의의는 PS 입문자 분들에게 적절한 난이도의 대회 경험을 제공하고 학습 의지를 북돋우는 것이라고 생각한다. 그런 면에서 생각해 보면 2023 INPC도 다음을 근거로 꽤 성공적인 대회였던 것 같다.

• 참여자 절반 이상이 약 45% 이상의 문제를 해결했다
• 프리징 이후 솔브가 굉장히 많았다

사실 출제 과정에서 중하위권 학생들이 풀만한 문제가 적지 않나 싶었는데, 인하대 1~2학년 학생들이 전반적으로 PS에 능숙해져 이런 결과가 나온 것 같다. 역시 멋있다. 검수진 분들도 문제의 퀄리티가 좋다는 의견을 주셔서 기분이 좋았다.

스코어보드 공개 중 촬영한 사진

운영에선 빠져 자세히는 알지 못하지만, 허름한 강의실을 빌렸던 작년과는 달리 멋진 장소에서 대회를 진행했다. 인하대가 SW 중심대학에 선정되고 벤처 스타트업 아카데미 사업?을 진행하며 이런 부분에서 도움을 많이 주시는 것 같다. 

---

간략한 해설

A. 아이그루스와 화장실

첫 문제로 간단한 사칙연산과 조건문을 활용하는 문제를 준비했다.

1. 주어진 수가 홀수인지 짝수인지 판별하고
2. 필요하다면 K를 K+1, K-1중 구간 [1, N]에 포함되는 값으로 수정하고
3. 출력한다

B. 트릭 플라워

모티브는 TCP Fairness에 관한 그래프다. 원래 두 선분의 교점을 log R번 정도 구하는 수학 문제였는데, 쉬운 문제가 없어서 제한을 조정했다. 꽃이 최악의 방법(?)으로 채워져도 비둘기집의 원리에 의해 (R^2) / 2번이면 모든 칸에 꽃이 피어있게 된다. 따라서 어떤 방법으로든 꽃의 존재 여부를 판별하며 시뮬레이션하면 된다. 다음은 참여자 분들이 작성한 방법들이다.

• 1차원 배열에 좌표를 추가하며 O(N) 탐색
• Set
• 2차원 Array

C. 인형 전시

같은 높이의 인형은 최대 C개 보일 수 있다. 서로 다른 높이의 인형은 항상 둘 다 보이게 배치할 수 있다 (만약 어떤 인형이 다른 인형을 가린다면 둘의 자리를 바꾸면 된다). 따라서 같은 높이의 인형이 C개보다 많다면 버리고, min(남은 인형의 개수, R * C)를 출력하면 된다.

 

D. 회문 끝말잇기

1글자의 단어부터 문자가 추가될 때 사용 가능한 단어의 수가 어떻게 변화하는지 살펴본다.

• 1글자는 1가지, 2글자는 회문이어야 하므로 1가지. (A, AA)
• 3글자는 26가지, 4글자는 회문이어야 하므로 26가지. (ABA ... AZA, ABBA ... AZZA)

길이가 k인 회문 단어는 26^floor((k - 1) / 2)개 사용 가능함을 관찰했다면, 길이가 L인 것부터 U인 것까지 하나씩 세면 된다.

 

승자는 누구일까? 길이가 3 이상인 단어는 짝수개이므로 2人 게임의 결과에 영향을 주지 않는다. 따라서 길이가 1 또는 2인 단어만 확인하면 된다. 여담으로 가장 많은 오답은 승자를 (게임에서 사용된 단어의 수) mod (1e9 + 7)의 홀짝에 따라 출력해 발생했다.

 

E. 점수 관리

정직한 구현 문제이다.

 

F. 최대 합 순서쌍의 개수

같은 수에 대한 "같은 수 순서쌍"중, 서로 가장 멀리 떨어진 쌍을 골랐을 때 합이 최대가 됨이 자명하다. 이를 map 등 자료구조를 이용해 저장하고, 합은 prefix sum 등을 활용해 O(log N)이하에 계산하면 된다.

 

G. 띠 정렬하기

가장 작은 수부터 시작해서, 다음으로 큰 수가 왼쪽 또는 오른쪽에 있다면 최종적으로 같은 띠에 남아있어도 된다. 그렇지 않다면 띠를 잘라야 한다. 이렇게 자른 횟수를 세어 출력하면 된다.

 

H. 운전 연습

가능한 멀리 이동하려면 순간이동 후 다시 돌아왔을 때 전기의 변화량이 가능한 큰 수가 되어야 한다. 한 충전소 i에 대해 그렇게 만드는 충전소를 최적의 충전소 j라고 하자. (0 ≤ j ≤ i - 1)

 

이때, 바로 다음 충전소 i + 1에 대해 j 또는 i만 최적의 충전소가 될 수 있다. 0 ... i 로 돌아가는 i + 1가지 경우에 대해, 추가되는 변화량은 F[i] - (A[i + 1] - A[i])로 동일하기 때문이다. 같은 아이디어에 의해 j와 i중 최적의 충전소는 (i → j → i 이동에서의 변화량) > 0 이라면 j가, 아니라면 i이다.

 

I. 나무 다리

dp[i][j][k][l]를 다음과 같이 정의한다.

• 마지막 나무토막의 좌표가 (i, j)
• k가 1이라면 j가 최솟값인 적이 있던 것
• l이 1이라면 j가 최댓값인 적이 있던 것

j의 범위는 [1, L-1] 내지 [0, L-2] 정도로 잡으면 된다. 그렇다면 k와 l이 모두 1일 때 다리의 너비가 L임을 보장하며, 그렇지 않을 때 다리의 너비가 L이 아님을 보장한다. 따라서 문제의 정답은 dp[W][j][1][1] (1 ≤ j ≤ L - 1)의 합과 같다.