2018 제 4회 삼성 SCPC 1차 예선 후기, 풀이

딱 이 맘때 쯤 PS에 입문해서 STL쓰는 법 부터 완전탐색 DFS BFS DP 등등 배우기 시작해서 진짜 딱 1년 되는 시점이다. 그 때에도 3회 SCPC 접수를 하고 있었고, 이제 막 시작하는 입장이라 참가는 안 했었다.

1년이면 길다면 길고 짧다면 짧은 기간이지만 나름 괜찮은 속도로 성장한 것 같다. 물론 다른 높은 대학에서 PS하시는 분들 보면 1년만에 퍼플, 오렌지 달고 백준 1000문제 찍으시고 그러던데... 머리가 다른것도 있지만 문제 수 부터 거의 2배 차이나기 때문에 노력의 차이가 아닌가 싶다. 가끔 블로그 보다보면 나도 열심히 해야지 자극 받다가도 막상 하면 너무 힘들어서 금방 쉬러가거나 집중력이 흐트러진다. 

 

아무튼, 1년동안에 공부한 것을 테스트하는 자리이기도 하고, 생에 첫 전국단위 대회이기때문에 내 인생에 의미있는 대회 중 하나다. 그래서 PS를 한 번도 안 해본 사람들만 거르는 1차 예선이라고 들었지만 전날부터 긴장하고 아침 7시부터 일어나 각성제 마구마구 투여하고 준비하고 있었다. 그도 그럴 것이 4시부터 11시 까지 알바때문에 다른 사람들보다 7시간의 시간이 덜 주어진 것과 마찬가지여서 더 긴장하고 준비하고 있었다.

 

1차 예선 난이도는 하~하중 정도인 것 같다. 작년 1차 예선에 비하면 1, 2, 3번이 지나치게 쉽고 5번은 풀지는 못 했지만 오늘 20분 정도 생각해보니 솔루션이 생각났기 때문에 똑똑한 사람들은 정말 쉽다고 생각하고 풀었을 것이다. 4번은 감도 안 잡 히긴하지만.

 

1번

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
template<typename a, typename b>
ostream& operator<<(ostream& os, const pair<a, b>& pai) {
	os << pai.first << ' ' << pai.second;
	return os;
}
template<typename a, typename b>
istream& operator>>(istream& is, pair<a, b>& pai) {
	is >> pai.first >> pai.second;
	return is;
}
 
#ifdef ONLINE_JUDGE
#define endl '\n'
#endif
 
#define INF (INT_MAX / 2)
 
#define MAX_N 200001
 
int n, k;
int arr[MAX_N];
 
int ans = 0;
 
int main() {
	int t;
	cin >> t;
	for (int tc = 1; tc <= t; tc++) {
		ans = 0;
		cout << "Case #" << tc << endl;
 
		cin >> n >> k;
		for (int i = 0; i < n; i++)
			cin >> arr[i];
		sort(arr, arr + n);
		for (int i = 0; i < n; i++) {
			int idx = upper_bound(arr, arr + n, arr[i] + k) - arr;
			ans = max(ans, idx - i);
		}
		cout << ans << endl;
	}
 
	return 0;
}

 

2번 문제보다 푸는데 오래걸린 문제다. 만점자도 2번문제보다 적다. 정말 naive하게 풀면 모든 실력값이 distinct하므로 set에 전부 넣고 배열정렬 후 for문으로 돌면서 $k$초과 차이나는 녀석들 전부 지우는 작업을 set이 empty할 때 까지 해주면 된다. 

나도 처음엔 이렇게 짯는데 너무 코드가 맘에 안 들어서 임시 저장해놓고 다시 생각해봤는데, 정렬해놓고 upper_bound로 $k$이하로 차이 나는 녀석들의 개수를 셀 수 있는데, 그 개수의 max값이 정답이 될 수 밖에 없었다. $k$이하 차이나는 녀석들 끼리는 무조건 다른 버스에 타야되기 때문에 그 max값이 버스의 대수가 될것이다.

 

근데 sort에 n * upper_bound만 썼을 뿐인데 2.5s라는 미친속도가 나왔다. 대회 유의사항에 cout cin 쓸 때에는 아무것도 쓰지 말래서 sync_with_stdio와 cin.tie를 빼고 endl만 '\n'로 고쳐서 썼는데 endl이 문제였다. 

코드그라운드에서 practice할 때 여러번 테스트해 본 결과 sync_with_stdio(false)와 cin.tie(NULL)을 쓰고, endl을 '\n'으로 고쳐서 쓰면 tc마다 다르겠지만 내가 본 최악의 경우 6배까지 차이가 난다. sync_with_stdio(false)와 cin.tie(NULL)을 쓰고, endl을 '\n'으로 고치치 않고 쓰는 것이 시간을 최소로 걸리게하면서 부분점수를 받을 수 있는 방법이다. sync_with_stdio(false)와 cin.tie(NULL)을 안 쓰고 endl을 '\n'으로 고쳐서 쓸 써도 부분점수를 받고 시간을 더 줄일 수 있지만 약간 더 느리다. 

sync_with_stdio(false)와 cin.tie(NULL)을 쓰고 endl을 '\n'으로 고쳐서 쓰면 부분점수를 못 받는다. 무조건 둘 중 하나만 하자.

 

2번

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
template<typename a, typename b>
ostream& operator<<(ostream& os, const pair<a, b>& pai) {
	os << pai.first << ' ' << pai.second;
	return os;
}
template<typename a, typename b>
istream& operator>>(istream& is, pair<a, b>& pai) {
	is >> pai.first >> pai.second;
	return is;
}
 
#ifdef ONLINE_JUDGE
#define endl '\n'
#endif
 
#define INF (INT_MAX / 2)
 
#define MAX_N 10001
 
int n;
vector<int> p;
 
bool isPelindrome(int number) {
	vector<int> v;
	while (number) {
		v.push_back(number % 10);
		number /= 10;
	}
	for (int i = 0; i < v.size() / 2; i++)
		if (v[i] != v[v.size() - 1 - i])
			return false;
	return true;
}
 
int main() {
	for (int i = 1; i <= 9; i++)
		p.push_back(i);
	for (int i = 10; i <= 10000; i++) 
		if (isPelindrome(i))
			p.push_back(i);
 
	int t;
	cin >> t;
	for (int tc = 1; tc <= t; tc++) {
		cout << "Case #" << tc << endl;
 
		cin >> n;
 
		bool printed = false;
		for (int i = 0; i < p.size() && !printed; i++)
			if (p[i] == n) {
				cout << 1 << ' ' << n << endl;
				printed = true;
			}
		if (printed)
			continue;
 
		for (int i = 0; i < p.size() && !printed; i++)
			for (int j = 0; j < p.size() && !printed; j++)
				if (p[i] + p[j] == n) {
					int arr[2] = { p[i], p[j] };
					sort(arr, arr + 2);
					cout << 2 << ' ' << arr[1] << ' ' << arr[0] << endl;
					printed = true;
				}
		if (printed)
			continue;
 
		for (int i = 0; i < p.size() && !printed; i++)
			for (int j = 0; j < p.size() && !printed; j++)
				for (int k = 0; k < p.size() && !printed; k++)
					if (p[i] + p[j] + p[k] == n) {
						int arr[3] = { p[i], p[j], p[k] };
						sort(arr, arr + 3);
						cout << 3 << ' ' << arr[2] << ' ' << arr[1] << ' ' << arr[0] << endl;
						printed = true;
					}
		if (printed)
			continue;
		cout << 0 << endl;
	}
 
	return 0;
}

 

심각하게 간단하다. 회문인 수를 10000까지 모두 구하면 198개가 나오는데, naive하게 198개 전부 돌려보면 된다. 1개로 만들어지면 출력, 아니면 2개로 만들고 출력, 아니면 3개로 만들고 출력. 불가능하면 0을 출력하랬지만 불가능한 경우는 10000이하로 없는 것 같다.

 

3번

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
template<typename a, typename b>
ostream& operator<<(ostream& os, const pair<a, b>& pai) {
	os << pai.first << ' ' << pai.second;
	return os;
}
template<typename a, typename b>
istream& operator>>(istream& is, pair<a, b>& pai) {
	is >> pai.first >> pai.second;
	return is;
}
 
#ifdef ONLINE_JUDGE
#define endl '\n'
#endif
 
#define INF (INT_MAX / 2)
 
#define MAX_N 200001
 
int n, m;
set<int> adj[MAX_N];
queue<int> q;
 
int cnt = 0;
 
int main() {
	int t;
	cin >> t;
	for (int tc = 1; tc <= t; tc++) {
		cnt = 0;
		for (int i = 0; i < MAX_N; i++)
			adj[i].clear();
		cout << "Case #" << tc << endl;
 
		cin >> n >> m;
		while (m--) {
			int u, v;
			cin >> u >> v;
			adj[u].insert(v);
			adj[v].insert(u);
		}
 
		for (int i = 1; i <= n; i++) 
			if (adj[i].size() == 2) {
				int u = *adj[i].begin();
				int v = *adj[i].rbegin();
				if (adj[u].count(v))
					q.push(i);
			}
 
		while (!q.empty()) {
			int here = q.front();
			q.pop();
			if (adj[here].size() != 2)
				continue;
			cnt++;
 
			int u = *adj[here].begin();
			int v = *adj[here].rbegin();
 
			adj[here].clear();
			adj[u].erase(here);
			adj[v].erase(here);
 
			if (adj[u].size() == 2) {
				int w = *adj[u].begin();
				int y = *adj[u].rbegin();
				if (adj[w].count(y))
					q.push(u);
			}
			if (adj[v].size() == 2) {
				int w = *adj[v].begin();
				int y = *adj[v].rbegin();
				if (adj[w].count(y))
					q.push(v);
			}
		}
		cout << n - cnt << endl;
	}
 
	return 0;
}

 

와 이걸 어떻게 풀지? 싶지만 간단하다. 그냥 없앨 수 있는 캡슐 없애고, 없애고나서 없앨 수 없는 캡슐 찾아서 또 없애고.. 더 이상 없앨 수 없을 때 까지 반복하면 된다. 이게 왜 되냐면, 캡슐을 없애고나면 새로 없앨 수 없는 캡슐은 생길지언정 없애지 못 하는 캡슐은 절대 생기지 않는다. 딱 예외가 예제에 있는 삼각형모양이거나, 모든 vertex의 degree가 2인 경우이다. 하나를 없애면 다른 거기에 연결된 없앨 수 있었던 vertex를 못 없애는데, 이 경우는 없앨 후보를 queue에 넣어두고 처리할 때 queue에서 pop하고 난 뒤 진짜 없앨 수 없는 녀석인지 한번 더 판단해주면 된다.

없앨 수 없는 녀석인 지 판별하고 없애기 위해서는 degree가 2인지 판별하고, 연결된 두 vertex가 서로 연결되어 있는지 확인해야하고, 두 vertex에 없애는 vertex와의 edge를 끊어야하는데, 그러기 위해서는 인접리스트로 관리하면 시간복잡도가 더 늘어난다.(구현하다보면 어 이거 순차탐색해야하나? 하는 순간이 있다.) lower_bound로 삽입해서 정렬상태를 유지해주면 두 vertex가 연결 되어있는지는 빠르게 판단 가능하나, edge를 끊어주려면 vector에 pop이 없기 때문에 인접리스트로 불가능해 보인다. 또, 인접행렬로 하자니 느리기도 느리거니와 꺼림찍한데, vector가 아니라 set으로 관리하며 모든 고민이 해결된다.

 

4번

당최 해법이 생각이 안 난다. 그룹1은 간단하다. n!으로 전부 해보면 된다. 그룹2는 도저히 해답이 안 보인다.

degree가 높은 녀석부터 중간의 index를 부여하면 예제 1번은 나오지만 2번에서 안 나온다. 그래서 조금 생각해보니 degree가 높은 녀석부터 중간의 index를 부여하되, 같은 degree를 가진 녀석들은 그래프의 중심에서 가까운 순서대로 index를 부여해봤다. 그래프의 중심에 있는지 판별은 bfs 2번이면 되기 때문에 어렵지 않았다.

하지만, 역시나 틀린 생각이고 그래도 tc그룹1 만점이 40점인데 43점정도 받았다. 3점 올렸으니 만족

 

5번

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
template<typename a, typename b>
ostream& operator<<(ostream& os, const pair<a, b>& pai) {
	os << pai.first << ' ' << pai.second;
	return os;
}
template<typename a, typename b>
istream& operator>>(istream& is, pair<a, b>& pai) {
	is >> pai.first >> pai.second;
	return is;
}
 
#ifdef ONLINE_JUDGE
#define endl '\n'
#endif
 
#define INF (INT_MAX / 2)
 
#define MAX_M 200005
 
int n, m, l;
pii arr[MAX_M];
 
pii ans;
 
int ccw(pii a, pii b, pii c) {
	ll value = (ll)(b.first - a.first) * (c.second - a.second) - (ll)(b.second - a.second) * (c.first - a.first);
	if (value == 0)
		return 0; // 일직선
	return value > 0 ? 1 : -1; // 1 : 반 시계 방향 -1 : 시계 방향
}
 
int main() {
	int t;
	cin >> t;
	for (int tc = 1; tc <= t; tc++) {
		ans = { INF, 0 };
		cout << "Case #" << tc << endl;
 
		cin >> n >> m >> l;
		int start = -1;
		int end = -1;
		int wantTo = n / 2;
		bool c = n % 2;
		for (int i = 0; i < m + 1; i++) 
			cin >> arr[i];
		sort(arr, arr + m + 1);
		for (int i = 0; i < m + 1; i++) {
			if (start == -1) {
				pii p1 = { wantTo, wantTo + c };
				pii p2 = { wantTo - 1, wantTo + c + 1 };
				pii p3 = arr[i];
				pii p4 = { wantTo, wantTo };
				pii p5 = { wantTo + 1, wantTo + 1 };
				if (ccw(p1, p2, p3) != 1 && ccw(p4, p5, p3) != -1)
					start = i;
			}
			if (start != -1 && end == -1) {
				pii p1 = { wantTo, wantTo };
				pii p2 = { wantTo + 1, wantTo + 1 };
				pii p3 = arr[i];
				if (ccw(p1, p2, p3) == -1)
					end = i;
			}
		}
		if (start == -1) {
			cout << -1 << endl;
			continue;
		}
		if (end == -1)
			end = m + 1;
 
		for (int i = start; i < end; i++)
			if (arr[i].second < ans.first)
				ans.first = arr[i].second;
 
		if (start != 0) {
			int a = wantTo * 2 + c;
			int b = (arr[start].second - arr[start].first);
			if (ans.first > (a + b) / 2) {
				ans.first = (a + b) / 2;
				if ((a + b) % 2)
					ans.second = 1;
				else
					ans.second = 0;
			}
		}
 
		if (end != m + 1) {
			int a = 0;
			int b = (arr[end - 1].first + arr[end - 1].second);
			if (ans.first > (a + b) / 2) {
				ans.first = (a + b) / 2;
				if ((a + b) % 2)
					ans.second = 1;
				else
					ans.second = 0;
			}
		}
 
		if (ans.first == INF)
			cout << -1;
		else if (ans.second == 1)
			cout << ans.first * 2 + ans.second << ' ' << 2 << endl;
		else
			cout << ans.first << ' ' << 1 << endl;
	}
 
	return 0;
}

 

그룹1번만 맞췄는데, $L$이 1이면 문제가 매우 간단해진다.

 

 

 

$(N / 2, N / 2)$점을 잡고, 기울기가 1, -1인 직선을 긋고 그 사이에 있는 모든 공간에 조명을 달면 무대를 모두 커버할 수 있다. 즉, 노란 범위 안에 있는 모든 점들 중 가장 y값이 작은 녀석의 y좌표가 정답 후보 중 하나 일것이다. 또 후보군이 있는데, $(N / 2, N / 2)$점에 기울기가 1인 직선과 만나는 직선, 그리고 -1인 직선과 만나는 직선의 교점도 정답 후보로 올라갈 것이다. 총 세 부호중 y좌표가 가장 작은 값이 정답이다.

먼저 글미에서 노란 범위안에 있는 점들을 찾는 방법은 CCW를 돌리면 된다. 그리고 교점은 직선의 기울기와 지나는 점이 모두 주어져 있으므로 방정식을 바로 구할 수 있고 간단하게 교점을 구할 수 있다.

 

문제는 만점을 받는 코든데, 아직 정해를 못 들었지만 오늘 20분정도 생각한 결과, y좌표를 파라메트릭을 돌리면 될 것같다. 사실 대회중간에도 최소y좌표를 찾는다는 점과 점을 $L$개 놓을 수 있다는 점을 보고 아 이거 파라메트릭냄새를 너무 풍긴다 싶었는데 결정함수을 어떻게 구성할지 바로 생각 안 나서 '3문제 만점 받고 두 문제 부분 점수 비비면 통과지 뭐'라는 생각으로 생각 안 하고 취침했다.

아무튼 결정함수는 x축과 평행한 mid(파라메트릭)좌표를 절편으로 갖는 직선을 죽 그은 후, 다각선분과 만나는 교점들을 모두 구한다. 그리고 (0, 0)을 포함해야 하므로 (0, 0)에서 기울기가 1인 직선을 그어서 아까 그은 x축과 평행한 직선과의 교점을 구하고(y = x와 y = mid 이므로 x = mid가 되겠지?)그 교점보다 작은 아까 구한 점들 중 x좌표가 큰 점에 전등을 설치한다. 그리고 그 전등에서 기울기가 -1인 직선을 그어서 무대에 닿는 x좌표를 구하고, 그 좌표에서 (0, 0)에서 기울기가 1인 직선을 그은 것 처럼 그어서 교점 구하고 교점보다 x좌표가 작은 점들 중 x좌표가 가장 큰 점에 전등을 설치하고.... 하는 작업을 반복하면 전등 설치 개수를 최소화 하면서 무대 전체를 커버칠 수 있는지 판별이 가능하다. 다각선분들 이루는 점이 $M + 1$개 이고 $M + 1$보다 절대 교점이 많이 생기지 않으므로 최대로 잡아 봤자 결정함수는 O($MlogM$)이 되고, 파라메트릭에 O($logY_{max} = log10^{12}$)이므로 전체 시간복잡도는 O($MlogM * log10^{12}$)가 될 것이다.

내가 만들어 본 몇개 tc는 다 돌아가고 결정함수도 단조 함수이기 때문에 가능할 것이라 생각한다. 빨리 코드그라운드에 1회 예선문제가 올라와서 5번 문제부터 빨리 풀어보고싶다. 

 

 

====

8월 9일 경 scpc에 예선문제들이 전부 올라와서 5번부터 풀어보았다.

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
template<typename a, typename b>
ostream& operator<<(ostream& os, const pair<a, b>& pai) {
	os << pai.first << ' ' << pai.second;
	return os;
}
template<typename a, typename b>
istream& operator>>(istream& is, pair<a, b>& pai) {
	is >> pai.first >> pai.second;
	return is;
}
 
#ifdef ONLINE_JUDGE
#define endl '\n'
#endif
 
#define INF (INT_MAX / 2)
 
#define MAX_M 200005
 
ll n, m, l;
pll arr[MAX_M];
 
bool decide(ll mid) {
	vector<pll> candidate;
	for (int i = 0; i < m - 1; i++) {
		if (arr[i].second < arr[i + 1].second) {
			if (arr[i + 1].second <= mid)
				candidate.emplace_back(arr[i + 1].first - arr[i + 1].second, arr[i + 1].second);
			else if (arr[i + 1].second > mid  && arr[i].second <= mid)
				candidate.emplace_back(arr[i].first + (mid - arr[i].second) - mid, mid);
		}
		else {
			if (arr[i].second <= mid)
				candidate.emplace_back(arr[i].first - arr[i].second, arr[i].second);
			else if (arr[i].second > mid && arr[i + 1].second <= mid)
				candidate.emplace_back(arr[i].first + (arr[i].second - mid) - mid, mid);
		}
	}
 
	int lastIndex = 0;
	ll maxValue = 0;
	ll remain = l;
	while (remain--) {
		int nextIndex = upper_bound(candidate.begin(), candidate.end(), pll(maxValue, LLONG_MAX)) - candidate.begin();
		if (lastIndex && lastIndex == nextIndex)
			break;
		for (int i = lastIndex; i < nextIndex; i++)
			maxValue = max(maxValue, candidate[i].first + candidate[i].second * 2);
		lastIndex = nextIndex;
	}
	return maxValue >= n;
}
 
ll parametricSearch() {
	ll l = 0, r = 2000000000000LL;
	while (l <= r) {
		ll mid = (l + r) / 2;
		if (decide(mid))
			r = mid - 1;
		else
			l = mid + 1;
	}
	return l;
}
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
 
	int tc;
	cin >> tc;
	for (int th = 1; th <= tc; th++) {
		cout << "Case #" << th << endl;
 
		cin >> n >> m >> l;
		n *= 2;
		m++;
		for (int i = 0; i < m; i++) {
			cin >> arr[i];
			arr[i].first *= 2;
			arr[i].second *= 2;
		}
 
		ll value = parametricSearch();
		if (value == 2000000000001LL)
			cout << -1 << endl;
		else if (value % 2)
			cout << pll(value, 2) << endl;
		else
			cout << pll(value / 2, 1) << endl;
	}
 
 
	return 0;
}

 

생각한대로 진행하면 맞게 나온다. 어차피 점들이 전부 기울기가 1, -1로 구성되서 좌표만 알면 그 직선의 x절편이 나오므로 선분 구조체를 안 만들고 점으로만 판별하는게 훨 편하다. 

문제는, 다각선분 위의 전구의 후보들을 뽑는 방법이 잘 못 되었는지 3일 넘게 고생했다. 아무리 생각해봐도 제대로 후보를 뽑았고, testcase 자동생성기로 몇 십 억개를 돌려봤는데도 전부 맞다고 떠서 그냥 다른 방법으로 뽑으니 바로 ac떴다.

처음에 생각한 방법은, y좌표가 mid보다 작은 값들은 전부 후보에 넣고, mid보다 큰 점은 그 점이 위로 볼록한 점일 때 앞 또는 뒤의 점의 y좌표가 mid 이하일 때만 mid직선과 만나므로, 그럴 경우에만 후보에 넣어주었다. 

이론상 자동적으로 정렬되어 후보에 들어가지만 계속 틀려서 sort해주었는데도 틀리고.. 아무튼 좀 이상했다.

그래서 지금 볼 점과 그 다음 점과의 관계만 생각해주게 넣어주니 ac가 떴다. 아직 이해가 잘 안 가지만 후자의 후보를 뽑는 방법이 후보의 중복이 훨 줄어드므로 그냥 넘어가야겠다.