BOJ 29111 Последовательности

문제 링크입니다.

문제 요약

$1$ 이상 $N+1$ 이하의 정수 중 $N$개를 선택해, 선택한 정수를 두 번씩 나열했을 때 같은 두 수 사이의 거리가 그 수와 같은 수열을 구성하세요. 예를 들어 $N = 2$일 때 $3 1 1 3$은 조건을 만족합니다.

풀이

Langford Pairing이라는 게 있습니다. $1$부터 $N$까지의 정수를 두 번씩 나열해 각 수 사이에 해당 수만큼의 다른 원소가 끼어있도록 구성한 수열이에요. 이는 우리가 원하는 수열에서 각 원소에 $1$을 뺀 것과 같습니다. 비슷한 예로 $0$부터 $N-1$까지의 정수로 만드는 Skolem Pairing이라는 것도 있습니다.

Langford Pairing은 $N \equiv 0 \mod 4$ 또는 $N \equiv 3 \mod 4$일 때, Skolem Pairing은 $N \equiv 0 \mod 4$ 또는 $N \equiv 1 \mod 4$일 때 존재합니다(이거 하나만으로 24507번 문제도 해결할 수 있습니다).

그래서 $N \equiv 2 \mod 4$ 꼴인 경우만 구성하면 문제를 해결할 수 있어요. 가능한 한 가지 구성 방법으로는, $N \equiv 3 \mod 4$ 꼴의 Langford Pairing에서 다른 모든 수에 정확히 한 번씩 끼이는 수를 제거하고 다른 모든 수에서 1을 빼는 방법이 있습니다. 제가 사용하는 Langford Pairing의 구성 방법에서는 이러한 수가 항상 유일하게 존재합니다.

코드

#include<bits/stdc++.h>
#define pb emplace_back
using namespace std;
using vi = vector<int>;

vi get_skolem(int n){
	assert(n%4 == 0 || n%4 == 1);
	if(n == 1) return {0,0};
	if(n == 4) return {1,2,1,3,2,0,0,3};
	if(n == 5) return {2,3,4,2,1,3,1,4,0,0};
	vi ret;
	
	if(n%4 == 0){
		int k = n/4;
		for(int i = 4*k-1; i >= 1; i -= 2) ret.pb(i);
		ret.pb(4*k-2);
		for(int i = 1; i <= 4*k-1; i += 2) ret.pb(i);
		ret.pb(2*k-2);
		for(int i = 4*k-4; i >= 2*k; i -= 2) ret.pb(i);
		for(int i = 2*k-4; i >= 2; i -= 2) ret.pb(i);
		ret.pb(4*k-2); ret.pb(2*k-2);
		for(int i = 2; i <= 2*k-4; i += 2) ret.pb(i);
		ret.pb(0); ret.pb(0);
		for(int i = 2*k; i <= 4*k-4; i += 2) ret.pb(i);	
	}
	else{
		int k = (n-1)/4;
		for(int i = 4*k; i >= 2; i -= 2) ret.pb(i);
		ret.pb(2*k+1); ret.pb(4*k-1);
		for(int i = 2; i <= 4*k; i += 2) ret.pb(i);
		ret.pb(2*k+1);
		for(int i = 4*k-3; i >= 2*k+3; i -= 2) ret.pb(i);
		for(int i = 2*k-1; i >= 1; i -= 2) ret.pb(i);
		ret.pb(4*k-1);
		for(int i = 1; i <= 2*k-1; i += 2) ret.pb(i);
		ret.pb(0); ret.pb(0);
		for(int i = 2*k+3; i <= 4*k-3; i += 2) ret.pb(i);
	}
	return ret;
}

vi get_langford(int n){
	assert(n%4 == 0 || n%4 == 3);
	if(n == 3) return {3,1,2,1,3,2};
	if(n == 4) return {4,1,3,1,2,4,3,2};
	vi ret;
	int k; if(n%4 == 0) k = n/4; else k = n/4+1;
	for(int i = 4*k-3; i > 2*k-1; i--) if(~i&1) ret.pb(i);
	for(int i = 2*k-2; i > 0; i--) if(i&1) ret.pb(i);
	ret.pb(4*k-2);
	for(int i = 1; i < 2*k-1; i++) if(i&1) ret.pb(i);
	ret.pb(4*k-1);
	for(int i = 2*k; i < 4*k-2; i++) if(~i&1) ret.pb(i);
	if(n%4 == 0) ret.pb(4*k); else ret.pb(2*k-1);
	for(int i = 4*k-3; i > 2*k-1; i--) if(i&1) ret.pb(i);
	for(int i = 2*k-2; i > 0; i--) if(~i&1) ret.pb(i);
	ret.pb(4*k-2); ret.pb(2*k-1);
	for(int i = 1; i < 2*k-1; i++) if(~i&1) ret.pb(i);
	ret.pb(4*k-1);
	for(int i = 2*k; i < 4*k-2; i++) if(i&1) ret.pb(i);
	if(n%4 == 0){ret.pb(2*k-1); ret.pb(4*k);}
	return ret;
}

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);
	int n; cin >> n; vi ans;
	if(n%4 == 0 || n%4 == 1){
		ans = get_skolem(n);
		for(auto& i : ans) cout << i+1 << ' '; return 0;
	}
	if(n%4 == 3){
		ans = get_langford(n);
		for(auto& i : ans) cout << i+1 << ' '; return 0;
	}
	if(n%4 == 2){
		ans = get_langford(n+1);
		int ban = 0; for(int i = 1; i < ans.size()-1; i++) if(ans[i-1] == 1 && ans[i+1] == 1) ban = ans[i];
		for(auto& i : ans) if(i != ban) cout << i << ' '; return 0;
	}
}