제3회 한국항공대 프로그래밍 경진대회 (KAUPC) 후기

 
[개최자 후기]
https://youngseo-computerblog.tistory.com/103

[후기] 2023 KAUPC 문제 출제 후기

 
 
[문제 확인하기]
https://www.acmicpc.net/category/detail/3632

제3회 한국항공대학교 프로그래밍 경진대회(KAUPC)

 
[참조글]
제1회 한국항공대 프로그래밍 경진대회 1위 후기
제2회 한국항공대 프로그래밍 경진대회 개최 후기
 
[기간]
3월 24일 ~ 7월 29일
 
참여 후기는 아니고 문제 출제 및 검수 후기입니다.
 
옛날에 1회 대회에서 김태현의 생일선물로 나가서 1위를 했던게 얼마전 같은데 벌써 3회 대회네요
그때 1위를 하고, 김태현의 생일선물의 김태현이 수상 소감을 말하는 진귀한 상황이었는데.. 😄
 
[출제 및 내부 검수]
- 20wjsdudtj (올해 개최)
- hello70825 (2022 개최)
- soo7652 (2021 개최)
- gojib2002 (GOAT)
 
[외부 검수]
- chansol
- shjohw12
- utilforever
 
이번 대회에서 어려울 것으로 예상했던 점은 출제하는 사람중에 직장인 2명, 휴학생 1명(나), 재학생이 1명이라 회의 시간 잡기가 힘들 것 같다는 것입니다.
하지만 일찍 문제를 만들기 시작한 점 + 바쁜 시기에는 회의 시간을 밤 10시 이후에 잡고 진행해서 스케줄 상으로 큰 문제점은 없었던 것 같아요.
우테코에서 페어와 미션을 하는데 중간에 밤에 회의를 했어서 미안했던 기억이... 저도 밤 11시까지 캠퍼스에 남아서 코딩할 줄은 몰랐던 때..
 

문제 발생: 각자 현생 사느라 회의하기가 힘들다
해결 방법: 약속이 거의 없는 시간인 밤 10시에 회의를 잡자

 
그리고 문제 만들 때 느꼈지만, 오랜만에 문제 제작 플랫폼인 Polygon을 사용해서 기억이 가물가물 했었는데, 작년에 미리 문서화를 해두어서 다행이었네요. 진짜 쓸 사람만 쓰는 플랫폼이라 한글로 정리된 유일한 가이드라인 블로그 글이 2015년... 이 글마저도 영어나 한글로 된 가이드라인을 찾기 힘들어서 적은 글이라고 나와 있습니다 😭
https://github.com/70825/Create-Programming-Contest

GitHub - 70825/Create-Programming-Contest: 교내 알고리즘 대회 개최 준비를 위한 문제 제작 플랫폼 사용 방

 
 
 
 

1. 출제한 문제 리뷰

---

[1] 곱하기와 쿼리

작년에는 제가 만든 문제들의 난이도가 의도치 않게 너무 높았습니다. (브론즈 4, 골드 1, 골드 1)
그래서 이번에는 난이도 자체는 쉬우면서 많이 틀릴 수 있는 문제를 만들어보자! 라고 생각해서 만들었습니다.
이때 제가 생각하는 함정 케이스뿐만 아니라, 문제를 만드는 중에 gojib2002님이 추가 함정 케이스를 알려주셨고, 외부 검수중에 chansol님이 overflow를 고려한 데이터가 없다고 하여 관련 데이터를 모두 만들어 문제가 좀 더 완벽해진 것 같습니다.
교내 대회에서는 정답률이 낮은 5%였고, BOJ에서도 정답률이 현재 기준 22.867%라서 고생했던 보람이 매우 있네요 😉 랭킹 1위님도 한 번 틀리게 만들어서 더욱 뿌듯했습니다.
 

[문제 아이디어]

문제 아이디어 자체는 브론즈 1에 있는 정렬 알고리즘중에 하나인 계수 정렬(Counting Sort)에서 따왔습니다.
 
문제를 읽어보면 최악의 경우 100,000,000(1억)의 약수를 구해야합니다. 그래서 O(1억 * Q)가 아니냐라고 생각할 수 있지만, X를 약수로 나눈다면 X = Y * Z 꼴로 이루어집니다. 이때 무조건 하나는 다른 수보다 작거나 같습니다. (여기서는 작은 수 = Y, 큰 수 = Z로 가정)
X가 완전제곱수이면 Y가 최대값이 되는 경우는 X의 제곱근입니다. 그래서 root(X)까지만 반복문을 돌려도 X가 Y에 의해 나누어 떨어지는지 확인하면 바로 Z도 함께 구할 수 있습니다.

💡 X가 Y에 의해 나누어 떨어진다. → X / Y = Z이므로 바로 Z를 구할 수 있다!

 
그래서 O(1억 * Q)가 아닌 O(A * Q)로 시간내에 문제를 풀 수 있게 됩니다.
 
계수 정렬 아이디어만 캐치해내면 충분히 문제를 풀 수 있도록 브루트포스로 풀 수 있게 제한을 설정했습니다.
 
 

[오버플로우 데이터 만들기]

외부 검수 과정에서 chansol님이 overflow가 발생하는 코드가 통과한다고 알려주셨습니다.
해당 코드는 int로 선언된 배열인데, 배열의 값이 0이면 인수분해가 불가능하여 0을 출력하고, 배열의 값이 0이 아니라면 인수분해가 가능한 것으로 판단하여 1을 출력합니다.
예시를 들어 설명하자면 배열에 들어가는 값은 arr[x]가 있을 때, 두 수를 곱해서 x를 만들 수 있는 경우의 수 입니다. 만약 입력값이 10 10 10 10이 들어온다면 arr[100]을 만들 수 있는 경우의 수는 6가지입니다. (= 4C2) 
 
사실 해당 코드는 배열을 long long으로 선언하면 문제가 없는 코드입니다. 하지만 int로 선언해서 오버플로우가 발생했기 때문에 의도와 다른 풀이이므로 무조건 틀려야하는 코드입니다.
그런데 이 코드가 통과하는 이유는 딱 한가지 경우에만 틀릴 수 있기 때문입니다. 바로 양수 * 양수인데 오버플로우가 발생해야하고, 오버플로우가 발생하고 나온 결과값이 0이어야하는 상황입니다.
 

[1. 데이터를 만들 수 있는 상황인가?]

먼저 해당 상황의 데이터를 만들 수 있는지, 만드는게 불가능한지 확인해야 합니다.
int 값의 범위는 -2,147,483,647 ~ 2,147,483,647이고, 틀리게 만들 데이터를 만드려면 2,147,483,647 * 2 + 2 =.4,294,977,296을 만들 수 있는 상황이 되어야합니다.
+2를 해주는 이유는 2,147,483,647 → -2,147,483,647로 오버플로우를 발생하는데 +1, 원하는 데이터는 0이므로 +1을 해야합니다.
이때 문제에 주어진 입력값으로 배열에 저장할 수 있는 최대 값은 4,999,950,000이었습니다.
다행히도 4,999,950,000 > 4,294,977,296이라서 일단 데이터를 만들 수 있는 희망은 보였습니다.
이제 두뇌를 풀가동하여 데이터를 만들어야 합니다.
 

[2. 약수로 접근하기]

먼저 쉬운 방법으로 4,294,977,296의 약수중에 데이터로 만들 수 있는 케이스가 있는지 확인을 해보았습니다.
하지만 슬프게도 (1, 4294977296),  (2, 2147488648),  (4, 1073744324),  (8, 536872162), (16, 268436081)만 존재합니다 😭
N = 100,000이기 때문에 max(arr) = 100,000이라서 arr[x] = 16, arr[y] = 268,436,081로 나오는 데이터를 만들 수 없었습니다.
 

[3. 오버플로우에 근접하는 값 찾기]

2번 방법이 실패했으니 이제 정말 머리를 사용해서 데이터를 만들어야 합니다.
 
매우 깊은 고민을 한 결과 현재 4,294,977,296으로 한 번에 만드는 데이터는 만들 수 없으니 2개 이상의 값을 서로 더하여 4,294,977,294을 만들어야 했습니다.
그래서 간단하게 X + Y = 4,294,977,296을 만들 수 있는 경우를 확인해보았습니다.
그러면 총 3단계를 거쳐 데이터를 만들 수 있게 됩니다.
 
[1단계] 4,294,977,296를 넘지 않으면서 근접하는 값 X 찾기
[2단계] X + Y = 4,294,977,296인 Y 구하기
[3단계] 1 이상 N - X 이하 범위에서 Y의 약수가 만들 수 있는 데이터인지 확인하기
 
 
 

[1단계] 4,294,977,296를 넘지 않으면서 근접하는 값 X 찾기
 

해당 코드는 arr[x] = (x를 만들 수 있는 모든 경우의 수)이므로 큰 값을 얻으려면 완전 제곱식인 케이스를 입력값으로 사용하면 됩니다.
 

RESULT = 4294977296

print(max(i for i in range(100001) if i * (i-1) / 2 <= RESULT))

 
위의 코드를 실행하니 4,294,977,296을 넘지 않는 최대값은 x = 92,682였습니다. (92682C2 = 4,294,930,221)
그러면 이제 x = 92,682부터 1씩 줄여나가 확인하면 됩니다.
 
저는 여기서 x = 92,542라는 값을 기준으로 하겠습니다.
 
 

[2단계] X + Y = 4,294,977,296인 Y 구하기

 
x = 92,542
X = x * (x-1) / 2 = 4,281,964,611
Y = 4,294,977,296 - X = 13,002,685
 
N의 범위는 최대 100,000인데, 이미 x = 92,542를 사용했으므로 N을 최대 7458개를 사용해서 Y를 만들 수 있어야합니다.
 

[3단계] 1 이상 N - X 이하 범위에서 Y의 약수가 만들 수 있는 데이터인지 확인하기

 
13,002,685의 약수를 구하면 아래와 같은 쌍이 나옵니다.
(1, 13002685), (5, 2600537), (641, 20285), (3205, 4057)
이중에서 (3205, 4057)은 3205 + 4057 = 7262이므로 7458개보다 적어서 데이터를 만들 수 있게 됩니다.
물론 이 값을 얻기까지 매우 오랜 시간이 걸렸습니다..
 

[마지막] 데이터 만들기

이제 마지막으로 데이터를 만들면 됩니다.
저는 x = 10,000일 때, 즉 arr[10000]인 값에서 오버플로우를 발생하도록 만들었습니다.
그래서 N = 92542 + 3205 + 4057 = 99804이고, A[i]에 들어가는 값은 100을 92542번 출력하고, 20은 3205번 출력하고, 500은 4057번 출력하게 만들었습니다.
이러면 숫자로만 이루어진 약 484KB인 데이터가 만들어집니다.
 
문제를 잘 이해하고 풀었으면 최대한 이해하기 쉽도록 적었는데, 잘 전달이 됐을지 모르겠네요.
 

어쨌든 월파 가신 분도 꽤 어려울 수 있다는 데이터를 내가 만들었따

---

[2] XOR 카드 게임

옛날에 코드포스 문제에서 XOR 연산과 관련된 문제가 많았습니다. 그때마다 XOR가 너무 어려워서 많이 틀렸던 기억이 나는데요. 그걸 생각해보면서 XOR을 알고, 관련 수학 수식을 해석할 수 있는지 물어보는 문제를 만들게 되었습니다.
처음 문제를 만들 때에는 지문에 있는 수학 수식을 해석하도록 문제를 만들었는데, 내부 검수에서 한 분을 제외한 모두에게 어렵다는 평가를 받고, 우테코에서도 몇몇 크루에게 알려주었는데 못풀겠다고 하여 난이도를 여러번 하향시켜서 완성했습니다. 그 과정에서 수학 수식은 아예 삭제해버렸네요. 그랬더니 너무 쉬운 DP로 변해버린.. 🥲
 

참고로 이 문제는 초기에 문제 이름을 뭐로할지 못정했어서 처음에 다빈 게임이라고 적어두었습니다 ㅋㅋ
 
DP 점화식 자체는 포도주 시식, RGB 거리 문제와 비슷한 매우 쉬운 난이도에 속하는 DP 문제입니다.

---

 
 
 

2. 그 외 문제 리뷰

---

[1] 스케이트보드

간단한 계산 문제입니다. 교내 대회를 진행할 때, 많이 틀리신 분들의 코드를 살펴봤는데, 1000byte 이상의 코드를 작성하고 계속 틀리셔서 마음이 아팠습니다 🥲
 

[2] 회장님께 바치는 합성함수

문제 검수할 때에는 수학 수식만 계산하면 끝이라 너무 쉬운게 아닌가... 라는 생각이 들었는데, 수학 수식 계산 + 다양한 경우의 수로 인해 티어가 높아진 것 같네요.
 

[3] 더하기

문제 아이디어가 좋았던 문제입니다.
 

[4] 카더가든

내부 검수 과정에서 캠핑카는 회전할 수 없다는 조건이 적혀있지 않아서 총 10가지 케이스에 대한 2차원 누적합 수식을 적어야하는 역대급 노가다 문제인줄 알았던 문제 🤣 이게 너무 인상 깊었네요
 

[5] 게임

문제에 함수가 많지만 문제를 이해하면 풀만합니다.
저는 SPFA 알고리즘을 BFS스럽게 변형하면 분기처리하기 쉽게 보여서 풀었는데, BFS가 의도한 풀이이고, DP로도 풀 수 있다고 하네요
 

[6] 의리 게임

지문은 굉장히 만만한 문제로 보이지만.. 시간복잡도를 계산해보면 도대체 뭘로 풀어야할까라는 생각이 드는 문제입니다.
정해는 유니온파인드를 사용하여 풀 수 있습니다.
 

[7] 점수 계산하기

LCA + Tree DP = 😇
코드 구현은 못하고, 풀이 증명만 검수했는데, 푸시는 분들은 대단한 것 같습니다.

---

 
 
문제를 만들 때마다 많은 고민을 하게 되는 것 같습니다. 
- 문제 유형이 대중적인가?
- 문제 지문은 간결한가? 사용자가 쉽게 읽고 이해할 수 있는가?
- 문제 데이터는 최선을 다해 만들었나?
 
요즘 협업 프로젝트를 진행할 때, 코드 작성하기 쉬운 길이 있어도 컴포트 존을 벗어나자라고 생각하며 진행하고 있는데, 알고리즘 문제에도 이런 마인드로 만드니 좋은 문제를 만든 것 같네요.
 
특히 이번에는 `난이도가 쉽다`, `많이 틀린다` 이 두 문장은 어떻게보면 모순적으로 보이는데, 난이도가 쉬우면서 많이 틀리는 문제를 만들어서 개인적으로 만족스러웠습니다. 거기다가 오버플로우를 이용해 저격하는 데이터도 만들어서 작년에 비해 성장했다는 느낌이 많이 들었네요.
 
알고리즘 실력이 많이 떨어져서 이제 대회에 나가도 성과를 낼 수 없어서 아쉬웠는데, 이렇게 문제 출제, 검수할 수 있는 기회가 있어서 좋았습니다.