2020 3/17 problem solving

오늘도 간략하게.

 

Ice Skates

 

홀의 결혼정리가 동원된다. 홀의 결혼정리를 간략하게 설명하자면, 이분그래프가 존재할 때 그 이분그래프에서 최대매칭이 존재하는 것의 필요충분조건은 이분그래프 한쪽의 모든 부분집합에 대해서 그 크기가 그들과 접한 다른 쪽 부분집합의 크기보다 작거나 같다는 것이다. 그러면 모든 1<=s<=e<=n인 s와 e에 대해 a[s]+a[s+1]+...+a[e]<=(e-s+1+d)k가 성립하면 됨을 알 수 있다.

여기서 누군가 의문을 품을 수도 있다. 사실 내가 의문을 품었었다.  모든 부분집합이라 했는데 왜 연속된 부분집합만 확인하는 거죠? 그러면 연속적이지 않고 떨어져있는 원소들을 생각해보자. 그 원소들은 d개씩 반대쪽 집합에 연결되어있을 것이다. 그러면 반대쪽 집합에서는 원소들이 연속적인 경우와 그렇지 않은 경우로 나눠보자. 연속적인 경우에는 a 배열의 중간에 떨어져있는 부분을 메우는 것이 조금 더 강한 조건임을 알 수 있다. 위의 부등식에서 좌변의 값만 증가하고, 우변은 변하지 않는다. 연속적이지 않은 경우에는 부분집합 자체를 반대쪽 집합이 연속적이게 여러 개로 나눌 수 있다. 그 여러 개에 대해서는 위의 부등식이 성립해야 하고, 거기에 대해 부등식들이 모두 성립하면 그 부분집합에 대해서도 홀의 결혼정리가 성립할 것이다.

허접한 증명은 끝났다. 그러면 이제 식을 변형해보자. b[i]=a[i]-k라 하면, 식이 b[s]+...+b[e]<=k*d가 성립한다. 그러면 b 배열에서 최대 부분합만 빠르게 찾으면 문제가 간단하게 해결된다! 이건 상당히 잘 알려진 테크닉으로 다음 문제에도 쓰이니까 다음 문제에서 설명하겠다. 그렇게 하면 최종 시간복잡도는 O(MlogN)이다.

 

연속합과 쿼리

 

대놓고 최대부분합을 찾으라고 한다. 굉장히 빠르게. 어떻게 해결해야할까? 답은 세그먼트트리다. 세그먼트트리의 각 노드에 그 노드에 해당하는 부분의 최대 부분합을 저장한다. 하지만 그것만 가지고는 노드를 합칠 수 없다. 그 노드의 값들의 합,왼쪽 값들의 합,오른쪽 값들의 합,최대 부분합. 4개를 저장한다. 그러면 노드를 간단하게 합칠 수 있다.

 

이런 식으로 합쳐주면 된다.

하지만 예외가 하나 있다. 구간의 모든 원소들이 0보다 작을 때가 있을 수 있는데, 그러면 최대 부분합은 0을 나타내고 있지만 답은 0이 아니다. 최댓값 세그먼트트리나 스파스테이블을 함께 운용하여 해결해야 한다. 나는 스파스테이블을 썼다. 그럼 최종시간복잡도는 O(MlogN).

 

쿼리와 쿼리

 

설명하기 전에 사진 하나를 보여주겠다.

엄청난 고생을 하여 맞췄다. 시간제한부터 저격데이터까지 정말 힘든 문제다.

우선 적당히 naive한 풀이를 구상해보자. 일단 먼저 M개의 변화쿼리를 받을 때 그 쿼리의 구간을 저장해둔다. 그리고 1번 쿼리를 받을 때마다 L번 변화쿼리부터 R번 변화쿼리까지 순회하면서 그 구간에 v를 업뎃한다. XOR은 교환법칙과 결합법칙이 성립하므로 정당하다. 그리고 2번 쿼리를 받을 때마다 값을 출력해주면 된다. 이 풀이의 시간복잡도는 O(MQlogN)이다. 1000억을 넘는 숫자라 어림도 없다.

 

그러면 복잡도 줄이기에 들어가보자. 복잡도 줄이기에 가장 좋은 건 버킷이다. M개의 쿼리를 사이즈 B의 버킷들로 묶어주자. 그리고 각 버킷마다 그 버킷의 상태를 prefix xor로 저장해놓는다. 버킷의 상태란, 버킷에 해당하는 모든 변화쿼리들의 구간들을 합한 것에서 각 위치에 대해 홀수 번 등장했는지 짝수 번 등장했는지를 저장해두는 것이다. 홀수 번 등장했다면 버킷째로 XOR을 시키는 쿼리에 영향을 받을 것이고, 아니면 아닐 것이다.

 

그리고 1번 쿼리를 날릴 때, 한 버킷에 완전히 들어가지 않는 변화쿼리들은 그냥 세그에 그 구간을 바로 업데이트해주고 아닌 경우에는 그 버킷에 해당하는 배열에 그 숫자를 xor해준다. 이것은 그 버킷 전체에 그 숫자가 xor되었다는 얘기다. 그리고 2번 쿼리에서는 먼저 그 구간에 해당하는 구간합부터 구해주고, 버킷들을 순회하면서 그 버킷에 저장된 숫자를 보고, prefix xor을 이용하여 그 버킷의 (s,e) 부분에 저장된 숫자가 몇 번 XOR되는지 확인한다. 홀수 번이라 1이 나오면 결과값에 그 수를 XOR해주면 된다.

 

시간복잡도는 버킷사이즈를 B라 했을 때 1번 쿼리에 대해 BlogN+M/B이고, 2번 쿼리에 대해 M/B이다. 총 시간복잡도는 O(BQlogN+QM/B)라고 할 수 있다. 하지만 시간이 빡빡하므로 펜윅 트리로 최적화를 넣어주자. 그리고 버킷사이즈는 적절히 300 근처로 넣어주면 AC를 어찌어찌 받을 수 있다.