AtCoder Beginner Contest 243 (ABC 243) 후기

성적

1827등으로 조금 아쉬운 성적이다. C에서 구현 실수가 있었고 D에서는 무지성으로 제출을 해서 도합 10분의 페널티를 받았는데 두 페널티가 없었다면 레이팅이 올랐을 것이다.

아는 선에서 설명하는 해설

A: ABC A치고 조금 당황스러운 문제긴 했는데 샴푸가 바닥날 때까지 러시안룰렛을 돌리면 된다.

 

B: 시키는 대로 naive하게 하면 $O(N^{2})$의 시간 복잡도로 정답을 받을 수 있다.

 

C: 오른쪽으로 이동하는 좌표, 왼쪽으로 이동하는 좌표를 따로 관리한다. 단순한 구현을 위해 map<int, set<int>> 을 사용했는데 각 좌표에 대해 lower_bound로 반대방향으로 이동하는 점과 충돌하는지 검사하면 된다.

 

D: 일종의 오프라인 쿼리로 볼 수 있다. 주어진 스트링에 대해 온라인으로 계산하지 말고 깊이의 변화, 오른쪽 노드로 가는 횟수를 카운트하여 한꺼번에 계산하면 오버플로우를 방지할 수 있다.

 

E: 플로이드 워셜로 최단경로를 계산한 다음 간선 A <-> B 에 할당된 비용 C를 가지고 비교할 것이다. A -> B / A <- B로 향하는 최단 경로의 중간 노드를 확인할 때 C보다 적은 비용이 감지되면 해당 간선은 필요 없게 된다. 이렇게 필요 없는 간선을 세면 된다.

후기

E번을 풀지 못해 자책을 했는데 1600점이 책정되서 조금 편안해졌다. 시간이 허락하면 백준에서 플로이드 워셜 문제를 좀 풀도록 해야겠다.