여기 있는 셋입니다.
감사합니다.
#11709 Toliets
우선 정렬을 하기 이전에, 언제 불가능한 상태가 될까를 생각해본다..
총 2N명이 있는데, N초 안에 완수하기 위해서는 한번도 놓치면 안된다는 뜻이다.
즉 매초마다 2개의 화장실이 전부 채워져 있어야 한다.
그런데 M은 공용화장실만 사용 가능하므로, 아직 사용하지 않은 M의 개수만큼의 시간은 최소한으로 걸린다.
따라서 현재 시간 + 남은 M의 개수 > N이 되버리면, 불가능하다.
문제 상황이 어떻게 흘러가는지를 생각해보자.
만약 특정 시점에 화장실이 전부 비어져 있고, M이 연속되게 나오는 경우를 보자..
ex) MMM.....MF~
그럼, M의 연속된 개수가 x라고 하면 x초 동안, 공용화장실에는 M이 여자화장실에는 F가 들어가게 된다.
즉 뒤의 x개만큼, F를 앞으로 당겨 사용하게 된다.
반대로 화장실이 비어 있을 때 F가 연속되게 나온다고 생각해보자.
FFFFF....F (F가 x개)
그럼 x/2번 공용화장실이 차게 된다.
즉 이 정보들을 조금 종합하고, 발상적인 생각을 하면 M을 -1로 F를 1로 놓고 prefix sum을 구한다.
그러고 나서 prefix sum의 max값을 mx라고 하면, mx/2+F의 개수>N이면 불가능하다.
반대로 말하면 mx/2 <= N- (F의 개수) 면 된다.
이때 N-F의 개수는 input에 따라 고정된 상수이다.
그럼 이제 우리는 적절히 정렬해서 불만도의 최댓값을 최소로 하면 된다.
subtask 2까지를 풀어보자.
여기서 parametric search를 이용하면 문제를 결정문제로 환원할 수 있다.
불만도의 최댓값이 K일때, 최적으로 배치하면 가능한가?
이를 풀기 위해서 다음과 같은 그리디한 전략을 생각한다.
뒤에서 부터 K개의 M을 문자열의 맨 앞으로 보낸다.
그 후에 위에서 설명한 것처럼 M을 -1로, F를 1로 놓고 prefix sum을 구한다.
prefix sum에서 나왔던 값중 max 값을 mx 라고 하면 mx/2 + F의 개수 <= N인지로 결정문제를 해결 할 수 있다.
시간복잡도는 O(nlogn)이다.
풀태스크는 어떻게 해결해야 할까?
사실 사용하는 전략은 똑같다. 동일하게 이분탐색을 하자.
다만, n이 매우 크기 때문에 K개의 M을 무지성으로 앞으로 보내는 것은 할 수 없다.
우리는 문자열이 반복된다는 점을 이용해서 뒤에서 부터 보면서 M을 앞으로 보내자.
이때 다음과 같은 생각을 해보자.
문자열 S를 앞에서 부터 볼때, prefix sum을 pre[S]라고 하고, prefix sum중 최댓값을 mx[S]라고 하면,
두 문자열 S와 T를 붙이면
pre[S+T]=pre[S]+pre[T]가 된다.
또, mx[S+T]=max(mx[S],pre[S]+mx[T])이다.
그럼 S에 T를 K번 반복한 문자열을 붙이면 어떻게 될까?
pre[S+T*K]= pre[S]+pre[T]*K
mx[S+T*K]=max(mx[S],pre[S]+mx[T], pre[S]+(K-1)*pre[T]+mx[T])가 된다. (잘 생각해보자...)
식을 떠올려냈다면, O(1)에 S에 T를 K번 반복한 문자열을 붙이게 되었을 때, prefix sum의 최댓값을 빠르게 구할 수 있다.
따라서 우리는 뒤에서 부터 M을 하나씩 앞으로 보내서 K개가 되는 시점에 보면
x번째 문자열에서 M을 다 사용했으면
뒤에는 전부 F일 것이고 (즉 이는 F 1개짜리 문자열을 그 개수만큼 곱한 것으로 볼 수 있음)
앞에서부터 봐오면, O(m)의 시간복잡도에 pre값과 mx값을 구해올 수 있다는 점이다.
따라서 결정문제가 O(m)에 풀린다.
O(mlogn)에 풀태스크가 해결된다.
결국 전체 문제를 푸는 아이디어와 생각의 흐름은
- prefix sum으로 동치조건으로 문제 바꾸기
- 이분탐색으로 결정문제로 바꾸는 아이디어
- 반복되는 문자열을 합치는 걸 어떻게 빨리 합칠 것인지
3가지였던 것 같다.
#25260 Event Hopping
이 문제는 매우 오랫동안 고민했는데 진전이 없었다.
문제를 그래프로 표현한다고 생각하면 특정한 정점 쌍들에 대한 최단경로의 길이를 빠르게 구하는 문제가 된다.
이를 set을 이용해 빠르게 구현해 내면 O(QNlogN) 정도에 구현이 가능해서 아마 25점~ 40점까지 받을 수 있을 것 같다.
승형님에게 어느정도 힌트를 얻었는데 Line Friends라는 문제랑 유사하다고 했다.
이미 풀려있어서 가보니까 문제가 조금은 다르긴 한데 어느정도 방향성을 잡을 수 있었다.
선분 a의 시작점을 Sa, 끝점을 Eb로 정의하면 다음과 같은 경우를 생각해보자.
x to y의 쿼리가 주어진다고 해보자.
x에서 적절히 K번의 이동을 통해서 Ei에서 끝날수도 있고, Ej에서 끝날수도 있다고 하자. (Ei<=Ej)
만약 우리가 목표로 하는 y에 대해 Ej<=Sy라면, Ei보다는 Ej로 도착하는 시나리오를 선택하는게 최적이다.
Ey=Ej는 자명하니 넘어가고, Ej<Ey라고 가정해보자.
그렇다면, Ei를 선택한 최적해에서도 처음으로 Ej<=Ez인 선분 z가 존재할 것인데, 이 선분은 Ej->Ez를 선택해도 같은 최적해이다. 따라서 같은 거리라면 Ei를 고르는 경로보다는, Ej를 고르는 경로가 이득이다.
그렇다면 다음과 같은 결론을 얻을 수 있다.
끝점이 Sy 이상일 때까지 최소한으로 이동한다.(최대한 멀리멀리씩 뛰면서)
그리고 그럴때의 도착 지점에서 y로 갈 수 있는지를 살펴본다. (즉 도착지점이 Ey이 이하임)
이는 sparse table과 이분탐색을 이용한다.
이렇게 하면 subtask 1과 5가 긁혀 30점을 받는데, 다음과 같은 예제를 구현하기에 어렵다.
7 1
1 2
2 4
4 6
6 8
8 10
0 11
11 13
1 3
이는 E6이 11인데, sparse table을 타고 가면 6으로 타고 가기 때문이다...
문제가 되는 부분은 우리가 멀리멀리 뛰어갈때 Ey보다 커지면 문제가 생긴다.
이를 해결하는 아이디어는 뒤에서부터 본다는 것이다.
즉 y->x로 보면, Ey보다 커지는 경우는 생각을 안하기 때문에 넘겨도 된다.
이 발상도 쉽지는 않은 것 같다.
- 그리디한 조건을 파악하기
- 거꾸로 뒤집어서 구하는 것이 동치임을 깨닫기
#5469 Fish
이 문제는 감을 못 잡아서 풀이를 보고 공부했다.
연쇄적으로 먹는다고 생각하지 않고, 가장 큰 물고기가 나머지를 전부 먹는다고 생각해도 동일하다.
같은 정수를 가지는 물고기들은 가장 큰 것 만 의미가 있다는 것은 쉽게 보일 수 있다.
여기까지 생각하고 생각을 멈췄었고, 다음은 풀이를 보고 이해한 내용이다.
위의 블로그 글을 많이 참고하였다.
경우의 수를 잘 세어본다는 것이 풀이의 끝이다.
물고기가 가지고 있는 돌의 색에 대해, 동일한 색의 물고기들 중에 가장 큰 크기로 색을 정렬해보자.
즉 1~K까지의 색에 대해서 C(x)->max(색이 x인 물고기의 크기)로 정의해보자.
그럼 우리가 어떤 집합을 셀 때 다음과 같이 세어 줄 수가 있다.
1. y가 집합의 물고기들의 색 중 하나일때 max(C(y))= 집합내의 가장 큰 물고기의 크기
각 색에 대해 가장 큰 물고기가 의미가 있기 때문에, 가장 큰 물고기는 색과 대응된다.
즉 C(x)로 색들을 정렬하면,
i를 순회하면서 i번째 색을 볼때, (1+cnt[1])*(1+cnt[2])*...(1+cnt[i-1])*(1+cnt[i])를 더해주면 된다.
단 (cnt[x]는 C[i]/2보다 작은 색이 x인 물고기의 개수)
2. 이제 1번의 여집합을 세줘야 한다.
가장 큰 물고기의 색이 x라고 하자
내가 C()값이 가장 큰 물고기가 아니기 때문에, C()값이 더 큰 물고기를 그 색중 제일 큰 물고기로 교체하면
1번 케이스로 얻을 수 있는 집합이 있는데, 우리는 이 경우를 이미 세어 주었기 때문에 고려해줘야 한다.
즉 다른 말로 모든 물고기들을 같은 색의 가장 큰 물고기로 바꾸어보면,
이미 세어준 경우가 아닌 경우를 고려해보자.
다음과 같은 경우이다. (색,크기)
(1,1)
(1,2)
(1,6)
(2,4)
-------------------
(2,10)
이처럼 (2,4)를 (2,10)으로 바꾸면, (1,6)을 얻을 수 없어 불가능하다.
이런 경우를 세 줄 때, 현재 내가 보는 색 x에 대해 C(x)/2이상이면서 가장 작은 크기를 넘어가는
걸 이분탐색으로 빠르게 구해주면 된다.
곱셈은 세그트리를 써주면 된다.
이런경우를 머리를 싸매고 모두 세 주면 문제를 해결 할 수 있다.
4번은
https://blog.naver.com/vermeil_/223580595763
대체한다.