(팀연습) Road To Grandmaster Round 6

저번 주에 이어서 또 도전... 저번보다 문제가 약간 별로인 것 같다.

저번보다 못한 6문제를 풀었다. 하나는 풀이를 알았는데 시간이 없었고, 하나는 내가 끝끝내 예외를 못찾아서 틀렸으니 조금 더 실력이 있었으면 8문제는 거뜬했을 듯. 내가 1문제를 푼거로 봐서 내가 못한 것 같다.. 근데 나한테 배정된 A~D가 솔직히 좀 어려워서 털릴 만 했다...

E번(637C) - Promocodes with Mistakes

N군이 후다닥 풀었다.

6자리의 n개의 이벤트 코드가 있는데, 코드를 칠 때 k자리를 잘못 칠 수 있다. 이 때 모든 코드를 구별하기 위한 최대 k를 구하는 문제.

엄청 쉬운데, 두 코드가 p자리가 서로 다르면, (p - 1) / 2개 이하를 잘못 쳐야 둘을 구별할 수 있다. 모든 쌍에 대해 반복하면 된다.

G번(566D) - Restructuring Company

D군이 후다닥 풀었다.

DSU의 확장판인데, 일반적인 DSU에 추가적으로 x~y의 구간을 한번에 합치는 연산이 들어간다.

풀이 방법은, set을 이용해 구간들을 유지하면 편하다. 예를 들어 [1, 2], [3, 7], [8], [9, 12]의 구간들이 있다면 그 중 가장 마지막 값인 2, 7, 8, 12만 set에 유지시키는 것이다. 그러면 lower_bound를 사용해 각 숫자들이 같은 구간에 포함되는지 log(n) 시간에 알 수 있으며, 합치는 것 또한 간편하다. 위 상태에서 만약 6~9의 구간을 합친다면, [3, 7], [8], [9, 12]를 [3, 12]로 만들어주면 된다. 합칠 때 더이상 대표가 아닌 원소를 set에서 빼고, 뺄 때 DSU merge를 한 번 해주면 된다.

총 merge 횟수는 n + q를 넘지 않게 된다.

A번(493D) - Vasya and Chess

그 무렵 나는 A~D에서 멘붕의 도가니에 빠져있었다. 하나도 모르겠어서 일단 나는 I번이 풀만하다길래 받아서 풀고있었는데, D군과 N군이 논의하다 정답을 알아냈다.

n * n짜리 체스판이 있는데, (1, 1)에는 white queen이, (1, n)에는 black queen이 있다. 나머지 칸에는 green pawn들이 가득 차있다. 흰색부터 시작해서 번갈아가며 턴을 진행하는데, 폰을 하나 먹거나 상대방의 말을 잡거나 할 수 있다. 말이 먹히거나 먹을 폰이 없으면 진다. 누가 이기는지, 흰색이 이긴다면 처음에 어떻게 움직여야 하는지도 출력해야 한다.

풀이가 생각보다 너무 허무하다. 판 크기가 홀수이면, 흑이 백이 움직이는대로 대칭으로 똑같이 움직이자. 그러면 언젠가 백이 가운데 칸으로 오게 되고, 그 때 잡으면 이긴다. 판 크기가 짝수이면, 오른쪽으로 한 칸 움직이자. 그러면 이제 흑이 움직이는 대로 백이 따라서 움직이면 된다.

알고리즘 게임에서는 흉내바둑을 항상 기억하자. 상대방 하는 대로 따라하는 것이 나쁘지 않은 전략일 때가 많다. 인생을 살면서도 잘 적용해보자. 경쟁자가 공부를 하면 최소한 그 시간에는 공부를 한다거나...

I번(590B) - Chip 'n Dale Rescue Rangers

바람이 불 때, 장애물까지 도달하는 최소 시간을 구하면 된다. 바람의 방향은 t초 때 한 번 바뀐다.

바람과의 상대 속도는 v 이하가 되도록 유지해야 한다.

바람이 불 때는 항상 장애물이 움직인다고 생각하자. 그렇다면 장애물의 시간에 따른 좌표는 초기 좌표가 $(x, y)$, 장애물이 움직이는 속도(바람 속도의 반대 방향)를 $(v_x, v_y)$라 했을 때 u초 뒤 좌표는 $(x + v_xu, y + v_yu)$가 된다. 이 거리가 vu와 같아야하므로, 제곱하면 u에 대한 이차방정식이 나온다. 이를 근의 공식을 이용해서 풀면 된다.

바람의 방향이 바뀐 이후 식이 약간 복잡하긴 하지만, 침착하게 풀자.

F번(442A) - Borya and Hanabi

5가지의 색과 5가지의 숫자가 있고, 각 카드마다 하나의 색과 하나의 숫자를 가진다. 주인공은 자기가 어떤 카드들을 가지고 있는지는 알지만, 각 카드의 위치는 모른다. 순서를 맞추기 위해 질문을 할 수 있는데, 하나의 색 혹은 하나의 숫자를 물어보면 그 색/숫자를 가진 모든 카드의 위치를 알려준다. 모든 카드의 위치를 맞추기 위한 질문의 최소 수를 구하는 문제이다.

질문은 10가지 종류가 있고, 질문의 순서는 상관이 없으므로 총 2^10가지 질문들의 목록을 다 해보면 된다. 이제 질문들이 주어졌을 때 카드를 맞출 수 있는지를 판별하는 함수를 구현해야 하는데, 구현을 어떻게 해야할지 참 갑갑하다... 나는 끝나고 2시간에 걸쳐 구현했는데, 더 쉬운 방법이 있다.

각 질문들을 bitmask로 표현한 뒤, 모든 카드의 pair에 대해 둘이 구분이 되는지 확인하면 된다. 하나라도 구분이 되지 않는다면 불가능한 것이다.

카드 a와 b가 구분이 되는지 여부는 (a != b) && ((mask & a) == (mask & b))로 확인할 수 있다. 이 값이 참이면 구분이 되지 않는 것.

이런 구현을 생각해낸 N군 리스펙...

남은 것: H번,

못푼 것 중 푼 것: K, L번

못푼 것: B, C, D, J번이 남았는데