Codeforces Round 1046 (Div.2) 후기

첫 블로그 글을 써본다.

어제 무려 3시간동안 진행된 코포의 후기를 작성해보겠다.

 

A. In the Dream (00:00 ~ 00:06)

각 팀이 매 half 마다 얻은 점수를 구해서 가능한지 여부를 판단하면 된다. 조건 분기가 좀 있었다.

 

B. Like the Bitset (00:06 ~ 00:13)

조건에 맞게 순열을 구성해야 하는 문제이다. 길이가 k 이상인 순열의 연속 부분 수열을 임의로 선택할 때, 그 부분 수열의 최댓값의 위치에 해당하는 주어진 문자열의 값이 0이어야만 한다. 풀이는 꽤 간단하다. 주어진 문자열의 값이 0인 위치에 우선적으로 큰 값을 배치한다. 순열을 구성하는 것이기 때문에, idx를 N으로 설정한 후, 1씩 줄이면서 배치하면 된다. 이후, 문자열의 값이 1인 위치에 같은 방법으로 idx를 1씩 줄이며 배치하며 연속으로 k번 이상 배치하지 않는지 확인해 가능 여부를 판단한다. 만약 가능하다면 조건을 만족함을 알 수 있다.

 

C. Against the Difference (00:13 ~ 00:58)

자연수 i 가 i 개 있는 수열을 블록이라 한다. 임의의 수열에서 블록으로만 이루어진 부분 수열을 선택할 때, 그 길이의 최댓값을 구하면 된다. 처음에는 해시를 짜는건가 고민하다가 dp 풀이를 생각했다. dp[i]를 현재 위치에서 i 번째로 가까운 i 값이 나온 인덱스와 수열의 길이의 최댓값으로 저장해 전이했다. 전이 과정에서 반례가 생겨서 2번 틀린 후에, i 값이 나온 최근 k개를 모두 저장하는 큐를 사용해 dp를 전이했고, 성공했다. 생각보다 말려서 조금 당황했다.

 

D. For the Champion (00:58 ~ 01:30)

여러 고정점이 있고, 로봇이 임의의 위치에 있다. 이 로봇을 상하좌우로 최대 10번 이동시켜, 매 턴마다 고정점과의 맨해튼 거리의 최솟값을 입력받는다. 이때, 로봇의 초기 위치를 구해야 한다. 사실 문제에 큰 힌트가 있었는데, 고정점, 로봇의 초기 좌표는 절댓값이 최대 1e9로 한정되어 있지만, 실제 2D 평면판은 무한 평면이다. 심지어 볼드 처리됨

이를 이용해 로봇을 오른쪽, 위로 2e9만큼 이동시킨다. 한번에 최대 1e9까지만 이동할 수 있으니 4개의 턴이 소모된다. 이렇게 하면 로봇이 다른 모든 고정점에 비해 오른쪽 위에 있음을 알 수 있고, 고정점의 x+y 최댓값을 알면 로봇의 초기 위치 x+y를 알 수 있다. 다음으로 로봇을 왼쪽으로 4e9만큼 이동시킨다. 이 또한 4개의 턴이 소모되고, 이렇게 하면 로봇이 다른 모든 고정점에 비해 왼쪽 위에 있음을 알 수 있으므로 같은 방법으로 로봇의 초기 위치의 y-x를 구할 수 있다. 이를 이용해 로봇의 초기 위치를 8개의 턴을 통해 구할 수 있다.

 

E. By the Assignment (01:30 ~ )

cycle의 길이가 홀수이면 이를 구성하는 정점의 l 값이 모두 0이어야 하고, 짝수이면 모두 같아야 함을 보였다. 그러나, 정작 cycle을 찾는 방법을 구현하지 못해 풀지 못했다. BCC (Biconnected Component) 를 이용하면 해결할 수 있다고 하니, 추후에 공부해서 업솔빙해야겠다.

 

블루 퍼포가 떴다

 

나름 괜찮지만 조금 아쉬운 부분들도 있었던 것 같다. F1이 E보다 쉬웠다는 말이 있는데, F1을 좀 더 자세히 보고 풀어보려고 했어야 했다. 그리고 C에서 평소와 다르게 시작 후 약 1시간이 되어서야 푼 점도 아쉽다. 쉬운 문제를 빠르게 풀어내는 연습을 할 필요가 있는 것 같다. 같은 문제를 풀어도, 푼 시간에 따라 퍼포가 거의 200 정도 차이가 나는 걸 보니 그 필요성이 역력히 느껴진다. 골랜디를 조금 돌려야 될 듯 하다.