Codeforces Global Round 13

Dashboard - Codeforces Global Round 13 - Codeforces

 

만족!

 

말렸다고 생각했는데 의외로 등수가 높게 나왔다! 듣도 보도 못한 글로벌 라운드라 긴장했지만, 3시간이나 내서 참여한 보람이 있었다. 실수를 더 줄이고, 구현을 더 빠르게 하는 연습을 한다면 퍼플을 갈 수 있을 것 같다.

 

 

Prob. A

쿼리마다 1의 개수를 구해서 0 또는 1을 출력하는 문제인데, 문제 해석을 이상하게 해서 a를 저장하지 않고 짜다가 한 번 갈아엎느라 시간이 오래 걸렸다. 문제를 읽지 않고 코딩을 시작하는 게 독이 될 수도 있다는 것을 깨달았다. 사실 엄청 말렸다고 생각해서 바로 탈주할까 고민했는데, 푼 사람이 그렇게 많지는 않아서 그냥 제출했다.

 

Prob. B

대충 벽을 밀어서 도착점까지 가는 문제인데, 아직도 구체화를 어떻게 시키는지 모르겠다. 문제 이해도 잘 안되고 어떻게 풀어야 할지 전혀 감이 안 왔지만, A를 이미 풀어서 탈주할 수도 없었다. 열심히 해석하고 여러 케이스를 직접 그려보았지만 풀이의 구체화가 쉽지 않았고, 그냥 눈에 보이는 DP를 박기로 결정했다. 높이 i인 장애물의 왼쪽, 오른쪽으로 나눠서 dp[n+1][2]를 만들고 경찰차 dp처럼 각 케이스 별로 처리해줬다. 시스텟까지 통과하기는 했지만 이 풀이가 정당한지는 잘 모르겠다.

 

Prob. C

앞쪽부터 시작하는 게 최선임이 자명하기 때문에 브루트포스로 짜서 제출했는데 역시나 9번 데이터에서 TLE가 났다. 시간복잡도가 최악의 경우 O(N^3)이라는 것은 알고 있었지만 그런 케이스가 없는 것 같다고 생각했으나 오산이었다. 이걸 도대체 어떻게 줄여야 하나 한참 고민했는데, 누적합처럼 미리 방문 횟수를 구해놓으면 O(N^2)이 될 것 같았다. 구현을 잘못해서 1틀 후 다행히 AC.

 

Prob. D

그래프 문제인 줄 알고 겁먹었는데, 애드혹이었다. 상당히 다양한 풀이가 나올 수 있는데 나는 그중 누적합을 이용하였다. 우선 a>b 인 경우를 걸러내고 생각해보자. a에서 b를 만들기 위해서는 a에 나오는 1을 쭉 밀어서 b가 나올 수 있어야 한다. 이 과정에서 1의 위치는 왼쪽으로 자유롭게 이동 가능하고, 합쳐질 수도 있다. 따라서 1의 개수가 충분하다면 b를 얼마든지 만들 수 있다. 이는 b의 모든 자릿수(이진법)에서 그 자릿수까지의 a의 1의 개수가 b의 1의 개수보다 많은지 확인하는 것으로 검증할 수 있다. 이 과정에서 잘못된 아이디어가 많이 나왔고, 모두 2번 데이터에서 막혔다.

 

Prob. E

이번엔 진짜로 그래프 문제다. 푼 사람이 많이 없어서 나 또한 풀지 못할 것이라고 생각하기는 했었다. 그리디하게 그래프를 자르는 dfs를 다양한 방법으로 구현했고, 각각 8, 2, 7번 데이터에서 막혔다. 10분 정도 남았을 때 풀 수 없음을 인정하고, 깔끔하게 포기했다.

 

 

전체적으로 멋진 아이디어가 필요한 문제들이 출제되었고, F, G, H 풀이를 살짝 들어봤는데 마찬가지였던 것 같다. 빠르고 완벽하게 푼 문제는 없었지만 크게 막히지 않고 틀릴 것 같은 풀이는 시도하지 않은 것이 레이팅 상승의 결정적인 요인이라고 생각한다.

 

개학날이 코앞으로 다가왔다 ㅠㅠ 내신을 버리지 않는 내가 되도록 노력하자!