APIO 2022

이번 APIO는 흥미로운 문제들이 많이 나왔던 대회입니다. 

저는 100+60+100=260점을 획득하여, 공동 1등을 하였습니다.

A. Mars

이번 대회 문제들 중에서 개인적으로 가장 재미있었던 문제입니다. 컴퓨터에 제약이 있는 흥미로운 문제라는 점에서 IOI 2021 레지스터랑 비슷한데, 안 말려서 다행입니다.

문제 요약: 0과 1로 된 2n+1*2n+1 크기의 정사각형 격자가 주어지는데, 이 격자의 1로 된 연결 요소의 개수를 구해야 한다. 이렇게 하면 너무 쉽기 때문에, 컴퓨터에 제약이 있다. 컴퓨터의 메모리는 2n+1*2n+1 크기의 정사각형 격자이고, 한 칸에 100비트만 저장할 수 있다. 연산의 순서에도 제약이 있는데, 이 컴퓨터는 메모리를 위쪽부터 아래쪽, 왼쪽부터 오른쪽 순서로 수정하는 행위를 n번 반복한다. 한 번 메모리를 수정할 때는 수정하는 칸을 왼쪽 위 꼭짓점으로 하는 3*3 정사각형 부분 메모리의 값을 볼 수 있다.  k번째 수정할 때 보는 부분은 원래의 왼쪽 위 꼭짓점을 그대로 왼쪽 위 꼭짓점으로 하고, 크기가 2n-2k-1인 정사각형이다. 마지막 수정할 때는 원래의 왼쪽 위 꼭짓점 칸만 보는데, 그 때 왼쪽 위에는 답이 2진수로 저장되어 있어야 한다. 

저는 대회 중에 작은 섭테를 긁으려는 시도를 하지 않았기 때문에, 만점 풀이만 설명하겠습니다.

41*41 격자의 정보를 100바이트 내로 담아야 했기 때문에, 격자의 모든 정보를 담을  수는 없습니다. 

그래서 기본 구조는 앞으로 볼 필요가 없는 오른쪽 아래 부분의 전체를 보내지 않고, 답을 구하는 데 꼭 필요한 정보만 보내는 것입니다.

앞으로 다시 볼 수 없는 오른쪽 아래 부분이 중요하기 때문에, 지금 수정하는 칸이 현재 돌고 있는 정사각형의 오른쪽 끝이나 아래쪽 끝이 아니라면 그냥 넘깁니다.

오른쪽 끝일 때는 자신 오른쪽에 있는 모든 원소와 자신 칸에서 한 칸 아래에 있는 원소 오른쪽 모든 원소를 저장해줍니다.

아래쪽 끝일 때도 대칭적으로 해줍니다.

이제 오른쪽 아래 꼭짓점이 남아 있는데, 이 부분이 중요합니다. 오른쪽 아래 꼭짓점의 오른쪽 원소들과 아래쪽 원소들은 꼭짓점 바로 위와 바로 왼쪽 원소들에 의해 저장되어 있습니다. 이제 이 원소들을 아래쪽 끝->꼭짓점->오른쪽 끝 순서로 보면서, 연속된 원소들은 구간으로 만들어줍시다. 이제 이 구간들이 어떻게 연결되어 있는지를 저장해 줍니다. 이를 위해서는 우선 오른쪽 아래 원소와의 x좌표 차이가 2 이하이거나 y좌표 차이가 2 이하이면서, 오른쪽 아래 원소를 왼쪽 위 꼭짓점, 전체 격자의 오른쪽 아래 꼭짓점을 오른쪽 아래 꼭짓점으로 하는 격자들에서 유니온 파인드를 해줍니다. 

오른쪽 아래 원소와의 x좌표 차이가 2거나 y좌표 차이가 2 구간인 원소들은, 유니온 파인드 범위에 포함되지 않는 오른쪽 아래 깊숙한 곳에서 연결이 될 수 있습니다.

이런 경우에는 저번에 돌았던 부분 오른쪽 아래 꼭짓점을 볼 수 있으므로, 그 꼭짓점에서 연결 요소의 정보를 가져와야 합니다. 저번에 돌았던 부분 오른쪽 아래 꼭짓점에는 x좌표나 y좌표가 2 차이나는 구간이 가장 바깥쪽 구간이 되므로, 구간이 어떻게 연결되어 있는지에 대한 정보를 가져올 수 있습니다.

가져와서 유니온 파인드를 하면, 가장 바깥쪽 부분의 원소들로 이루어진 구간이 어떻게 연결되어 있는지를 알 수 있고, 이 구간들을 연결한 모양은 위에서 말했던 순서대로 봤을 때 교차하지 않음을 알 수 있습니다.(증명은 안 했습니다.) 

이를 이용하면 괄호 문자열과 비슷한 형식으로 연결 모양을 인코딩할 수 있습니다. 2i+2번째 비트는 연결이 곧 있을 거라는 여는 괄호의 역할을 하고, 2i+1번째 비트는 저번에 연결이 있을 것이라는 신호와 연결이 된다는 것을 알려줍니다. 

이렇게 인코딩한 뒤에는, 오른쪽 아래 부분에 있었으나 가장 바깥쪽에는 없어져 더 이상 탐색되지 않는 부분의 개수를 저장해 줍니다. 이는 저번 오른쪽 아래 꼭짓점에서의 이 값과, 이번 유니온 파인드에서 있는 연결 요소 중 바깥쪽에 없는 연결 요소의 개수의 합입니다.

 

이를 구현해주면 100점을 맞을 수 있습니다. 참고로 유니온 파인드를 비효율적으로 구현하는 등의 이유로 메모리 초과가 나올 수 있습니다. 구식 컴퓨터라 메모리도 부족하다는 설정인가요?

 

B. Game

유일하게 만점을 받지 못한 문제입니다. 아직 만점 풀이를 알지 못해서, 60점 풀이만 씁니다. 

문제 요약: 초기 상태에 0->1, 1->2 ...... k-2->k-1의 방향 간선이 있고, 다이나믹하게 간선이 추가되는 그래프가 있다. 이 그래프에 0~k-1의 정점을 하나라도 포함하는 사이클이 있는지 구하여라. 간선은 온라인으로 주어지므로, 오프라인 풀이는 불가능하다.

60점일 때는 정점 개수가 3만이고, k는 1000 이하입니다. 각 정점마다 갈 수 있는 0~k-1 정점 중 최소 번호와, 0~k-1에서 이 정점으로 올 수 있는 최대 번호를 구해줍니다다. 만약 최대 번호가 최소 번호 이상인 정점이 생기면 사이클이 만들어진 것이므로 그만둡니다.. 

맨 처음에는 0~k-1 정점은 최소 번호를 번호+1, 최대 번호를 번호-1로 해주고, 나머지는 없다고 표시해줍니다.

이제 간선을 하나 추가할 때마다 dfs를 돌려줍시다. 첫 번째 dfs는 간선을 원래 방향대로 타면서, 올 수 있는 최대 번호를 갱신해주고, 두 번째 dfs는 간선을 역방향으로 보면서, 갈 수 있는 최소 번호를 갱신하면 됩니다..

답은 총 정점 개수*k번 갱신되고, 갱신이 안 되면 dfs를 멈추면 되므로, 시간 복잡도는 정점 개수*k이므로, 통과됩니다.

 

C. Perm

증가하는 부분 수열(빈 수열 포함)의 개수가 정확히 K인 순열을 만들면 됩니다. K는 10¹⁸까지 가능하고, 길이는 90 이하여야 합니다. 

이 문제는 https://www.acmicpc.net/problem/22998 와 비슷합니다.

풀이: 길이가 120 이하일 경우에는 2^a=K를 만족하는 최대 a를 길이로 하는 증가수열을 넣어준 뒤, 뒤에다가 K의 i번째 비트가 켜저 있으면 i+1번째 원소보다는 작지만 i번째 원소보다는 큰 원소를 감소하도록 넣어주면 됩니다.

이러면 K가 2ⁿ-1일 때 120개를 사용하게 되므로, 이를 바꿔 봅시다.

만약에 켜저 있는 비트가 2개 연속해 있으면, 작은 비트에 해당하는 원소를 넣은 뒤 뒤에다가 자신보다 큰 원소가 2개 있도록 하여 하나의 원소로 두 개의 비트를 킬 수 있습니다.

이 최적화를 사용하면 길이는 항상 90 이하가 되며, 자신보다 큰 원소가 뒤에 0개 혹은 2개 있도록 하는 것은 작은 원소부터 넣어주면 달성할 수 있습니다.

 

총평:

각 문제들에 적절하게 시간 배분을 하고, 여러 가지 관찰들을 차근차근 해내며 생각한 결과, 지금까지 했던 대회 중 최고의 성적을 거둘 수 있었습니다. 앞으로도 이 대회에서 배운 것들을 잊지 않고 좋은 성적을 거둘 수 있으면 좋겠습니다.