2024 IOI 멘토교육 1주차

IOI 2021 Day 2를 돌았다.

0:00~0:14 (100점)

1번 문제를 읽었다. 한 눈에 풀이가 바로 보여서 2, 3번을 읽지 않고 바로 구현해서 맞았다.

주어진 구간에서 A, T, C의 개수가 다르면 답이 -1이고, 같으면 답을 (2개씩 바뀌어 있는 개수)+(3개씩 바뀌어 있는 개수)*2로 계산할 수 있다.  a에서 A, T, C인 자리와 b에서 A, T, C인 자리를 각각 누적합으로 계산해놓으면 된다.

0:14~0:52 (111점)

2, 3번 문제를 읽었다. 두 문제 모두 전체 풀이는 감이 오지 않았다. 2번은 섭테가 많아서 최대한 긁어야겠다고 생각했고, 3번은 수학적인 관찰이 필요해보였다.

일단 2번 문제의 1번 섭테를 긁었다. 각 쿼리 별로 나이브하게 돌아도 시간복잡도가 최대 $O(Qmax(s_i))$이기 때문에 그냥 해도 된다.

0:52~1:12 (124점)

2번 문제의 3번 섭테를 긁었다. 모든 s_i가 같기 때문에 계속 지다가 어느 순간부터 이기게 된다는 것이 자명하다. 따라서 희소 테이블로 각 위치별로 계속 진다고 가정했을 때 도달하는 위치와 그때까지 더해지는 힘의 합을 구해 놓으면 처음으로 이기게 되는 순간을 로그 시간복잡도로 계산할 수 있다. 처음으로 이기게 되는 순간 이후의 동작은 DP로 미리 구해 놓을 수 있다. $D_i$를 i에서 출발해서 계속 이긴다고 가정했을 때 최종적으로 더해지는 힘의 합이라고 정의하면 i를 N-1부터 0까지 돌리면서 $D_i=D_{l_i}+s_i$로 계산할 수 있다.

1:12 ~ 1:36(150점)

2번 문제의 2번 섭테를 긁었다. 2번 섭테에서는 모든 $i$에 대해 $s_i=p_i$가 성립하므로, 이기든 지든 얻는 힘이 같다. 여기서 한 가지 관찰을 할 수 있는데, 질 때는 무조건 힘이 2배 이상으로 증가한다는 것이다. 따라서 총 패배 횟수는 24번을 넘을 수 없다. 이 사실을 이용하면 위와 비슷한 방식으로 해결할 수 있다. 계속 이긴다고 가정할 때 도달 위치와 더해지는 힘의 합을 구할 수 있고, 출발 위치에서 계속 이기기 위한 현재의 최대 힘을 구할 수 있다. 계산한 희소 테이블을 통해 패배하기 전까지 갈 수 있는 최대한을 가고, 한 번 지고를 반복하면 쿼리당 로그 제곱의 시간복잡도로 계산할 수 있다.

1:36 ~ 2:19(162점)

전체 문제를 생각했지만, 감이 잘 안 와서 일단 4번 섭테를 긁었다. 4번 섭테에서는 $s_i$로 등장하는 값이 최대 5가지이므로, 그 값을 각각 $v_1, v_2, ..., v_5$라고 했을 때 현재 힘이 $v_1$보다 작은 상태에서 이동하다가 $v_1$ 이상, $v_2$ 미만인 상태로 이동하다가, 최종적으로 $v_5$ 이상인 상태로 이동할 것이다. 각 상태별로 희소 테이블을 만들어서 이동하면 로그 복잡도로 해결할 수 있다.

2:19 ~ 2:42(183점)

2번의 전체 문제는 좀 어려워 보여서, 3번으로 넘어왔다. 3번에서 $n = 2$, $k \le 2$인 테스트 케이스는 어떻게든 해결할 수 있어 보여서 풀이를 시도했고, 푸는 것에 성공했다. 2자리 이진수 2개를 비교해서 더 작은 것을 찾아내야 한다. 두 이진수를 각각 ${a_1 a_2}_{(2)}$와  ${b_1 b_2}_{(2)}$라고 하자. 우선 $2^1$ 자리의 값은 $a_1 and b_1$으로 계산할 수 있다. 이제 $2^0$자리를 계산해야 한다. 먼저 $a_1$과 $b_1$에 각각 $a_1 and b_1$을 xor해서 $a_1$과 $b_1$이 모두 1인 경우 둘다 0으로 바꾸는 연산을 시행하고, $(a_1 or a_2) and (b_1 or b_2)$를 계산하면, $2^1$자리가 가장 작은 것 중 $2^0$자리의 최솟값을 구할 수 있으므로 $2^0$자리라고 볼 수 있다.

2:42~4:33(195점)

2개의 이진수를 비교해서 더 작은 수를 찾아낼 수 있다면, 가장 작은 수를 찾아내거나 정렬하는 것이 가능하다. 2개의 이진수를 비교하는 방식을 사용한다면, 이진수의 비교에 사용하는 연산의 수를 최소화해야 한다. 우선 떠올린 것은 약 $15k$번의 연산을 사용하는 방법이었다. 변수 $a?$와 $b?$를 각각 a, b가 유효한가?(유효하면 0, 아니면 1)로 정의했을 때, 이 두 가지 변수를 관리하면서 가장 큰 자리수부터 계산해나가는 방식이다. $c$를 $a$와 $b$ 중 더 작은 값이라고 가정할 때, $c_i$는 $a_i$, $a?$, $b_i$, $b?$을 적절히 연산해서 계산할 수 있다. 그러나 이 방식은 너무 많은 연산을 사용하기 때문에 남은 테케 중 어떤 것도 해결할 수 없었다.

계속 생각하다가 더 효율적인 방법을 떠올렸다. 비트 빼기를 사용하는 것인데, $a$와 $b$의 대소는 비트 빼기 연산을 이용해 밝힐 수 있다. $a$, $b$의 길이가 $k$일 때, $a+2^k$에서 $b$를 뺐을 때 $2^k$ 자리 비트가 1이면 $a$가 $b$보다 큰 것이고, 0이면 $a$가 $b$보다 작은 것이다. 이 여부를 알아냈으면 더 작은 것을 구할 수 있다. 이 방법을 사용해서 섭테 3을 긁었다.

4:33 ~ 5:00(195점)

똑같은 방법을 사용해서 섭테 5를 풀려고 시도하다 시간이 끝났다.

 

결론

최종 점수 100 + 62 + 33 = 195점으로 끝났다.

1번 문제는 그냥 쉬운 문제였다.

2번 문제는 섭테를 많이 풀어서 방법을 응용하면 될 것 같은데, 잘 떠오르지 않았다.

3번 문제는 비트 연산을 잘 쓰면 풀릴 것 같은데, 이런 유형에 좀 약한 것 같다.

업솔빙할 예정.

 

업솔빙

 

2번 문제 업솔빙을 성공했다.

전체 문제는 앞 섭테의 아이디어를 활용해 해결할 수 있었다.

힘을 $[2^i, 2^{i+1}-1]$으로 25개의 상태로 분리할 수 있다. 각 상태에서는 $s_i \le 2^i$일 때는 무조건 승리하고, $s_i \ge 2^{i+1}$일 때는 무조건 패배한다. 그리고 $2^i < s_i < 2^{i+1}$인 경우는 한 번만 승리한다면 상태가 다음 상태로 넘어간다. 이 관찰을 이용해서 각 상태별로 희소 테이블을 따로 관리하면 된다. $i$ 상태에서 $2^j$ 만큼 진행하는 동안 $2^i < s_i < 2^{i+1}$인 경우에서 계속 진다고 가정할 때 최종 위치, 더해지는 힘의 합, 계속 지기 위한 현재 힘의 최댓값을 각각 관리하면 된다.

모든 변수를 long long으로 관리하고 배열을 정적으로 잡으면 메모리 초과 때문에 마지막 섭테를 해결할 수 없다.

따라서 변수를 int로 관리하고, 배열을 $j \le i$인 경우만 관리하면 전체 문제를 해결할 수 있다.

 

3번 문제를 풀이를 보고 업솔빙에 성공했다.

 

전체 문제 풀이는 비트 연산의 연산 횟수를 극단적으로 줄여야 하기 때문에 방법이 조금 복잡하다.

우선 $s=0$, $q \le 150$인 섭테부터 해결해보자.

두 수를 비교하는 방식을 사용한다면 $q$가 최소 $cn$이기 때문에 풀리지 않는다.

따라서 여러 개의 수를 한 번에 비교하는 방식을 사용할 것이다.

기본적으로는 앞의 섭테를 푸는 방식인 비트 뺄셈 연산을 사용하는데, 이를 동시에 연산해주는 방법이다.

우선 n이 2의 거듭제곱이라고 가정하자.(n이 2의 거듭제곱이 아니면 그렇게 만들면 된다.)

이제 $a_0, a_1, \ldots, a_{\frac{n}{2}}$와 $a_{\frac{n}{2}+1}, \ldots, a_n-1$로 나눠서 한 번에 비교할 것이다.

우선 나눠진 두 이진수 뭉탱이를 빼주고, 받아올림 위치를 $k, 2k, \ldots, nk$에서 확인할 것이다.

두 수를 X, Y라고 하면 받아올림 위치를 $(Y-X) xor X xor Y$로 계산할 수 있다.

$(Y-X) xor X xor Y$와 $k, 2k, \ldots, nk$ 위치만 마스킹 된 수를 AND 연산하면 그 위치만 남을 것이다. 이를 $Z$라고 하자.

그리고 $Z=Z-(Z>>k)$를 대입해주면, 우리가 원하는 유효한 자리만 1로 칠해질 것이다.

이를 $X xor Y$와 XOR해주고, 다시 $X$와 XOR해주면 X의 각 자리에는 둘 중 더 작은 이진수가 남게 될 것이다.

이렇게 상수번의 연산을 통해 n을 반으로 줄였기 때문에 최종적으로 로그번의 연산에 문제를 해결할 수 있다.

 

다음은 $s=1$인 경우를 생각해보자.

$n \le 10$은 그냥 비교를 통해 해결할 수 있으므로, $n \le 100$인 경우만 풀어보자.

일단 $s=0$인 경우처럼 반을 나눠 둘씩 한번에 비교해 정렬한다는 아이디어를 떠올릴 수 있지만, 이는 반을 나눠서 같은 거리에 있는 두 수만 정렬할 수 있기 때문에 전체 수열을 정렬하기는 어렵다.

그러나 놀랍게도 이 방법을 잘 활용하면 전체 수열을 정렬할 수 있다.

예를 들어 n=9라고 하자. (0, 1, 2, 3)과 (4, 5, 6, 7, 8)으로 나눠서 정렬하면 (0-4), (1-5), (2-6), (3-7)이 정렬될 것이고(A), (0, 1, 2, 3, 4)와 (5, 6, 7, 8)로 나눠서 정렬하면 (0-5), (1-6), (2-7), (3-8)이 정렬될 것이다(B).

이제 4, 0, 5, 1, 6, 2, 7, 3, 8 이라는 순열을 생각하자.

그러면 위의 A는 연속한 홀수 번째와 짝수 번째를 정렬하는 연산이 되고, B는 연속한 짝수 번째와 홀수 번째를 정렬하는 연산이 된다.

그렇다면 A, B를 이용해 버블 소트처럼 정렬할 수는 없을까?

A, B를 반복해서 n번 시행하면 신기하게도 정렬이 된다는 것을 보일 수 있다.(Odd-even sort)

 

pf)

1. Knuth의 0-1 원리

어떠한 정렬기준으로 0과 1로만 이루어진 수열을 정렬할 수 있다면, 같은 정렬 기준으로 임의의 수열을 정렬할 수 있다는 것이다.

이를 간단하게 생각해보면, 모든 x에 대해 수열의 각 원소를 "x보다 작은가?"로 바꾸면 0, 1이 되므로 모든 x를 기준으로 왼쪽과 오른쪽이 나뉜다. 따라서 수열을 정렬할 수 있다는 것을 알 수 있다.

2. Odd-even sort 작동 원리

$i$번째 연산$(0 \le i \le n-1)$에서는 모든 $j(0 \le j \le n-2)$에 대해 $a_j$와 $a_{j+1}$을 정렬한다.(단, $i$와 $j$는 기우성이 같다.)

3. Odd-even sort 증명

Knuth의 0-1 원리에 따라 주어진 수열의 원소를 모두 0과 1로 바꿀 수 있다.

각 1의 위치를 $x_1, x_2, \ldots, x_k$라고 하자.

우선 $x_k$의 경우 1번째 또는 2번째 연산에서 무조건 한 번 이상 오른쪽으로 움직이고, 3번째부터는 계속 오른쪽으로 움직인다.

따라서 $x_k$는 $n-k+1$번 연산을 시행하면 무조건 오른쪽에 도착한다.

$x_{k-1}$의 경우 1번의 연산 이후 $x_k$와 비교되지 않기 때문에, $n-k+2$번의 연산을 시행하면 오른쪽에 도달한다.

같은 방식으로 $x_i$는 최대 $n-i$번의 연산 이후 올바른 위치에 도달한다.

 

이렇게 Odd-even sort를 이용하면 A, B 각 연산을 총 $O(n)$번 사용하고, 연산을 시행할 때 상수번의 연산을 사용하기 때문에 선형의 연산 횟수로 해결할 수 있다.

개인적으로 문제의 풀이가 매우 아름다웠다.