문제 이해

26599번: 용 조련사 룰루 이번 문제는 다시 오랜만에 ps 공부를 시작하면서 추천받은 문제이다.

문제 풀이

코드포스 div2 B번으로 나올 법한 문제였다.
우선 학살이 일어날지를 쉽게 판별하기 위해 $P_i$를 정렬하였다. 처음에는 쉽게 생각해서 $P_i$를 쭉 돌면서 $d = P_i - P_{i-1}$가 한번이라도 M 초과이면 불가능, 모두 M 이하면 가능이라고 생각했다. 하지만 쉽게 반례를 생각할 수 있었다.

5 5
1 9 10 11 12

Answer
YES
3 2 1 4 5

Output
NO

사실 가장 큰 $P_i$ 4개에서 서로 그 차이가 M 이하이기만 하면 전부 YES라는 사실을 깨달을 수 있었다. $P_{n-2}, P_{n-3}$을 먼저 보내고 나머지를 보낸 후 가장 힘이 센 용 두마리, 즉 $P_{n-1}, P_{n}$를 보내면 항상 학살이 일어나지 않기 때문이다.

코드

#include <bits/stdc++.h>
#define INIT() std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL);
typedef long long ll;
typedef std::pair<ll, ll> P;

#define SZ 1000005
int n, m;
std::vector<P> p;

int main(){
	INIT();
	std::cin >> n >> m;
	for(int i=0; i<n; i++){
		int x;
		std::cin >> x;
		p.push_back({x, i+1});
	}
	sort(p.begin(), p.end());
	bool flag = false;
	int idx = -1;
	for(int i=p.size()-1; i>0; i--){
		int diff = p[i].first-p[i-1].first;
		if(diff>m){
			flag = true;
			idx = i;
			break;
		}
	}
	if(flag){
		if(p.size()<5 || idx>p.size()-4) std::cout << "NO\n";
		else{
			std::cout << "YES\n";
			for(int i=p.size()-3; i>=0; i--){
				std::cout << p[i].second << ' ';
			}
			for(int i=p.size()-2; i<p.size(); i++){
				std::cout << p[i].second << ' ';
			}
		}
	}
	else{
		std::cout << "YES\n";
		for(auto &v: p){
			std::cout << v.second << ' ';
		}
	}
	return 0;
}

코드가 전체적으로 깔끔하지는 않지만 최대한 직관적으로 적어보았다.

정리

오랜만에 PS 문제를 풀었더니 코드가 생각처럼 쉽게 적히지 않았다. 그래도 코드포스 div.2 B 정도 되는 문제를 어떻게어떻게 잘 푼 것 같아서 다행이다.