IOI19 Arranging Shoes

문제

https://oj.uz/problem/view/IOI19_shoes

문제 보기 - Arranging Shoes (IOI19_shoes) :: oj.uz

왼쪽 신발과 오른쪽 신발이 여러 개 있고, 각 신발마다 크기가 같은 신발끼리만 짝을 맞출 수 있다. 처음에는 신발들이 막 아무렇게나 섞여 있을 때, 이 신발들을 짝이 맞는 신발들끼리 붙어 있으며, 같은 짝에서는 왼쪽 신발, 오른쪽 신발 순서대로 배열해야 한다. 사용할 수 있는 연산은 인접한 두 신발을 swap하는 연산일 때, 연산의 최소 횟수를 구한다.

($N<=100000$)

풀이

https://koosaga.com/236

일단 가장 먼저 최종 배치 상태에서 매칭의 순서만 정해진다면 단순 인버전을 구하는 문제로 변형된다. 이제 최적의 매칭이 어떠한 꼴로 구성되는지만 결정해 보면 답은 $O(NlogN)$ 에 구할 수 있는 방법이 생겼으니, 최적의 매칭의 순서에 집중하자.

 

Observation 1 : 

서브태스크별로 풀다 보면 얻을 수 있는 아이디어는 가장 왼쪽 신발을 잡고, 이 왼쪽 신발이랑 같은 크기의 반대쪽 신발을 가장 왼쪽 위치까지 끌고 온다. 그 다음 제일 왼쪽 신발이 오른쪽일 경우 이 두 신발만 swap해준다. 이 과정을 왼쪽 두 신발을 제거했다고 생각하고 반복한다.

 

증명은 다음과 같다. 최적해가 있다고 생각하자.

일단 뭔지는 몰라도 최적해에서 가장 왼쪽 신발과 매칭되는 신발이 있을 것이다. 가장 왼쪽 신발은 A, 그 신발과 매칭될 신발을 B라 하자.

이 상태에서 우리가 할 수 있는 모든 swap의 종류는 다음 세가지로 나뉜다.

AB-AB swap / AB-else swap / else-else swap

AB-AB swap 은 최대 1개 일어나고, AB-else swap은 else들의 상대적 위치에 아무런 영향을 주지 못한다. 이를 이용하여 생각하면, A, B의 최적해에서의 위치가 있을 때 둘이 만나기 위해서는 적어도 둘 사이의 거리만큼의 이동은 필요하고, 만약 만난 위치가 가장 왼쪽에 위치하지 않는다면 이는 다른 신발들이 움직일 때 뛰어넘어야 하는 장애물의 역할만 할 뿐이다. 다시 말해, 어떤 최적해가 이 두 신발의 위치가 제일 왼쪽이 아니라면 이 둘의 위치를 다시 제일 왼쪽으로 옮겨주면 되기 때문에 매칭을 왼쪽으로 한다고 생각해도 된다.

 

이제 만약 같은 신발이 여러 개가 있다고 한다면, 짝이 맞는 신발 중 가장 왼쪽에 있는 신발을 끌어오면 된다. 그 이유는 가장 왼쪽이 아닌 신발을 끌어오는 최적해가 있다면, 그 신발을 끌어오다가, 가장 왼쪽에 있는 신발의 위치에서 내려놓고 가장 왼쪽 신발을 끌어온다고 생각해도 변하는 것은 없기 때문에 이러한 형태로 바꿀 수 있다.

 

이제 마지막으로 특정 종류의 신발을 모두 스택에 담아 놓고 하나씩 빼며, 어떠한 구간에서 아직 삭제하지 않은 신발의 수를 세는 문제는 펜윅 트리를 이용하여 해결할 수 있다.

 

시간 복잡도 : $O(NlogN)$

 

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;

int S[MAXN+10], N;
vector<int> pos[MAXN+10];
bool vis[MAXN+10];
ll ans;

int tree[MAXN+10];
void update(int i) { for(; i<=N*2; i+=(i&-i)) tree[i]++; }
int query(int i) { int ret=0; for(; i>0; i-=(i&-i)) ret+=tree[i]; return ret; }
int query(int l, int r) { return query(r)-query(l-1); }

ll count_swaps(vector<int> _S)
{
	int i, j;

	N=_S.size()/2;
	for(i=1; i<=2*N; i++) S[i]=_S[i-1];

	for(i=2*N; i>=1; i--) pos[S[i]+N].push_back(i);

	for(i=1; i<=2*N; i++)
	{
		if(vis[i]) continue;
		int j=pos[-S[i]+N].back();
		ans+=j-i-1-query(i, j);
		pos[S[i]+N].pop_back(); pos[-S[i]+N].pop_back();
		vis[i]=true; vis[j]=true;
		update(i); update(j);
		if(S[i]>0) ans++;
	}	
	return ans;
}