총점 : 14 + 60 + 93.7 = 167.7 (한국 기준 10등, Unofficial 동상)
<세 줄 요약>
1. 2번과 3번은 변별력이 크지 않아서 1번 점수에 따라 시험의 성패가 갈렸다.
2. 그런데 1번이 딱히 좋은 문제인지는 모르겠다...
3. 작년보다 쉬운 난이도로 숨통은 좀 트이는 시험이었다.
APIO 2021에서 5시간 동안 머리를 싸매고 얻은 결과가 40점대였기에, APIO라는 시험에 대해 그렇게 좋은 기억이 있지는 않았다. 또한 한국 6등까지만 수상이 가능한데 수많은 계절학교 모의고사 및 선발고사에서 한 셋 기준으로 6등 안에 들어본 기억이 없기에, 참가에 의의를 두고 즐겁게 참여했다. 원래는 KMO 다음 날 보려고 했는데, KMO를 생각보다 잘 봐서 머리 컨디션이 좋다고 판단하고 당일 밤에 응시하였다.
일단 점수에 대한 코멘트를 하자면, 2번은 그냥 다 60점이라고 보아도 무방하다. 3번도 다 100-a점 (a<10)이라고 보아도 무방하다. 그래서 1번에 그 쪼개져있는 섭테들에서 얼마나 많은 섭테를 긁었는지만으로 시험의 성패가 갈렸다. 이 과정에서 2번의 60점이라는 점수가 매우 크다는 것도 한 몫을 했다. 2번에서 100점을 받은 사람이 세계에서 3명인데, 이 3명 모두 1등을 차지하지 못했다. 100/60/100이 1등이라고 한다. 이는 2번에서 60점을 너무 쉽게 줘서, 2번에서 100점을 맞아도 1번에서 60점 이상 긁기 힘들었기 때문이었다. 그래서 개인적으로 1번보다는 2번의 배점 선정이 조금 아쉬웠던 것 같다. 현재 60점을 받을 수 있는 풀이의 배점을 조금 더 낮췄으면 더 좋았을 것 같다.
아래는 문제 요약 및 코멘트, 그리고 나의 접근이다.
1번. Mars
(2n+1)*(2n+1)의 배열이 주어지고, 각 칸은 1 또는 0으로 이루어져있다. 결과적으로 1로 이루어진 컴포넌트의 개수를 구하는 것이 목표인데, 쓸 수 있는 메모리가 한정되어있다. 우리에게 주어지는 것은 100자리 이진수열 (2n+1)*(2n+1)개이며, 이들은 각각 1000...000 또는 0000...000으로 초기화되어있다. 전자는 초기 배열의 칸이 1인 경우, 후자는 초기 배열의 칸이 0인 경우이다. 그리고 k단계에 걸쳐 이 배열에 덮어쓰기를 할 수 있다. (k=0부터 n-1)
각 k번 단계에서는 (0, 0)부터 (M, M)까지 순회하며, 여기서 M=2(n-k-1)이다. (i, j)를 순회할 때는 현재 (i, j)부터 (i+2, j+2)까지 9개의 이진수열이 주어진다. 그러면 이 9개의 이진수열 정보를 이용하여 (i, j)번 칸의 이진수열을 업데이트하는 문제이다. 이렇게 해서 모든 단계가 종료되면 (0, 0)의 이진수열에는 초기 배열에서 1로 이루어진 컴포넌트의 수가 들어있어야 한다.
우선 읽는 데에 10분이 넘게 걸렸고, 테스트 케이스가 대충 아래와 같이 생겼다. 출제자 나와
일단 뇌가 하얘졌고, 풀기가 싫어졌다. 나는 즐겁게 대회를 하기로 했으니 즐겁지 않은 문제는 안 풀기로 하여 2번, 3번에서 긁을 수 있는만큼 긁고 나서 1번으로 돌아왔다. 실제로 1번에 투자한 시간은 그렇게 많지 않은 것 같다.
우선 정보들을 잘 저장해서 초기 배열 (2n+1)*(2n+1)의 모든 칸의 정보를 (0, 0)의 이진수열로 옮길수만 있다면 마지막 단계에서 단순 컴포넌트 세기 DFS로 문제를 해결할 수 있다. 이 풀이가 14점이고, 자꾸 전역변수에서 이상한 짓 하지 말라고 경고해서 나는 DFS도 stack을 이용해서 짜서 한 번에 긁었다. 여기서 생각을 조금 더 확장해보면, 결국 마지막 단계에서 다룰 수 있는 칸은 총 9칸이다. 그러면 각 칸에 100개씩, 총 900개의 칸을 저장할 수 있지 않을까? 이걸 잘 짜면 최대 54점까지 노릴 수 있을 것 같은데, 실제로 54점을 받은 친구가 없어서 잘 모르겠다. 몇몇 친구들은 54점 혹은 100점부터 짜다가 결국 0점 받고 끝냈다고 한다.
2번. Game
N개의 정점으로 이루어진 그래프를 다룰건데, 초기에는 0번부터 K-2번 정점에 대해 i->i+1 간선만 그어져있다. 0번부터 K-1번 정점을 지나면 스탬프를 받을 수 있으며, 만약 이 점들 중 하나를 포함하는 사이클이 있다면 스탬프를 무한히 받을 수 있다. 여기서 이 그래프에 방향 간선이 하나씩 추가되는데, 어느 시점에서 스탬프를 무한히 받는 사이클이 처음으로 생기는지 알아내면 되는 문제이다.
N-K개의 정점에 대해 in[x]를 x번 정점에서 갈 수 있는 스탬프가 있는 정점 번호의 최솟값, out[x]를 x번 정점으로 갈 수 있는 스탬프가 있는 정점 번호의 최댓값이라고 하자. 어떤 x에 대해서도 in[x]<=out[x]가 되는 순간 스탬프를 무한히 받는 사이클이 생긴다. 그 외의 경우 K개의 정점 안에서 역방향으로 가는 간선이 추가될 경우 바로 스탬프를 무한히 받는 사이클이 생긴다. 이를 나이브하게 구현하여, 간선이 추가될 때마다 DFS로 in과 out을 갱신해주면 시간복잡도 O(NM)이 되어 30점을 받을 것 같았는데, 무려 60점을 줬다. 여기서 60점은 최종 섭테를 제외한 모든 점수이다. 알고보니 각 N-K개의 점들마다 in과 out은 최대 K번까지만 갱신되며, 갱신되지 않는 경우 바로 return을 갈겨주었으므로 시간복잡도가 O(NK)로 보장이 되는 것이다. 암튼 이걸 모르고 60점을 받았다.
참고로 이 문제에서 만점을 받은 학생은 전 세계에서 3명이라고 한다. 그런데 최종 섭테를 제외한 점수인 60점이 너무 쉽게 떠서, 문제의 변별력이 삭제된 것 같다. 오히려 이 문제에 시간을 오래 투자한 학생들만 손해를 본 느낌인데, 난 그다지 많이 투자하지 않아서 큰 피해를 본 것 같지는 않다. 친구가 https://koosaga.com/271 이 글을 통해 이 문제의 100점 풀이를 구상했다는데, 시간 내에 짜지는 못했다고 한다. 나도 아직 저 글을 다 읽어보지는 못해서 틀린 풀이일 수도 있는데, 도전해보고 싶은 사람들은 저 글을 참고하면 좋을 것 같다.
3번. Permutation
증가하는 부분수열의 개수가 정확히 K개 있는 permutation을 만들면 되는 간단한 문제이다. K<=1e18이고, permutation의 길이가 90 이하면 만점을 준다. 배점표는 아래와 같다.
개인적으로 Constructive type의 문제들을 좋아해서 재미있게 풀었다. 이런 방법, 저런 방법들을 시도해보며 점수를 조금씩 올렸다. 결과적으로 100점은 받지 못했지만 재미있게 풀어서 아쉽지는 않다. 아래는 내가 접근했던 과정들이다.
10점 :
길이 N의 permutation을 N-1, N-2, ... , 0으로 적으면 증가하는 부분수열의 개수는 N+1개이다. 따라서 주어지는 K에 대해 길이 K-1의 순열을 역순으로 만들면 부분문제 1에 해당하는 점수인 10점을 받을 수 있다.
71.2점 :
10점을 긁으면서 큰 것들을 앞에 사용하고 작은 것들을 뒤에 사용하면 두 수열을 더하는 효과를 가져올 수 있다는 사실을 관찰하였다. 또한 길이 N의 permutation을 0, 1, ..., N-1로 적으면 공집합 제외 2^N-1개의 증가하는 부분수열이 나온다. 따라서 K가 주어지면 K-1을 2^N-1의 합들로 나누어 수열을 구성해줄 수 있다. 정확히는 아니지만 대충 로그 스케일이고, 구현하면 71.2점을 받는다.
91.36점 :
순열을 여러 개로 분리해서 사용하는 것은 너무 길이 낭비 같아보인다. 이에 따라 기본 수열을 잡고, 중간중간에 숫자를 끼워넣는 방식을 생각할 수 있다. 구체적으로는, K를 이진수로 표현하여 최대 크기의 비트를 1<<k라고 하자. 그러면 우선 길이 k의 증가하는 순열을 하나 적는다. x, x+1, ..., x+k-1과 같이 말이다. 그런 다음 K의 켜져있는 비트 1<<i에 대해, 뒤의 i개의 수 앞에 x보다 작은 수를 하나 추가하면 1<<i개의 증가하는 부분수열을 더 만들 수 있다. 따라서 켜져있는 비트의 개수만큼 수를 더 추가해주면 된다. 예를 들어, K=11인 경우 1<<3이 가장 큰 비트이므로 0, 1, 2, 3을 적어둔다. 그런 다음 1<<1과 1<<0이 켜져 있으므로 각각 수를 하나씩 추가하여 0, 1, 2, -1, 3, -2로 적어주면 된다. 추가한 숫자만큼 모든 항에 더해주면 증가하는 부분수열의 개수가 정확히 K개인 순열이 된다. 개수는 최대 60+59=119개를 사용한다. 이론상 90.33점이고, 저격 tc가 없어서 91.36점을 받는다.
93.7점 :
사실 주변에서 같은 점수를 받은 사람을 못봤고, 이 풀이를 생각한 사람은 나밖에 없을 것 같다. 여태껏 이진수로 접근했으니 이제 삼진수로 접근하자. 1 0 3 2 5 4 .... 하는 식으로 순열을 만들면 2N개의 수로 3^N을 표현할 수 있다. 삼진수는 0, 1, 2를 포함하기 때문에 +2*3^i, +3^i을 할 방법이 필요한데, 그 방법은 생각보다 간단하다. 이진수를 넣을 때처럼 삼진수에서도 1 -1 0 3 2 5 4 ... 를 하면 +2*3^(N-1)이 되고 1 0 -1 3 2 5 4 ...를 하면 +3^(N-1)이 된다. 같은 방식으로 모든 3^i에 대해 처리해줄 수 있다. 3^38>1e18이므로 N이 최대 37이고, 개수는 최대 37*2+36=110개를 사용한다. 이론상 93.33점이고, 저격 tc가 없어서 93.7점을 받는다.
100점을 받은 친구들도 많은 것을 보니 이 문제는 백준 티어 기준 플래인 것 같다. 다양한 풀이를 생각해볼 수 있어서 재미있었다.