BAPC 2021

선발고사 대비용으로 3시간짜리 셋을 돌았다. OI가 아닌 ICPC 셋을 선택한 이유는, 적당한 3시간 OI 셋을 찾을 수가 없었다. 3인 셋을 혼자 도는 거니까 대략 스코어보드 깠을 때 5등 안에 들자는 마음으로 셋을 쳤다.

 

최종 스코어보드

대회 당시 9솔이 최대였고, 나는 11솔을 했다. 

 

J 빼고는 크게 어려운 문제가 없는 셋이었다. 각 문제에 대해 푼 순서대로 대략적인 풀이를 적어 본다.

 

A (0:02)

문제 해석하는 게 푸는 것보다 더 오래 걸리는 문제다. 예제가 예상과 달라서 10초 정도를 허비하는 바람에 1분째에 맞출 수 있는 문제에서 시간을 날렸다.

 

답은 $(x \pm r, y \pm r)$의 네 꼭짓점으로 이루어진 정사각형이다. 이 외에도 다양한 답이 있겠지만, 굳이..?

 

B (0:19)

쉬워 보여서 A 다음으로 잡았는데, 구현에서 조금 말려서 오래 걸렸다. 기본적인 아이디어는, 일단 각 attribute별로 요구하는 최대치까지는 끌어 올려 줘야 한다는 것이다. 그럼 각 attribute 별로, 최소 요건은 만족되었고, 추가로 다음과 같은 수치가 정해진다. 

• 이 attribute를 $1$ 증가시키면 $A_i$점을 얻는다.
• 그 다음에 이 attribute를 $1$씩 증가시키면 추가로 $B_i$점씩을 얻는다.

이때 $A_i > B_i$가 무조건 성립하므로, 그때그때 가능한 최선의 선택을 그리디하게 하면 된다. $k$가 크기 때문에 우선순위 큐를 이용하는 것이 좋고, $B_i$를 이용하기 시작하는 순간 그 뒤의 나머지 선택도 모두 같은 선택을 해야 한다는 점을 이용하면 해결된다. 시간 복잡도는 $O(N \log N)$ 언저리이다.

 

D (0:30)

$DP[i][j]$를 $i$번 점까지 왔고, 마지막 점프의 길이가 $j$ 이상인 경우의 답이라고 하면 $O(N^2)$에 문제를 풀 수 있다. 우선 $i$열에서 $i+1$열로 전이할 때는 $j$ 이상 -> 정확히 $j$로 고쳐서 풀고, $i+1$번 열에서 $j$를 $N$부터 $1$까지 옮기면서 DP[i][j] = max(DP[i][j], DP[i][j+1]) 을 해 주면 된다.

 

F (0:40)

먼저 전체 합을 n/2로 나눠 주면 두 스탯 합이 나오고, 팀원을 한 명씩 set 등의 자료구조로 보면서 파트너를 찾아주고 둘 다 set에서 제거하는 연산을 반복하면 가능성을 판별할 수 있다.

 

H (0:50)

well known 한 유형이다. 일단 아무 스패닝 트리나 잡고, 그 트리 위에서 해결한다. 트리 위에서 dfs를 하면서, 일단 내려갈 때는 최대한 늦게 마킹(숙소에 방문)을 하고, 올라올 때(이 숙소에 더 이상 방문할 일이 없을 때)는 모든 숙소에 다 방문을 한다. 이렇게 하면 마킹 시점의 차이가 항상 3 이하임을 쉽게 보일 수 있다.

 

I (0:59)

컴퓨터 수 $c$가 정해졌을 때 가능한지 판별하는 결정 문제로 바꾸고, parametric search로 문제를 해결한다. 결정 문제를 풀 때는, 시간이 가장 촉박한 문제부터 해결하며, 시간이 남아 있는지 보는 방식으로 그리디하게 판정하면 된다.

 

K (1:32)

기본적으로 생각할 수 있는 형태는 (0, 0) - (0, M) - (1.001, M) - (1.001, 0) - (2.002, 0) - (2.002, M) - ... 과 같은 곡선이며, 이 곡선을 따라갈 경우 길이가 거의 가장 길다는 것을 눈치챌 수 있다. 그런데 여기서 길이 제한이 있으므로, 이 곡선 어딘가에서 곡선을 따라가는 것을 멈추고 직선으로 도착점까지 이동해 주면 된다. 이 점은 이분 탐색으로 찾을 수 있다.

 

E (1:48)

대충 $N$이 적당한 크기 이상이면 성공할 수 있다는 믿음을 가진다. 하지만 $N$이 크면 LCS를 구하기 힘드므로, $N = 100$인 구간씩 쪼개고 최대의 LCS를 구한 뒤 합친다. 이렇게 하면 만점이 나온다.

 

C (2:02)

처음에 m<=100으로 잘못 읽었는데, 다시 보니 m<=10이었다.

 

푸는 방법은 간단한데, Bitmask DP를 이용해 밑 줄부터 쌓아올린다. 전처리를 통해 가능한 bitmask랑 (두 칸씩 인접한 형태로 나와야 하기 때문에 가능한 mask 수가 제한된다), 한 mask 위에 쌓아올릴 수 있는 mask에 관한 정보를 구해 둔 뒤 문제를 풀면 $O(N \times 4^M)$ 정도에 풀린다. 사실 mask 수가 훨씬 작기 때문에 시간복잡도는 이것보다 훨씬 작다.

 

L (2:06)

셋을 돌면서 유일하게 재밌었던 문제.

 

언뜻 봤는데 쉬운 풀이법이 생각나지 않았고, 뭔가의 강한 직감으로 식을 정리해야 풀 수 있는 문제라는 걸 깨달았다. 식을 정리해 보면 $R_i$를 $i$번 사람과 다른 모든 사람의 점수의 합이라고 정의할 때, 그룹 A에 있는 사람들의 $R_i$ 합에서 그룹 $B$에 있는 사람들의 $R_i$ 합을 뺀 것이 구하는 답이라는 것을 알 수 있다. 따라서 $R_i$가 큰 사람들을 그룹 A에, $R_i$가 작은 사람들을 그룹 B에 넣어주면 문제가 풀린다.

 

몇 대회 연속으로 식 정리 문제에 말리다가 처음으로 풀었더니 기분이 좋다. 물론 지금까지 본 식 정리 문제들보단 난이도가 쉽긴 했다.

 

G (2:29)

$4000 < 275 \times 15$라는 점을 이용해 쿼리 한 번당 15개의 연산자를 알아내면 된다. 맨 끝에 있는 15개의 연산자를 알아내는 방법이 있을까? 길게 고민하지 말고, 랜덤 수열을 넣는 것을 반복하면 된다. 15개의 연산자 앞쪽 수들은 전부 0으로 채우고, 15개의 연산자 바로 뒤에 배치되는 15개의 수는 랜덤으로, 그리고 그 뒤의 수들은 앞에서 알아낸 결과에 따라 + 뒤이면 0, * 뒤이면 1을 넣으면 된다. 랜덤으로 수를 배치했을 때, 두 가지 연산자 조합이 하나의 결과가 나오면 망하기 때문에, 이런 경우가 생기지 않도록 계속 반복해서 시도해보면 된다.

 

J (Unsolved)

게임이론 문제고, 풀이의 방향은 단순히 모든 상태를 시험해 보는 방법으로 보인다. 일단 상태의 가짓수를 보자면, 도둑 입장에서 상태는 $2M$가지이다. 또한 경찰 입장에서는 상태가 $O(N^2)$가지이다. 도둑 입장에서는 가장 먼 점들 중 하나를 찾아 가면 되는데, 이때 점 후보를 계산해 두고 (사전에 Floyd Warshall을 돌려야 한다), 가능한 모든 경우로 전이할 수 있다고 표시해 둔다. 경찰 입장에서 가능한 후보 전이도 $N$개 이하라서, 가능한 모든 경우를 다 해보면 $O(N^3)$ 정도에 상태 전이 테이블을 구할 수 있다. 그러고 나서는 게임이론 문제 풀듯이 상태전이 그래프에서 dfs를 한 번 돌리면 판정이 끝날 것이다.

 

풀이 감을 대략적으로 잡은 상태에서 시간 내에 푸는 걸 포기했다. 대회에서 가장 어려운 문제 포지션인 것 같긴 한데, 크게 어려운 것 같진 않다. 고른 ICPC 셋이 생각보다 쉬워서 (spoiler를 하나도 듣지 않고 선정하니 이런 일이 발생한다), 다음에는 셋 선정에 좀 더 고심해야 할 것 같다.