One, Two, Three 출제 후기

2024년 1월 2일에 군대를 가게 되었다. 군대에 가게 되면 대학생이 아니게 되니 대학생 대회들에 멋진 문제를 내서 대학생들에게 풀리겠다는 생각으로 훈련소와 후반기 교육을 하면서 문제들을 만들게 되었다.

 

One Two Three는 ainta님의 문제 스타일에 영향을 받은 문제이다. 신탁, 하나 둘 셋, 점 연결하기, comparing plants를 풀면서 인위적이지 않은 설정들에서 재미있는 관찰들을 추가하면서 문제를 풀어나가는 것이 재미있었다. 특히 신탁이라는 문제를 풀면서 하나의 시행을 다양하게 변환하면서 점점 문제를 풀어나가는 과정이 인상깊었다. 그래서 나도 ainta님처럼 간결한 문제를 만들고 싶었다.

 

점 연결하기, 돌 가져가기 문제들을 보면 길이 N의 수열을 주고 적당한 시행을 줘서 문제를 완성시킨다. 오랜 시간 나의 문제 출제거리에 들어갔던 사과게임을 여기에 적용하기로 했다.

사과게임은 사과의 합이 10인 직사각형을 제거하는 것을 반복하는 게임이다

 

아래는 처음에 만든 문제의 형식이다.

 

길이 N의 수열 A가 주어진다. 각 원소는 1 이상 K 이하의 수이며, 구간의 합이 p가 된다면 해당 구간을 지울 수 있다.

 

원래 사과게임은 2차원에서 진행되지만, 2차원에서 문제를 만들었다가는 절대 못 풀 것 같아서 1차원으로 만들었다.

이제 K와 p를 정하기로 했다. (K, p)=(2, 3)일 때에는 문제가 너무 쉬웠다. (K, p)=(3, 4)로 하니까 약간의 관찰들을 할 수 있었다.

 

1. 1과 3이 인접해있다면 제거하는 것이 이득이다.

2. 2와 2가 인접해있다면 제거하는 것이 이득이다.

 

하지만 이러한 관찰들을 하다 보니 1111233332111123332...와 같은 형태로 환원이 되었고, 여기에서 냅색이 추가되지 않으면 풀리지 않을 것처럼 생겼다. (Challenge: 이 문제를 풀어보자) 보통 문제가 냅색으로 가면 안 풀렸기 때문에 나는 문제를 살짝 틀기로 했다. 그래서 p에 8을 추가하기로 했다. 이러면 무엇이 좋냐 하면 233을 제거할 수 있다는 것이 좋았다. 

 

13을 제거하는 것이 좋고, 233을 제거하는 것이 좋다는 것을 보니 1, 2와 3의 매칭 문제처럼 생겼다. 매칭의 아이디어를 가지고 제거할 수 있는 구간에 대한 관찰을 한 결과, dp 풀이가 완성되었다!

 

제거할 수 있는 구간이라는 키워드는 신탁이라는 문제에서 따온 것이다. 신탁의 풀이를 비교해보자.

https://www.acmicpc.net/problem/18343 (신탁 링크)

 

(풀이 스포선)

-----------------------------------------------------------------------------------------------------------------------------------------------------------------

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

신탁: 특정 원소로 신탁을 해석하고 싶다고 하자. 원소보다 큰 값들은 +, 작은 값들은 -, 해당 원소는 0으로 두자. (같은 원소가 여러 개 있을 때는 eps를 더해서 모든 원소 값을 다르게 한다) +와 -가 섞여있는 구간에 중앙값 시행을 하면 +와 -중 더 많은 값으로 바뀐다. +, -, 0이 섞여있는 구간에 중앙값 시행을 했을 때에는 +와 -의 개수가 같아야 한다.

 

중앙값 시행은 다음 2개의 시행으로 쪼갤 수 있다.

 

1. 같은 값 3개를 하나로 바꿈 (+++ -> +, --- => -)

2. +와 -를 합쳐서 없앤다

3. 0의 양옆에 있는 +와 -를 제거한다.

 

이에 대한 증명은 생략한다. 이제 3번 시행을 제거해보자.

 

최종적으로 배열을 0으로 만드는 시행들을 나열해보자. 이중 3번 시행을 제거하면 0을 기준으로 대칭인 배열이 된다. (대칭이란, 왼쪽에 있던 +가 오른쪽에서 -로 나타나는 것이다. 예를 들어서 ++-0+--와 같은 것이다.)

 

하지만 2번 시행을 사용해서 0을 기준으로 같은 쪽에 있는 +와 -를 제거해주면 한쪽에 +만 남고 다른 쪽에 -만 남는 배열이 된다. 이때 +와 - 개수가 같다.

 

따라서 우리는 0을 기준으로 왼쪽/오른쪽에 +와 -를 몇 개 남길 수 있는지 알아야 한다. 1번 시행에 의해 여러 개의 +는 1개 혹은 2개의 +로 바꿀 수 있기 때문에 그 개수는 중요하지 않고, (1) +로 남길 수 있는지, (2) 0으로 남길 수 있는지, (3) -로 남길 수 있는지 여부가 중요하다. (1)만 해결해보자.

 

+로 치환할 수 있는 구간은 +를 1, -를 -1로 치환했을 때 합이 1 이상의 홀수인 구간이다. 자세한 증명은 생략한다.

 

따라서 이를 사용해서 dp를 돌릴 수 있고, 이러면 11점짜리 O(N^2logN) 풀이가 나온다. 관찰을 더 하면 O(NlogN)까지 가지만 여기서부터는 풀이 라인이 달라진다.

 

 

 

One, Two, Three에서 O(NlogN) dp까지 생각한 이후에는 신탁의 풀이 빌드업을 따라가서 쿼리를 추가하고 싶었지만 아쉽게도 쿼리로 이어지는 관찰을 하지 못했다. 하지만 O(N)에 문제를 풀 수 있는 방법을 찾았고, 나름 만족스러운 풀이였기에 출제를 했다. 하지만 O(NlogN)에 뚫려버렸고, O(N) 풀이는 미래 내 개인문제로 만날 수 있게 되었다.

 

재미있는 애드혹 문제를 출제해서 만족스럽다. 앞으로도 더 재미있는 문제들을 만들어서 대학 대회들에 내고 싶다!