AtCoder Beginner Contest 294

항상 앳코더랑 코포는 계속 참가했는데 풀이를 쓰는 게 귀찮아서 계속 블로그를 방치하고 있었다.

너무 블로그를 방치하는 거 같아서 이제부터 대회 이후 간단히라도 쓰려고 한다.

 

A. Filter

code

 

길이가 \(N\)인 배열을 입력받은 뒤 짝수인 원소만 출력하면 되는 문제이다. 문제에서 시키는대로 하면 된다.

 

B. ASCII Art

code

 

\(H\times W\)크기의 정수 배열을 입력받는다. 각 배열은 0이상 26 이하의 정수이다. 각 정수 \(x\)를 \(x\)번째 대문자 알파벳으로 치환하여 출력하고, \(x\)가 0이면 마침표로 치환하려 출력하면 된다. 역시 문제에서 시키는대로 하면 된다.

 

C. Merge Sequences

code

 

길이가 \(N\), \(M\)인 두 배열 \(A\), \(B\)가 주어진다. 두 배열의 값은 모두 서로 다른 정수이며 오름차순이다. 두 배열을 하나의 오름차순 배열로 합쳤을 때 몇 번째 숫자가 되는지를 출력하면 된다.

 

큐에 두 배열의 값을 넣고, 두 큐의 맨 앞에 있는 숫자 중 작은 숫자를 뽑는 과정을 반복하면 된다. 숫자를 뽑을 때 몇 번째로 뽑은 숫자인 지를 기록하여 출력하면 \(O(N+M)\)에 풀 수 있다.

이 과정은 merge sort에서 merge하는 과정과 동일하다.

 

D. Bank

code

 

총 \(N\)명의 손님이 존재한다. 각 손님의 번호는 1부터 \(N\)이다. 이제 세 종류의 쿼리를 처리해야 한다.

첫 번째 쿼리는 한 번도 부르지 않은 손님들 중 번호가 가장 작은 손님을 부른다.

두 번째 쿼리는 불려진 적이 있는 \(x\)번 손님의 요구를 처리한다.

세 번째 쿼리는 한 번 이상 불려진 손님 중 요구를 처리하지 않은 손님의 번호를 다시 부른다.

이제 세 번째 쿼리에 의해 불려진 손님의 번호를 모두 출력하면 된다.

총 \(Q\)종류의 쿼리를 처리해야 한다.

 

한 번 이상 부른 손님의 번호를 c++의 set으로 관리하면 된다.

먼저 첫 번째 쿼리는 1번 손님, 2번 손님, 3번 손님... 순으로 부르게 된다. 따라서 첫 번째 쿼리를 수행할 때마다 불러야 할 손님의 번호를 1씩 늘려가면서 set에 추가하면 된다.

두 번째 쿼리는 단순히 \(x\)를 set에서 제거하면 된다.

세 번째 쿼리는 set에 있는 숫자 중 가장 작은 번호를 출력하면 된다.

 

위와 같이 set을 이용하여 각 쿼리를 처리해 총 \(O(QlogN)\)의 시간복잡도로 모든 쿼리를 처리할 수 있다.

 

E. 2xN Grid

code

 

\(2\times L\)의 평면이 주어진다. 각 칸에는 숫자가 적혀있다. 이제 같은 숫자가 적혀있는 열의 개수를 출력하면 된다.

 

문제 자체는 쉬워보이지만, 입력 형식을 보면 그렇지 않다는 것을 알 수 있다. 일단 \(L\)이 최대 \(10^{12}\)이라 단순하게는 구할 수 없다는 것을 알 수 있다. 대신, 각 행은 \(N\)개의 구간으로 구분되고, 각 구간에는 똑같은 숫자들이 적혀있다. 구간의 개수는 최대 \(10^5\)개이다.

 

따라서 두 행의 구간을 합쳐도 많아야 \(2\times 10^5\)개 밖에 안된다는 것을 알 수 있다. 또한 이 구간에는 모든 열이 동일하다. 따라서 이 구간들 중 열의 두 숫자가 동일한 구간들의 길이의 합을 빠르게 구하면 문제를 풀 수 있다.

 

이는 투 포인터를 응용하면 풀 수 있다. 각 포인터는 첫 번째 행과 두 번째 행의 구간의 시작점을 가리킨다. 맨 처음에는 두 포인터가 각 행의 첫 번째 구간을 가리키도록 한다. 각 포인터가 가리키는 구간 중 겹치는 부분의 길이를 구하고, 만약 겹치는 부분에 있는 열의 두 숫자가 동일하면 최종 정답에 해당 길이만큼 더한다.

이제 두 포인터 중 다음 구간의 시작점이 더 앞에 있는 포인터를 움직인다. 이를 포인터가 맨 끝으로 갈 때까지 반복하면 된다. 자세한 구현 방식은 위 링크의 c++ 코드를 참고하면 좋을 것이다.

 

F. Sugar Water 2

code

 

Takahashi는 \(N\)개의 소금물이 든 비커를, Aoki는 \(M\)개의 소금물이 든 비커를 가지고 있다. Takahashi의 소금물 하나와 Aoki의 소금물 하나를 섞으면 새로운 소금물이 생긴다. 이렇게 총 \(NM\)개의 소금물을 만들 수 있다. 이제 이 \(NM\)개의 소금물 중 \(K\)번째로 농도가 큰 소금물의 농도를 출력해야 한다.

 

먼저 \(NM\)이 최대 25억이므로, 모든 경우를 계산하는 것은 매우 어렵다. 따라서 모든 경우의 수를 계산하는 접근법 보다는 다른 방법으로 접근해야 한다.

주어진 문제처럼 \(K\)번째 농도를 구하는 문제의 경우에는 이분탐색으로 풀리는 경우가 많기 때문에 \(NM\)개 중에서 \(x\) 이상의 농도를 가진 소금물의 개수를 구하는 방법을 생각해 보았다. 만약 소금물의 개수를 \(O(NlogN)\) scale로 계산할 수 있다면 문제를 풀 수 있을 것이다.

 

일단 Aoki의 소금물을 하나 고르자. 이 소금물에는 \(C\)만큼의 소금과 \(D\)만큼의 물이 있다. 이제 Takahashi의 \(N\)개의 소금물 중, Aoki의 소금물과 섞었을 때 농도가 \(x\) 이상이 되는 소금물의 개수를 계산해야 한다. 이렇게 하면 어렵지만 수식을 쓴 뒤 정리하면 문제의 접근법이 보인다.

 

먼저 Takahashi의 i번째 소금물에는 \(A_i\)의 소금과 \(B_i\)의 물이 있다. 이제 소금물을 섞었을 때 농도가 \(x\)이상이라는 것을 수식으로 표현하면 아래와 같다.

 

\(\frac{A_i + C}{A_i + B_i + C + D} \ge x\)

\(A_i - x(A_i+B_i) \ge x(C+D)-C\)

 

즉, 위 수식을 만족하는 \(i\)의 개수를 구하면 된다. 그런데 이는 전처리를 해두면 \(O(logN)\)안에 구할 수 있다. 먼저 \(A_i - x(A_i+B_i)\)를 모든 \(i\)에 대해 계산해두고 이를 정렬하자. 그렇다면 c++의 lower_bound 함수를 이용하여 \(x(C+D)-C\)보다 큰 소금물의 개수를 구할 수 있다.

 

따라서 Aoki의 소금물을 하나 골랐을 때, 이 소금물과 섞었을 때 농도가 \(x\)이상이 되도록 하는 Takahashi의 소금물의 개수를 \(O(logN)\)에 구할 수 있다. 따라서, \(NM\)개의 소금물 중 농도가 \(x\)이상인 소금물의 개수를 \(O(MlogN)\)에 구할 수 있다.

 

이분 탐색을 이용하면 \(K\)번째 소금물의 농도를 구할 수 있다. 이 문제는 double 변수형인 정답을 이분탐색으로 찾아야 한다. 탐색을 50번 정도 해야 정확한 답이 되며, 나의 경우 안정성을 위해 100번 반복한다.자세한 구현 방식은 위 링크의 c++ 코드를 참고하면 좋을 것이다.

 

G. Distance Queries on a Tree

code

 

그냥 HLD 기초 문제이다. 백준의 트리와 쿼리1 문제와 매우 흡사하다. 이 문제를 풀고 싶다면 트쿼1을 구글에 검색해보자.

 

후기

E번은 오랜만에 구현하는 투 포인터라 살짝 당황했었다. 그래도 침착하게 구현하니 바로 맞출 수 있었다.

E번 풀고 F번을 풀려고 했는데 생각보다 어려워서 조금 헤맸다. 그래서 standings으로 가니 F를 건너뛰고 G번이 더 많이 풀린 것을 보았다. G번을 읽어보면 트쿼1과 그냥 똑같은 문제인 걸 알 수 있다. 그래서 그냥 코드 긁어와서 제출했다. 물론 배열 크기를 바꾸지 않아서 2번 틀렸다;;

 

최근 G번에 어려운 알고리즘의 기초 버전으로 나오는 거 같다. 그래도 조금만 문제를 꼬아서 내면 어떨까 하는 생각이 든다. 애초에 F번보다 G번이 점수가 높은데, G번 문제가 더 많이 풀릴 정도로 너무 쉽게 나오는 게 이상하긴 하다.

 

Ex 문제는 아무리 봐도 풀이가 안떠오르길래 바로 editorial을 보았다. 맨 아래로 스크롤을 내려보니 \(O(M1.74^M)\)같은 괴상한 시간복잡도가 있길래 바로 건너뛰었다. 언젠간 공부하지 않을까? 근데 지금은 아닌 거 같다.