codeforces round 812 (div.2)

A. Traveling Salesman Problem

 

문제 :

$2$차원 평면에 $n$개의 점이 있고 각 점들은 $x$축 또는 $y$축에 있으면서 $-100\leq x_i, y_i \leq 100$의 값을 가진다. $(0,0)$에서 출발해서 상하좌우로 $1$만큼 움직여 모든 점을 방문한 뒤 다시 원점으로 돌아올 때 필요한 최소 움직임을 구하면 된다.

 

 

풀이 :

점들이 축 위에 있으므로 $max(x_i,0) - min(x_i,0)$값의 2배와 $max(y_i,0) - min(y_i,0)$값의 2배를 더해주면 된다.

 

 

코드 :

<hide/>
#include<bits/stdc++.h>
using namespace std;
 
void solve() {
	int n, x, y;
	int y1 = 0, y2 = 0;
	int x1 = 0, x2 = 0;
	for (cin >> n; n--;) {
		cin >> y >> x;
		if (y < y1) y1 = y;
		if (y > y2) y2 = y;
		if (x < x1) x1 = x;
		if (x > x2) x2 = x;
	}
	cout << (y2 - y1) * 2 + (x2 - x1) * 2 << '\n';
	return;
}
 
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t;
	for (cin >> t; t--;) {
		solve();
	}
	return 0;
}

 

---

 

B. Optimal Reduction

 

문제 :

길이가 $n$이면서 양의 정수로 된 수열 $a$가 있다. 임의의 $l, r (1\leq l \leq r \leq n)$을 선택해서 $a_l, a_{l+1}, ... , a_r$의 값을 1 감소시킬 수 있는 연산이 있다. $f(a)$는 수열의 모든 값을 0으로 만드는 연산의 최소 사용 횟수이다. $f(b)$는 $a$ 원소의 순서를 임의로 변경해서 수열의 모든 값을 0으로 만드는 연산의 최소 사용 횟수이다. $f(a)\leq f(b)$가 참인지 거짓인지를 알아보면 된다.

 

 

풀이 :

$f(a)\leq f(b)$가 되려면 $a$의 원소들이 계속 증가하다가 감소하는데 이 패턴이 한번만 있으면 된다.

첫 번째는 어떤 부분을 감소시켰을 때 두 부분으로 나눠져서 각 부분에 대해 연산을 해야 해서 최소가 될 수 없다.

두 번째는 어떤 부분을 감소시켜도 항상 감소시켜야 할 부분이 하나이기 때문에 최소가 될 수 있다.

 

 

코드 :

<hide/>
#include<bits/stdc++.h>
using namespace std;
 
void solve() {
	int n;
	cin >> n;
	vector<int> ar(n);
 
	int cnt = 0;
	for (int i = 0; i < n; i++) cin >> ar[i];
	
	for (int i = 1; i < n;) {
		cnt++;
		while (i < ar.size() && ar[i - 1] <= ar[i]) i++;
		while (i < ar.size() && ar[i - 1] >= ar[i]) i++;
	}
	if (cnt < 2) cout << "YES\n";
	else cout << "NO\n";	
}
 
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t;
	for (cin >> t; t--;) {
		solve();
	}
	return 0;
}

 

---

 

C. Build Permutation

 

문제 :

길이가 $n$인 수열 $a = [0, 1, 2, ... n-1]$가 있다. 그리고 $0$부터 $n-1$까지 각 한 번씩 등장하는 수열 $p$가 있다.$a_i + p_i$의 값이 어떤 수의 제곱수가 되면 된다. 만약 $p$를 만들 수 없으면 $-1$을 출력하면 된다.

 

---

 

D. Tournament Countdown

 

문제 :

$2^n$명이 토너먼트 방식으로 경기를 한다. 누가 우승자인지 $\lceil \frac{1}{3}\cdot 2^{n+1} \rceil$번의 질문 내에 구하면 된다.

 

---

 

E. Cross Swapping

 

---

 

F. Lost Array