#23571 John's Gift

2021 icpc 본선 문제.

다양한 풀이가 많은 것 같아서 내 풀이를 남기고자 한다.

 

문제요약.

정렬되지 않는 수열 A, B가 있다. 이때, A에서 딱하나 빼고, B에서 딱하나 빼자.

그리고 적절히 매칭했을때, 매칭된 모든 원소의 차이의 최댓값을 최소화하게 매칭됐을때 A에서 어떤 걸 빼는게 최적인가? 차이의 최댓값을 최소화를 동일하게 할 수 있다면, A중 값이 가장 작은걸 출력하라.

 

1. 빼는게 없다고 가정하면 정렬했을 때 매칭하는게 최적해다.

이건 well known 입니다. 증명은 넘기겠습니다.

 

2. 빼는게 있을 때 이런걸 생각해봅시다. 우선 정렬을 하고 matching을 합니다.

그런 상태에서 차이를 전부 계산해줍시다. 이때 최댓값을 dif라고 합시다.

최적으로 A,B를 하나씩 빼면 dif는 절대 늘지 않습니다.

dif가 되는 index를 잡고 빼주면 변하는게 없기 때문입니다. (dif가 나오는 index가 여러개여도 늘지는 않습니다.)

따라서 우리는 차이가 dif가 되는 모든 index를 변화시켜야 합니다.

따라서 그것들을 모두 변화시킬 수 있는  구간만을 보면 됩니다.

 

 

위 그림은 원래 매칭이고, 아래 그림은 A2을 빼고 ,Bi를 뺀겁니다.

즉 2~i에 차이가 dif가 나오는 모든 index들이 포함되어 있는 경우만 고려해주면 됩니다.

 

3.

i에서 차이는 dif가 되는게 최적해입니다.

지금 최적으로 매칭되어 있기 때문에, dif를 모두 뺐다면 뒤에건 굳이 더 나쁘게 매칭할 필요가 없습니다.

 

이 3가지 사실을 이용하면 각각 A를 빼는 위치마다 빼는 B의 위치가, 고정됩니다. (dif의 index들 중 최소거나 최대)

이를 이용해서 세그트리 2개와 prefix,suffix max를 관리하면 O(nlogn)에 풀 수 있습니다.

update가 없고, 구간이 연속적이어서 세그가 없어도 됩니다.

근데 그냥 대회때는 세그 썼습니다.