Educational Codeforces Round 126

문제풀기

lml 2022. 4. 11. 21:16

C의 첫 제출이 19:07인데 부등식에 등호 하나 잘못 걸었다가 4틀하고 01:25:22 AC가 되었다.

E에서 생각해냈던 처음 아이디어가 Mo's인데 구현이 아주아주 더러워서 실패. 구현했어도 아마 TLE

A. Array Balancing

전형적인 DP문제처럼 생겼지만, 그냥 그리디하게 a_i와 b_i를 swap해도 된다.

B. Getting Zero

그냥 1 ~32768에 대해 미리 모두 전처리를 해두고 쿼리를 받을 때마다 뱉으면

어떤 사람들은 이 문제를 (쿼리를 받고 나서 계산) + (쓸모없는 map 사용)으로 TLE hack을 당하기도 했다.

C. Water the Trees

당연히 2씩 물을 주는게 이득이기 때문에 2씩 물을 몇 번 줄 수 있는지 확인하면 된다.

-> 이렇게 해서 풀면 되는데 문제에서 숫자를 nlgn으로 준 것으로보아 이분탐색도 허용한 듯하다.

D. Progressions Covering

-> 이를 제일 그리디하게 진행하는 방법은 맨 뒤에서부터 n씩 가해주는 것이다.

-> segtree를 이용하여 각 순간순간에 얼마만큼 감소하였는지 구해주었다.

-> segtree 없이도 이것의 구현이 가능하다.

-> 현재 몇 번의 operation이 위에 가해졌는지 확인해주고 이만큼 감소치에 가해주면 된다. (editorial 참고)

E. Narrow Components

-> 위에서 이야기하였듯이 처음으로 생각했던 풀이는 Mo's이다. 근데 nsqrtn이 통과할지는 애매하다.

-> 그래서 두 번 째로 생각했던 것은 segtree이다. 예상복잡도는 anlgn이다.

-> TLE를 맞았는데 조금 더 이쁘게 깎으면 될 것 같다.

-> 사실 info끼리의 덧셈 계산의 형태를 보니 L, R boundary만 쓰는 형태로 구조를 짜면 통과가 될 것 같다.

-> prefix sum을 이용하여 적당한 a[R] - a[L - 1] 정도로 답을 구할 수도 있을지 모른다는 생각을 할 수 있다.

-> 그렇다면 저 a가 무엇이 되어야 하는가? 저 a는 (각 열에 있는 component 수) - (그 사이 행으로 인한 연결)일 것이다.

-> 다만 케이스들을 넣다보면 1번행과 3번행이 연결되었는데 두 번 빠지며 생기는 예외들이 있음을 알 수 있다.

-> 111 / 101 / 111이 대부분의 생각에 예외가 되어준다. 위의 아이디어에 따르면 (1 + 2 + 1) - (2 + 2) = 0이 된다.

-> 근데 다행히도 특정 구간 [l, r]에서 1번행과 3번행이 연결되어 있으려면 111과 101만으로 이루어져 있어야 한다.

-> 111 / 101 / 101 ... / 101 / 111로 이루어진 모든 구간 [L, R]를 저장해주자.

-> 그렇다면 쿼리에 주어지는 [qL, qR] 사이에 있는 위와 같은 구간 [L, R]의 개수를 구해서 더해주면 된다.

-> 마찬가지로 아마 anlgn이고 prefix같은 느낌으로 미리 처리를 해주면 저 로그도 뗄 수 있을 것이다.

여담으로 오일러 정리로 V - E + F 값을 이용하는 풀이도 있다.

F. Teleporters

-> 보자마자 답에 대한 이분탐색을 생각해낼 수 있다.

-> 위의 과정을 위해서는 반드시 F(개수) = (총 energy)인 함수 F가 필요한데 이를 떠올리기가 쉽지 않다.

-> 우선 쉽게 구할 수 있는 함수인 G(최대 간격의 크기) = (필요한 추가 Teleporter의 수)를 구하였다.

-> 그렇다면 Teleporter의 개수가 주어질 때 최소의 (최대 간격의 크기)를 이분탐색으로 구할 수 있다.

-> 하지만 최대 간격의 크기를 구하였다 치더라도 남는 Teleporter를 어디에 배치해야하는지 알기 쉽지 않다.

직관적으로 당장 Teleporter을 설치했을 때 더 많이 energy를 줄이는 쪽으로 설치해야한다.

-> 또한 직관적으로 일정한 a_i와 a_(i + 1)사이에 설치되는 Teleporter가 늘수록 이 감소량은 줄어든다.

-> 따라서 특정한 값 x에 대해 감소량이 x 이상인 동안에만 Teleporter를 설치한다고 하자.

-> 그렇다면 감소량인 x값에 대해서 이분탐색을 해주면 된다.