3 - 1. 다양성이 힘이다.
문제를 요약하자면,
1) N개의 수들이 있다.
2) 어떤 한 Group에서 '실력' 이라는 값을 그 Group 내의 임의의 두 사람에 대해 값의 차를 모두 더한 값으로 정의한다.
3) N개의 수 들 중 연속한 K개를 모아 만들 수 있는 N-K+1개의 Group 중 '실력' 이 가장 높은 팀의 실력값을 구하여라.
로 요약 가능하다.
풀이 : Splay Tree
먼저 어떤 Group에 원소를 추가한다고 생각해 보자. 이 원소를 추가했을 때의 '실력' 값의 변화는 무엇일까?
원소의 값을 a라고 하면,
x 가 Group에 속하는 원소일 경우
1) x > a 이면 x - a
2) x < a 이면 a - x 가 더해진다. (등호는 1, 2 중 어디에 붙어도 상관없다.)
이는 원래 Group이 정렬된 상태일 경우, lower_bound와 prefix - sum을 이용하여 log |Group|에 구할 수 있다.
원소가 추가된 이후에도 이러한 방식으로 '실력' 값을 갱신하려면, 추가된 후에도 Group이 정렬된 상태여야 한다.
즉 원소의 추가/삭제 및 위 쿼리를 해결 가능한 자료구조가 필요해진다.
우리는 정말 유용한 자료구조 Splay Tree를 사용 가능하다.
원소의 key 값을 바탕으로 Splay Tree를 만들어 보자.
각 노드마다 key값, 서브트리의 노드 개수 size, 그리고 서브트리의 key값의 합인 sum을 저장하자.
위 쿼리는 어떻게 해결 가능할까?
먼저, 쿼리를 행하고자 하는 원소 a를 루트로 만든다. (Splay)
그럼 루트 왼쪽의 서브트리에는 a보다 작은 원소들이 있고, 오른쪽의 서브트리에는 a보다 큰 서브트리가 있을 것이다.
왼쪽에 대해서는 a * (a보다 작은 원소의 개수) - (a보다 작은 원소들의 합) 을 더해주면 되고,
오른쪽에 대해서는 (a보다 큰 원소들의 합) - a * (a보다 큰 원소들의 개수) 를 더해주면 된다.
이는 각각 루트에 대해서 왼쪽 자식, 오른쪽 자식의 size, sum을 의미한다.
이제 쿼리를 시행 가능하니, 문제는 끝났다. 왼쪽의 K개를 넣고 쿼리를 처리하면서 첫 번째 '실력'을 계산하고,
그 Group의 맨 왼쪽 원소를 제거하고, 그 다음 오른쪽 원소를 넣는 것을 반복하면서 '실력'을 계산하면 된다.
위와 같은 방법을 사용하면 N - K + 1개의 Group의 실력을 모두 구할 수 있고, max인 값을 구해주면 된다.
3 - 2. 원룸 구하기
풀이 : Sweeping, Deque, Segment Tree, Segment Tree Beats
일단 좌표의 범위가 너무 크므로 좌표압축을 한다.
각 원룸마다 범위가 최소여야 하므로,
x좌표가 늘어나는 방향으로 스위핑하면서 deque의 앞에 넣고,
조건을 만족하는 경우가 생기면 계속 조건을 만족할 때까지 deque의 뒤에서 원소를 빼는 것을 생각해볼 수 있다.
먼저, 조건을 만족한다는 것을 어떻게 확인할까?
이는 간단한 Segment Tree를 이용해 확인 가능하다.
구간 minimum query, 점 update를 지원하는 세그먼트 트리를 만들고,
종류 i인 곳이 deque에 들어가면 i인 점의 수를 1 증가시키고, 빠져나오면 1 감소시키자.
종류 1 ~ K에 대해 range minimum query를 적용시켰을 때 값이 1 이상이면 모든 종류의 가계가 있는 것이다.
먼저 deque에서 원소를 뺄 때, deque 내부의 원룸들에 대해서 값을 minimum으로 갱신해줘야 한다.
원룸들을 좌표 순으로 정렬했을 때 deque 내부의 원룸들을 생각해보면, 일종의 투 포인터 비슷하게 움직인다는 것을 알 수 있다.
그 두 포인터 사이 원소들에 대해, (deque의 top에 있는 것의 좌표 - deque에서 빼낸 원소의 좌표) 중 최소인 값이 정답이 된다.
Range Minimum Update가 지원되는 자료구조가 필요하다.
어떻게 해결할까?
Segment Tree Beats를 이용하여 해결 가능하다.
https://www.acmicpc.net/problem/17474 를 약간 변형하면 된다.
17474번: 수열과 쿼리 26
길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 L R X: 모든 L ≤ i ≤ R에 대해서 Ai = min(Ai, X) 를 적용한다. 2 L R: max(AL, AL+1, ..., AR)을 출력한다. 3
www.acmicpc.net
이제 앞에서 스위핑 해주었으므로, 뒤에서부터 스위핑을 한번 더 하면 된다.
3 - 3 생존 신호
소수점이 있는 문제이다. 1, 2일차의 Output Only보다 어렵고, 코드로 어떻게 하는지 막막한 문제이다.
하지만 1, 2일차와 다르게 시뮬레이터를 이용해 푸는 것이 가능하고, 재미있으므로 손으로 하였다.
-------
4 - 1 선물 상자
N명의 사람이 원형으로 앉아있다. i번째 사람은 D_i의 수치를 가지고 있다. 몬스터는 최초에 1번에서 시작하여 시계 방향으로 사람들을 세어 M번째 사람에게 간다. 그리고 그 사람의 수치를 감소시킨다. 사람의 수치가 0이 되면, 그 사람은 원에서 제외된다. 마지막에 살아남는 사람을 구하면 된다.
풀이 : Splay Tree
이 문제에서 눈여겨 보아야 하는 것은 N의 제한이다. N <= 2000으로, 상당히 작은 편이다.
먼저, 시작이 i일 때, 다음 수는 i + M % (size of 원판) 이 될 것이다.
이러한 수들을 나열하다 보면, 싸이클이 형성된다.
이 싸이클은 원판에 남아있는 사람들의 수에 따라 달라진다.
형성된 싸이클에서 생각해보면..
start -> .. -> start 꼴이 될 것이다.
이 싸이클에서 가장 작은 수를 생각해보자. (가장 작은 수가 여러 개라면, start에 제일 가까운 원소를 생각한다.)
가장 작은 수를 a라고 하면, 이 싸이클을 a - 1번 돈 뒤, start 부터 a까지 이동하게 되면 사람 한 명이 제거될 것이다.
이 상황에서 가장 큰 문제는, 노드를 제거해야 한다는 것이다.
링크드 리스트를 이용하자니, 임의 원소 접근이 O(N)라는 사실이 발목을 잡는다.
노드의 삭제가 자유롭고, 각 원소 접근도 O(N)보다 빠른 자료구조가 무엇이 있을까?
그것은 바로 Splay Tree이다.
index를 key로 하는 Splay Tree를 생각하면 된다.
이는 수열과 쿼리 시리즈 중 스플레이 트리를 사용하는 문제들이 쓰는 테크닉이다.
예시를 들자면... https://www.acmicpc.net/problem/17607
17607번: 수열과 쿼리 31
길이가 N이고 0과 1로만 이루어진 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 L R: A의 [L, R] 구간에 들어있는 수의 순서를 뒤집는다. 즉, 이 쿼리의 결과
www.acmicpc.net
위에 언급되었던 싸이클에서 st -> .. -> a 사이 원소들은 a만큼 빼고, a -> .. -> start 사이 원소들은 a - 1만큼 제거한다.
이후 start 지점을 다시 잡아주면 된다.
시간복잡도는 N^2logN. N <= 2000임을 생각하면 넉넉하다.
4 - 2. 파스칼
파스칼 삼각형에서 부분 정사각형의 합을 정의한 뒤, 합이 K가 되는 정사각형의 개수를 찾는 문제이다.
풀이 : Offline Query, Two Pointer, 휴리스틱 전처리, 이분 탐색
이 풀이의 Key Point는, nCk가 상상 이상으로 크다는 것이다.
아무리 K <= 1e18이라고 해도, k = 6정도만 되어도 n <= 3100이다.
N <= 3100인 N에 대해 삼각형들의 합을 모두 전처리한다.
전처리하는 방법에 대해 설명하자면, 먼저 위를 고정시키고 아래로 사이즈를 늘려갈수록 값은 증가한다.
즉 쿼리를 모두 받아두고 앞에서부터 맞는지 투 포인터 비슷하게 확인해주면 된다.
이제 N C 6을 포함하는 삼각형들에 대해선 고려할 필요가 사라졌다.
고려해야 할 것은 이제 15개의 삼각형들 뿐이다. 이는 이분탐색으로 찾아주면 된다.
if(m >= 3100) cnt += 2;
if(m >= 3102) cnt += 2;
if(nC2(m) >= 3100) cnt += 2;
if(nC3(m) >= 3100) cnt += 2;
if(nC4(m) >= 3100) cnt += 2;
if(nC5(m) >= 3100) cnt += 2;
if(Check_1(m) >= 3100) cnt += 2;
if(Check_1(m-3) >= 3100) cnt += 2;
if(Check_2(m) >= 3100) cnt += 2;
if(Check_3(m) >= 3100) cnt += 2;
if(Check_3(m-4) >= 3100) cnt += 2;
if(Check_4(m) >= 3100) cnt += 2;
if(Check_5(m) >= 3100) cnt += 2;
if(Check_6(m) >= 3100) cnt += 2;
if(Check_6(m-5) >= 3100) cnt += 2;
if(Check_7(m) >= 3100) cnt += 2;
if(Check_8(m) >= 3100) cnt += 2;
if(Check_9(m) >= 3100) cnt += 2;
if(Check_10(m) >= 3100) cnt += 2;
if(Check_10(m-6) >= 3100) cnt += 2;
:blobfearful:
4-3 낙하 데미지
섭테 1, 2밖에 풀지 못하였다.
서브테스크 1은 그냥 단순 DP이다. 높이순으로 정렬한 뒤 낮은 것부터 갱신해주면 된다.
서브테스크 2는 다익스트라 알고리즘과 스위핑으로 해결하였다.
먼저 for all i -> c_i = 0일 경우,
"가능한 인접한 선분"에 무조건 내려야 함을 알 수 있다.
이제 x좌표 순으로 선분을 스위핑하면서, Set에 넣는다.
어떤 선분을 set에 insert하는 과정에서,
그 선분 바로 위에 있는 선분과 바로 아래에 있는 선분과만 연결해주면 된다.
따라서 E <= 2N이고, 다익스트라 알고리즘은 ElogV이므로 잘 돌아간다.
(참고로 메모리 제한이 뻑뻑한 편이다. 잘못하면 MLE를 받을 수 있다.)