2025 KSA Automata Winter Contest 후기

2등했다.

작년에는 좀 망쳤던거같은데, 올해는 잘 쳐서 좋다. G에서 좀 심하게 말렸는데, 나만 그런건 아닌 것 같아서 신경쓰지 않기로 했다.

 

풀이

내가 푼 것만 있다. (A에서 H)

I와 J는 업솔빙 이후 정리할 예정이다.

A. 아름다운 수열

상당히 비직관적인 관찰을 요구하며, 증명도 어렵다. 다음 관찰이 핵심이다.

• $i$번째 원소가 $i$인 수열은 문제에서 제시된 조건을 모두 만족한다.

증명이 굉장히 재미있는데, 여백이 부족하여 여기에는 적지 않겠다.

B. 저녁 태권도

각 학생이 정확히 한 날짜를 제외하고 모든 태권도에 참여해야 한다는 것을 알 수 있다.

결국 중요한 것은 $i$일에 참여해야 하는 학생의 최소 명수인 $A_i+B_i$이다. 아침, 저녁에 상관없이, 이 조건을 만족하도록 모든 학생을 각 날짜에 배정했다 하자. 그러면 각 $i$일에 대해 해당 일자에 배정된 $A_i+B_i$명의 학생 중 $A_i$명을 아침에 배정하고, 나머지를 저녁에 배정한다면 문제에서 주어진 조건을 만족한다.

방법은 여러가지가 있겠지만, 나의 경우 $1$일부터 순서대로 보면서 각 일자에 태권도에 참여할 사람을 고르는 방법을 사용했다. $i$번째 일자에는 현재 태권도에 참여한 횟수가 가장 작은 $A_i+B_i$명을 $i$일에 배정시키면 된다. 위 과정이 모두 끝났을 때, 참여 일자가 부족한 학생들에 대해 참여하지 않은 아무 일자에 참여시켜 횟수를 채워주면 된다.

C. 미술 수업

주어진 직선들은 전부 $y=(x-a)$꼴이거나 $y=-(x-b)$꼴이다. 이에 해당하는 $a$와 $b$를 전부 모아주고, 중복된 것은 제거해주자. ($(x, y)$가 주어졌을 때, $a=x-y$인 직선과 $b=x+y$인 직선이 하나 만들어진다)

교점들은 다음과 같이 분류할 수 있다.

• $x$축과 다른 직선간의 교점
• $y=(x-a)$꼴의 직선과, $y=-(x-b)$꼴의 직선 간의 교점

전자의 경우, 앞서 구한 $a$와 $b$들의 합집합 크기가 된다.

후자의 경우, 각 $a$에 대해 교점이 있는 $b$의 조건은 $a < b$인 것이다. ($a=b$인 경우는 전자에 해당하므로 제외한다)

그래서, 각 $a$에 대해 자신보다 큰 $b$의 개수를 구해주면 되는데, 이분탐색, 투 포인터 등 여러 방법이 다 가능하다.

D. KSA 문자열 2

주어진 문자열이 몇 개의 K, S, A 문자로 이루어져 있는지 각각 구하면 만들 수 있는 KSA 문자열의 최대 길이를 구할 수 있다.

이제 연산 횟수를 최소화해야 하는데, 연산을 통해 결과 문자열을 완성했을 때, 한 번도 연산에 사용되지 않은 문자열들을 생각해보면, 이들은 결과 문자열의 suffix임을 알 수 있다.

이에 해당하지 않는 문자들은 전부 제거되거나, 연산에 의해 맨 앞으로 이동되었을 것이므로, 결국 문제는 다음과 같다.

• 주어진 문자열을 $s$, 결과 문자열을 $t$라 하자. $t$의 suffix 중 $s$의 substring인 것의 최대 길이를 구하라.

이는 $t$의 길이 $i$의 suffix를 포함하는 $s$의 suffix의 최소 길이를 $i$의 증가에 따라 관리하는 것으로 풀 수 있다.

E. 수열의 점수

일단 $X$나 $Y$가 1인 경우를 예외처리해주자.

우선 $A_i=A_{i-2} - A_{i-1}$이므로, $A_{i-2}=A_{i-1}+A_i$이다.

즉, 수열의 점수가 $k>2$라 할 때 $A_k, A_{k-1}, \cdots, A_1$은 초항이 $A_k$와 $A_{k-1}$인 피보나치 수열이라는 것이다.

$A_{k-1}=a, A_k=-b$라 하자. 수열의 점수 $k$의 정의에 의해 $a>0, b \le 0$이다. 또한, $A_{k-2}=a-b$이므로 $a>b$이다.

또한, $F_i$를 초항이 $0, 1$인 피보나치 수열이라 하자. 그러면 다음이 성립한다.

• $A_{k-i} = aF_i - bF_{i-1}$

만약 한 수열이 수열의 점수가 $k$라 하자. 그럼 만약 $a$를 1로 바꾸고, $b$를 0으로 바꾸게 된다면 $a>b$이므로 $A_1, A_2$의 값이 모두 감소하게 된다.

즉, 수열의 점수가 $k$인지 확인하려면 $a=1, b=0$으로 놓고 길이 $k$의 수열을 끝에서부터 만들어서 $A_1 \le X, A_2 \le Y$인지만 확인하면 된다는 것이다. 즉, 피보나치 수열의 $k$번째 항이 $X$이하이며 $k-1$번째 항이 $Y$ 이하라면 수열의 점수가 $k$인 수열이 존재한다는 것이다.

F. 멀티버스를 여행하는 한별이를 위한 안내서

필자의 정수론적 지식이 부족한 관계로 증명은 생략한다. 기본적인 발상은 오일러 정리이다.

다음과 같은 경우로 나눠 생각한다.

1. $K$가 2, 5를 모두 인수로 가짐

조건을 만족하는 $(a, b)$는 $(0, 1), (1, 2), \cdots, (8, 9)$ 중 하나이다. 이를 이분탐색으로 찾으면 된다.

총 4회의 쿼리가 소요된다.

2. $K$가 2를 인수로 갖고, 5는 가지지 않음

이 경우, $(10, \phi(5^8)+10)$을 쿼리로 날렸을 때 답이 YES이다.

다음 조건을 만족하는 $(a, b)$ 중 하나가 답이다.

• $1 \le a \le 8$
• $d=b-a$라 하면, $d | 2^2 \cdot 5^7 = \phi(5^8)$

$a$와 $d$를 각각 이분탐색으로 찾으면 된다.

$a$의 경우, 후보는 8가지이므로 3회의 쿼리가 필요하다.

$d$의 경우, 2의 지수와 5의 지수로 분리하여 생각한다. 2의 지수는 $[0, 2]$가 모두 될 수 있으므로, 2회의 쿼리가 필요하다. 5의 지수는 $[0, 7]$이 모두 될 수 있으므로, 3회의 쿼리가 필요하다.

최악의 경우 총 8회의 쿼리가 필요하다.

3. $K$가 5를 인수로 갖고, 2는 가지지 않음

이 경우, $(10, \phi(2^8)+10)$을 쿼리로 날렸을 때 답이 YES이다.

다음 조건을 만족하는 $(a, b)$ 중 하나가 답이다.

• $1 \le a \le 8$
• $d=b-a$라 하면, $d | 2^7 = \phi(2^8)$

2와 같은 방식으로 탐색하면 총 6회의 쿼리가 필요하다.

4. $K$가 10과 서로소임

이 경우, $(1, \phi(10^8))$을 쿼리로 날렸을 때 답이 YES이다.

조건을 만족하는 $a$는 항상 $1$이고, $b$는 $\phi(10^8)$의 약수이다.

따라서 앞선 방식과 같이 이분탐색을 통해 찾으면 최대 7회의 쿼리가 필요하다.

 

이제 목표는 위 네 가지 상황 중 어디에 해당하는지 알아내고, 각각에 맞는 쿼리를 날려 답을 알아내면 된다.

순서를 잘 조정해야 $Q=10$이라는 제한을 만족시킬 수 있다.

우선 4에 속하는 경우인지부터 걸러내고, 그 다음에 2에 해당하는 경우, 이후 1과 3 중 어디에 해당하는지 알아내면 $10$회 이하의 질문으로 풀 수 있다.

G. 자습 째기

답으로 가능한 수는 suffix에 해당된다. 따라서 $x$를 고정하고 결정 문제를 푼 후, 이분 탐색을 적용할 수 있다.

우선 우리의 목표는 후반 $N-x$일 중 감시가 없는 날의 수를 최대화하는 것이다.

 

다음과 같은 간단한 관찰이 있다.

관찰 1. 가능한 연산의 횟수($A$)를 1회 늘릴때마다 답(감시가 없는 날의 수의 최댓값)은 최대 1 증가한다는 것이다.

 

각 교사 $i$에 대해 $cnt_i$를 교사 $i$가 총 몇 번 감시를 하는지로 정의하자. 이때, 만약 첫 $x$일에 $c_i$번 초과로 감시를 했다면, 이로 인해 감시가 되지 않은 날은 세지 않는다. 보다 엄밀하게 하자면, 다음과 같다.

$cnt_i$는 다음과 같은 $j$의 개수이다.

• $j \le x$, $t_j=i$, $t_1, t_2, \cdots, t_{j-1}$에서 $i$는 $c_i$번 미만 등장했다.
• $j > x$, $t_j=i$

한 최적해에서, 집합 $S$를 후반 $N-x$일 중 감시가 없는 모든 날에 대하여, 해당 날에 배정된 교사들의 집합이라 하자.

초기 상태의 $t$에서 $A$번의 변경을 통해 최적해를 만드는 과정을 생각해보자. 또한, 여기서 "최적해"는 답(감시가 없는 날의 수의 최댓값) 을 최대한 증가시키면서, 연산의 횟수를 최소화하는 것으로 생각하자.

 

우선, $S$의 한 원소 $i$에 대해 $t$의 첫 $x$개 원소에서 $i$가 $c_i$번 초과로 등장한다면, $c_i$개의 인덱스만 남겨두고 전부 $0$으로 바꿔주자. (사실 이렇게 하면 $t$에서 $i$의 등장횟수가 $cnt_i$가 된다)

 

관찰 2. 최적해의 $t$의 첫 $x$개의 원소만을 볼 때, 다음을 만족한다.

• 모든 교사 $i$에 대하여 $t_j=i$인 $j \le x$는 최대 $c_i$개 있다.

만약 $c_i$회 초과로 등장하는 $i$가 있다면, 해당 위치에 대한 연산을 롤백시켜도 답은 감소하지 않는다. 왜냐하면 롤백하더라도 첫 $x$개의 원소에서 $c_i$번 등장했으므로, 후반 $N-x$일에 이 교사가 할당된 모든 날에는 감시가 없기 때문이다.

 

관찰 3. $t$에서 $S$의 원소였던 값을 다른 값으로 바꾸는 것은 최적이 아니다.

일반성을 잃지 않고 최적해에서 해당 연산을 가장 마지막 연산으로 했다고 가정하고, 연산을 통해 답이 증가하게 되었다 가정하자.

$t_i=a$를 $b$로 바꾼 상황을 살펴보자. $b$가 $S$의 원소가 아니라면 감시가 없는 날이 추가로 생겨나지 않을 것이므로, $b \in S$라 할 수 있다. 그런데, $a$는 현재 답에 양수의 기여를 하고 있다. (마지막 연산인 $a$를 $b$로 바꾼 것이 최적해이므로 이를 하기 전에도 답에 양수의 기여를 하고 있다고 생각할 수 있다) 만약 $i$가 $t_j=a$인 $j$들 중 가장 작은 $c_a$개 중 하나일 경우, 이를 제거하면 교사 $a$가 할당된 날 중 $c_i +1$번째 날은 $c_i$번째가 된다. 관찰 2에 의해 이 날은 $x+1$일 이후이고, 따라서 답이 1 줄어든다. 그렇지 않다면, $i$일은 이미 감시가 없던 날이었으니, 이 날에 배정된 교사가 변하더라도 답은 증가하지 않는다.

 

관찰 4. $i \in S$인 모든 $i$에 대해 $\max \{ cnt_i -c_i, 0 \}$합은 $A$보다 작거나 같다.

결국 $cnt_i$가 $c_i$이하면 $i$는 답에 기여하지 않기 때문에 $i$가 답에 기여할 때 $cnt_i-c_i$가 양수라면 이 횟수만큼 연산이 필요하다.

 

관찰 5. 답은 $N-\sum_{i \in S}{c_i}$를 넘을 수 없다.

이는 쉽다. 각 $i$에 대해 $i \in S$면 교사 $i$가 배정되어 있으면서 감시가 없는 날이 존재하는데, 감시가 없는 날의 수(답)와 $c_i$의 합은 $N$ 이하이다. 식을 정리하면 위 값을 얻는다.

 

관찰 6. 답은 $\min \{ N-x, N-\sum_{i \in S}{c_i}, \sum_{i \in S}(cnt_i-c_i)+A \}$이다.

약간의 디테일이 생략되어 있다.

만약 $cnt_i \le c_i$인 $i$가 존재한다 하자. 그렇다면 적당한 $t$값을 $i$로 바꾸는 것으로 답을 증가시킬 수 있다. 증가시킬 수 없는 경우는 이미 답이 $N-x$인 경우밖에 없다.

 

관찰 7. $S$에 $cnt_i<c_i$인 $i$는 최대 하나이다.

여러 개 있다면 하나 빼고 다 빼는 것이 답을 단조증가시킨다.

 

이제 결정 문제를 풀자. 감시가 없는 날, 즉 답은 $N-x-B$ 이상이어야 한다. 따라서 $\sum_{i \in S}{c_i} \le x+B$여야 한다. 따라서 문제는 $\sum_{i \in S}{c_i} \le x+B$이고, $\max \{ cnt_i -c_i, 0 \} \le A$인 모든 집합 $S$에 대해 $ \sum_{i \in S}(cnt_i-c_i)+A$를 최대화시키고, 이 값이 $N-x-B$ 이상인지 묻는 문제가 된다. $cnt_i-c_i$의 부호를 바탕으로 모든 교사를 분류해 주고, 양수인 것들로 knapsack을 돌린다. 이후 음수인 교사가 없을 때, 한 명 있을때를 다 봐서 하나라도 조건을 만족하는 경우가 있는지 검사해 주면 된다.

 

다 쓰고 보니 좀 두서없이 쓴 것 같은데, 에디토리얼이 올라오면 그것을 보는게 나을 것 같다는 생각이 든다.

 

H. 쿠키 공장

$s$ 오름차순대로 쿠키를 만든다고 가정해도 무방하다. 쿠키 주문을 $s$ 순으로 정렬하고, 다음 값을 관리하는 세그트리를 만들면 된다.

• 구간의 첫 번째 주문의 $s$값
• 구간에 있는 모든 주문을 다 처리했을 때, 마지막으로 쿠키를 만든 시간
• 구간 내에서 주문이 들어온 총 쿠키의 개수 ($c$값의 합)

그렇게 자명하지는 않지만, 주문의 순서관계가 있기에 두 노드를 합칠 수 있다.

 

문제는 $s$도 쿼리에 의해 변한다는 것인데, 결국 중요한 것은 각 $s$에 대한 쿠키 주문의 $c$ 합이기에, 쿼리로 들어올 $s$들을 모두 다 모아 좌표압축해주면 풀 수 있다.

타임라인

0:00 ~ 0:00 (48초) / 100점

푼 문제: A

A를 읽고 바로 풀었다. $i$번째 원소를 $i$로 하는 수열을 찍는다는 것은 거의 바로 떠올라서 짰는데, 3초 차이로 퍼솔을 놓쳤다.

출제진분에게 듣기로는 퍼솔이 파이썬 코드인데, 아래와 같이 정말 쉽게 짤 수 있다.

print(*range(1, n+1))

이걸 어떻게 이겨...

0:00 ~ 0:08 / 200점

푼 문제: A, D

스코어보드에서 A 퍼솔을 놓친것을 확인했고, 억울해서 다른 문제 퍼솔을 노리려고 했다. E는 뭔가 수학 느낌이라 못 할거같았고, 그래서 D를 골라서 풀었다.

잠이 덜 깨서 그런지 코딩이 좀 오래 걸렸는데, 운이 좋게 퍼솔할 수 있었다. (D부터 잡으신 분들이 그렇게 많지도 않은 것 같았다)

0:08 ~ 0:27 / 400점

푼 문제: A-D

F는 아예 정수론 문제여서 내가 퍼솔을 못 할 것 같았고, 그래서 그냥 앞에서부터 풀기로 했다.

B는 좀 뇌절을 많이 했다. 이거 유량 아님? 하다가 시간을 많이 버린 것 같다.

C는 코딩에서 실수해서 한번 틀리고 맞았다.

0:27 ~ 1:14 / 600점

푼 문제: A-F

E와 F를 풀었다. E는 관찰과 코딩 모두 금방 했는데, F는 좀 말렸다.

고등학교 때 배웠던 온갖 정수론 지식을 다 가져와서 풀었다.

Decision tree를 잘 조정하면 쿼리 횟수가 딱 10이 나오는데, 깔끔한 문제인 것 같다.

1:14 ~ 2:51 / 600점

푼 문제: A-F

G를 쭉 생각했다. 온갖 접근은 다 해봤는데, 결국 올바를 것으로 추정되는 풀이를 찾을 수 있었다.

풀이의 골자를 찾는데는 그리 시간이 걸리지는 않았는데, 코딩이 좀 오래 걸렸다. 코딩하는 동안 풀이의 반례와 예외가 여러가지 생각났고, 고치는데 좀 오래 걸렸다.

그런데 제출하니 RE가 떴다.

2:51 ~ 4:13 / 700점

푼 문제: A-F, H

처음엔 G를 계속 디버깅했다. 내가 놓친 부분이 좀 있어서 그걸 다 고쳤고, 그랬더니 또 틀려서 코드에 assert()문을 넣어서 이분탐색을 하니 틀린 이유를 알 수 있었다. 이후, 어디가 틀렸는지 모르겠어서 제너레이터, 체커를 만들고 스트레스를 돌렸다. 30분에 하나 꼴로 코드의 틀린 점을 찾을 수 있었다.

 

3시간 50분쯤 스코어보드를 봤는데, G가 솔브가 없고 H가 많이 풀려 있어서 잠깐 H를 보고 오기로 했다. H는 그냥 쉬운 문제였고, 짜서 맞았다.

4:13 ~ 4:54 / 800점

푼 문제: A-H

대회가 끝나기 8분 전, 드디어 G의 반례 데이터를 찾았다. 디버깅은 별로 어렵지 않았고, 오류를 수정하니 드디어 맞았다.

4:54 ~ 4:57 / 803점

푼 문제: A-H, I(3점)

남은 문제는 I와 J였고, 내가 할 수 있는게 무엇이 있나 생각해보다가, 바로 풀리는 I에 서브태스크가 하나 있길래 긁었다.

그냥 이중포문 돌리면 되는 서브태스크였는데, 스코어보드를 본다면 알겠지만 이 3점을 획득함과 동시에 등수가 6등에서 2등으로 상승했다.

4:57 ~ 5:00 / 803점

푼 문제: A-H, I(3점)

또 할게 더 있나 봤는데, I의 21점 서브태스크도 쉽다는 것을 바로 발견했다. 그냥 레이지세그를 쓰면 되는데, 이걸 3분만에 코딩하는 것은 불가능하기에(적어도 나에게는) 그냥 끄기로 했다.