BOJ 2431 신호 장애

문제 링크입니다.

위아래 결정하기

위아래를 결정하면 열차의 방향도 따라옵니다. 어차피 위아래로 움직이는 건 공짜니까 입력으로 들어오는 방향은 깔끔하게 무시해도 좋습니다. 최종적으로 열차의 배치는 간격이 일정한 루프가 되어야 합니다. 그러기 위해서 열차를 적당히 위아래로 쪼개서 배치하는 게 좋겠습니다.

갑작스럽지만, 열차를 현재 위치에 따라 오름차순 정렬한 뒤 위아래 지그재그로 배치하는 게 최선입니다. 4개의 열차가 각각 순서대로 $a, b, c, d$ ( $a < b < c < d$ ) 에 위치해 있다고 생각합시다. 지그재그로 배치하는 것과 안쪽을 위로, 바깥쪽을 아래로 밀어넣는 방식을 비교했을 때 어느 쪽이 더 거리의 최솟값과 최댓값의 차가 커지는지 확인해 보세요. 그걸 Exchange Argument와 비슷한 사고 방식을 따라 일반화하는 것으로 이를 증명할 수 있습니다.

간격 맞추기

루프의 전체 길이와 열차의 수를 알고 있는 우리는 두 열차 사이의 간격을 구할 수 있습니다. 한 열차를 기준으로서 고정했다고 치면, 다른 열차들은 그 열차에 대한 상대적 위치가 이미 결정되어 있습니다. 그러면 답은 아무리 커봤자 각 열차의 현재 기준에 대한 상대적 위치로부터 최종적으로 있어야 되는 상대적 위치까지의 거리 중 최댓값이겠네요.

하지만 우리는 기준이 되는 열차 역시 움직일 수 있습니다. 이를 거꾸로 해석하면, 다른 모든 열차에 한쪽 방향으로 추가 속도를 줄 수 있는 겁니다. 반대로 움직여야 되는 경우에는 정지해 있으면 되고, 필요한 경우에는 가속을 받아 2배 속도로 움직일 수 있게 되는 겁니다. 따라서 각 방향마다 떨어져 있는 거리 중 최댓값의 합을 반으로 나눈 값이 답이 됩니다. 이는 현재 기준에 대한 상대적 위치 - 최종적으로 있어야 되는 상대적 위치의 최솟값과 최댓값을 구하는 것으로 알아낼 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

ll a[101010];
long double delta[101010];

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	ll m, n; cin >> m >> n;
	for(int i = 0; i < n; i++){
		char c; cin >> a[i] >> c;
	}
	sort(a, a+n);
	for(int i = 1; i < n; i += 2) a[i] = 2*m-a[i];
	sort(a, a+n); a[n] = a[0]+2*m; long double mn = 0, mx = 0;
	for(int i = 1; i <= n; i++){
		delta[i] = delta[i-1]+a[i]-a[i-1]-(long double)(2*m)/n;
		mn = min(mn, delta[i]);
		mx = max(mx, delta[i]);
	}
	cout << fixed << setprecision(12) << (mx-mn)/2;
}