문제 출제하기

오늘은 여태까지 출제한 문제들에 대해서 문제 출제 과정을 알아볼 것이다. 고등학생 때 플래티넘 열심히 풀던 시절에 문제를 만들고 싶었지만 문제를 하나도 만들지 못했던 과거의 나를 생각해보면 처음 문제 만드는 것이 가장 어려운 것 같다. 그래서 문제를 처음 만드는 사람들에게 조금이나마 도움이 되고자 내가 문제를 만들었을 때 어떠한 방식으로 문제를 만들게 되었는지 써보겠다! 옛날에 만들어서 조금 까먹었을지도... 최신순으로 적어보자.

 

카이스트 가을대회

이때 4문제 냈다. 각각 어떻게 풀었는지 적어보자.

1. HLD

이 문제는 Heavy Light Decomposition 이라는 알고리즘에 대해서 생각하다가 나온 문제이다. HLD는 트리를 여러 개의 체인으로 쪼개서 하나의 path 최대 2logN개의 체인으로 쪼개지는 알고리즘이다. 이때 체인을 서브트리가 가장 큰 자식 쪽으로 이어주는데, 이것은 가능한 모든 path에 대해서 쪼개지는 체인의 개수를 bound 시켜주는 방법이고, path가 몇 개 주어졌을 때 더 좋은 체인을 만드는 방식이 있는지 궁금해서 만들었다. 처음에는 한 번에 한 개의 path를 추가시켜주는 방식으로 해서 bound를 관찰하려고 했으나, 여러 개의 path를 주어도 문제가 풀린다는 것을 알아서 한 번에 여러 개의 path를 주는 것으로 문제를 변경했다. 이렇게 하면 데이터 만들기가 더 쉽다.

2. Good Triangle

이 문제는 옛날에 고등학생 때 만들었다. 그냥 문제를 만들고 나니까 재미있게 풀려서 냈다. 어떻게 만들었는지는 다 까먹었다. 

3. Simple Link Cut Problem

이 문제도 옛날에 만들었던 문제를 어렵게 한 것이다. 그래서 어떻게 만들었는지 기억이 안 난다.

4. Swapping Brackets

이 문제는 원래 두 괄호 i, j를 swap할 때 필요한 비용이 f(i, j)일 때 올바른 괄호문자열로 만드는 데 필요한 최소 비용을 구하시오. 와 같은 문제가 될 예정이었다. f(i, j)를 여러 가지 방식으로 주어보았는데, min(A[i], A[j])라던가 A[i]+A[j]라던가 다양한 시도가 있었다. 하지만 이런 경우에는 안 풀리거나 너무 쉽게 풀렸다. 그러다가 JOI 국가의 행사 처럼 'A[i]가 얼마 이하인 괄호들만 바꿀 수 있다'라는 조건을 추가해보기로 했다. 그랬더니 열린 괄호들은 모두 앞으로 가고 닫힌 괄호들은 모두 뒤로 가야 한다는 성질을 발견했고, 몇 개의 열린 괄호들과 닫힌 괄호들만 swap하면 된다는 것을 관찰했다. 관찰하고 나니까 dp를 얹어서 현재의 문제가 적당히 풀릴 것 같다는 생각을 했고, 처음에 세제곱으로 문제를 냈다. 약간의 식정리를 하면 제곱이 될 것 같아서 제곱에 풀었다.

 

카이스트 봄 대회

이 때에도 4문제를 냈다.

1. Simple Game

이 문제도 옛날에 만들어서 어떻게 만들었는지 까먹었다.

2. Monochrome tree

이 문제도 옛날에 만들었다. 그래서 어떻게 만들었는지 까먹었지만 대충 예상을 해보자면 tree에 inversion counting을 섞은 것이 아닐까 싶다. 참고로 이 문제는 최소값을 구하는 문제이지만, 최대값을 구하는 문제도 열심히 풀었지만 그리디는 성립 안 하고 이상한 knapsack dp쪽으로 흘러서 출제하지 못했다.

3. Merging Branches

이 문제는 급하게 만들었다. 구간이 N개 만들면 보통 어떻게든 문제가 만들어지기 때문에 구간을 N개 잡고 시작했다. 중간에 많은 과정이 기억이 안 나지만, even split이라는 문제의 풀이와 비슷하게 풀려서 출제했다.

4. Binary Sequence and Queries

원래는 이런 자구비빔밥이 아니었고 쿼리가 없는 상태에서 신기한 수학적 관찰로도 풀리는 문제였다. (실제로는 다양한 방법으로 풀린다.) 그래서 별볼일 없는 문제였는데 SongC가 쿼리를 넣어보자고 해서 넣어보았다. 섭태 3이 원래 문제였는데 어쩌다보니 쿼리를 한 개 더 추가하게 되었다. 이런 문제는 보통 자료구조 근육이 있으면 잘 만들 수 있다. '관찰을 하고 그 관찰을 토대로 세그먼트 트리에 잘 비비기'의 전형적인 쿼리 문제 풀이를 따라간다.

 

SUAPC 2023 Winter

여기에는 2문제 냈다.

1. 좋은 문자열 만들기

코드포스 출제 과정에서 내가 만든 div2B가 마음에 안 들어서 새로운 문제로 교체하려고 했지만 반려당했다. 반려당한 문제 중 하나가 이 문제이다. 이 문제도 굉장히 전형적인 코드포스 문제이다. 어떠한 시행을 정의하고, 좋은 상태를 정의하고, 시행을 최소 개수로 해서 좋은 상태로 만드는 것이다. 이번에 카이스트 가을대회에 나온 Irreducible permutation과 비슷한 유형이다. 원래는 prefix sum으로 적당히 풀리는 문제인데, 나중에 알고보니 답이 2 이하가 되어서 조금 다른 맛의 문제로 변했다.

2. Azber is playing at biou's house

흔한 dp 문제이다. 어떻게 만들었는지 기억이 잘 안 난다.

Codeforces Round 851

6문제 셋이다. 여기 문제들도 옛날에 만들어서 기억이 잘 안 난다.

1. One and Two

수열의 원소를 작게 제한하고 문제를 만들면 엄청 쉬운 문제가 되는 경우들이 있다. 작정하고 쉽게 만든 문제라서 2의 개수만 세도 된다는 것을 아이디어라고 하고 냈다. 좋은 문제는 아니라고 생각한다.

2. Sum of Two Numbers

이 문제는 예전에 투어리스트가 만들었던 "1과 0으로만 이루어진 수를 더해서 N을 만들고자 할 때 필요한 최소 개수의 수"와 비슷한 아이디어로 생긴 문제이다. '덧셈' 그리고 '해 구성하기'로 문제를 만들고 싶어서 자릿수 합으로 문제를 만들었다. 해 구성하기 문제의 경우에는 문제에 조건을 더 추가해서 푸는 경우가 대부분이다. 나는 여기에 '받아올림이 없다'라는 조건을 추가하면 문제가 쉽게 풀린다는 것을 착안해서 div2A로 냈다. 나중에 div2B로 올라갔다.

3. Matching Numbers

이것은 https://www.acmicpc.net/problem/22357 를 풀다가 생긴 문제이다. 틀린 풀이의 방향 중 어쩌다 보니 저런 일을 하는 경우가 생겨서 문제로 기록해두었다.

4. Moving Dots

앳코더에 보면 가능한 모든 2^N가지에 대해서 특정 수의 합을 구하시오. 와 같은 문제들이 자주 나온다. 나도 이런 문제를 만들고 싶어서 별의별 상황에 대해서 2^N가지에 대해서 합을 구하는 문제를 만들어보았다. 하지만 대부분 굉장히 자명하거나 안 풀리는 문제로 나왔고, 어쩌다보니 이렇게 운이 좋게 moving dots라는 문제가 나오게 되었다. 요즘에도 저런 템플릿으로 문제를 만들어보고 싶은데 안 나온다.

5. Sum over Zero

이건 dp 문제를 만들었는데 제곱 밑으로 안 떨어지길래 blackking26한테 풀어달라고 했더니 셋을 사용한 dp로 풀어주었다. 지금 보니까 그냥 세그먼트 트리 dp 문제였고 만약 지금 이런 문제를 만들었다면 출제하지 않았을 것이다. 하지만 div2E의 난이도로는 좋은 문제인 것 같다.

6. XOR, Tree and Queries

비슷한 문제를 어디선가 보고 비슷한 생각이 나서 출제한 것 같다. xor이 가장 작아야 한다는 조건은 문제를 다 만들고 나서 너무 흔한 문제 같아서 마지막에 추가했다. 나름 재미있게 풀리는 것 같다.

 

이제부터는 그냥 기억나는대로 적겠다.

1. 오렌지 섬 여행하기

심층 문제 풀다가 페리 수열을 접했고 이것을 해 구성하기 문제로 만들면 어떨까해서 출제했다. 엄청 뚫렸다 ㅜㅜ

2. 이차함수와 직선

'이차함수를 그렸을 때 사이로 직선 그리기'라는 컨셉으로 시작한 문제이다. 원래는 사이로 그릴 수 있는 직선의 기울기 범위 구하는 문제였는데, 삼분탐색으로 하면 너무 쉽게 풀려서 좀 더 맛있게 만들고 싶었다. 그러다가 직선을 그릴 수 없는 경우에는 이차함수 3개만 있으면 된다는 것을 관찰했고, 그대로 문제로 냈다. 어쩌다 보니 구현이 더러워졌다.

3. Polynomial and Easy Queries

'세그먼트 트리에서 교환법칙이 성립하는 쿼리는 레이지로 쉽게 처리할 수 있다'라는 생각이 들어서 만든 문제이다. 교환법칙이 성립하는 함수를 인터넷으로 검색해서 만들었다. 보통의 ps 문제와는 다른 결이 느껴진다.

 

옛날에 만든 문제들이 지금보다 더 신기한 것 같다. 요즘은 무난한 문제들을 만든다고 하면, 옛날에는 이런 것이 왜 문제가 될 수 있지 싶은 문제들이 많다. 트리 정리하기 같은 문제들이 그런 편에 속한다. 

마지막으로 문제 만들면서 있었던 일에 대해서 말을 하자면, 풀리지 못한 문제들이 출제된 문제들보다 훨씬 더 많다는 것이다. 그렇기 때문에 문제가 안 풀리거나 너무 자명하게 풀리면 조금씩 조건을 수정해서 풀리는 문제로 만드는 것이 좋은 방식인 것 같다. 지금 내 문제 모음집에 자명한 문제 절반 풀리지 않은 문제 절반해서 문제들이 쌓여있다... 나는 어쩌다가 운이 좋으면 문제가 만들어진다고 생각하다. 문제가 안 만들어진다고 너무 상심하지 말자.