codeforces round 810 (div.2)

A. Perfect Permutation

 

문제 :

$p_1, p_2, ... p_n$인 길이가 $n$인 수열이 있을 때 $i$가 $p_i$를 나누어 떨어지는 수가 최소가 되도록 수열을 정하면 된다. 수열에서는 1부터 $n$까지 한 번씩만 등장한다.

 

 

풀이 :

$n$이 홀수면 $1\ 3\ 2\ 5\ 4\ ... n\ (n-1)$이 되고

$n$이 짝수면 $2\ 1\ 4\ 3\ ... n\ (n-1)$이 된다.

 

 

코드 :

<hide/>
#include<bits/stdc++.h>
using namespace std;
 
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t;
	for (cin >> t; t--;) {
		int n;
		cin >> n;
		if (n % 2) {
			cout << 1 << ' ';
			for (int i = 2; i <= n; i++) {
				if (i % 2) cout << i - 1 << ' ';
				else cout << i + 1 << ' ';
			}
		}
		else {
			for (int i = 1; i <= n; i++) {
				if (i % 2) cout << i + 1 << ' ';
				else cout << i - 1 << ' ';
			}
		}
		cout << '\n';
	}
	return 0;
}

 

---

 

B. Party

 

문제 :

$n$명의 사람들이 파티에 갈 수 있는데 $i$번째 사람이 파티에 못 가면 $a_i$만큼의 행복도가 감소한다. $n$명의 사람들에 대한 $m$개의 친구관계가 있는데 이 관계의 수가 짝수가 되기 위해 감소하는 행복도의 값을 최소로 해야 한다.

 

 

풀이 :

사람들을 정점, 관계를 간선으로 하는 그래프로 생각한다. $\Rightarrow$ 그래프의 간선 수가 짝수가 되면 된다.

$m$이 짝수이면 정점을 제거할 필요가 없으므로 답은 0이 된다.

$m$이 홀수이면 몇 개의 정점을 제거하여 남은 간선의 수를 짝수로 만들면 된다.

 

(1) 제거하는 정점이 한 개 : 자신에게 연결된 간선의 수가 홀수이면서 최소인 $a_i$가 답의 후보가 된다.

(2) 제거하는 정점이 두 개 :  $m$개의 쌍에 대하여 연결된 간선의 수가 홀수이면서 두 정점에 해당하는 $a_i$의 값의 합이 최소일 때 답의 후보가 된다.

 

첫 번째는 정점을 하나만 제거하는 것이 가장 좋지만 $a_i$값이 달라지면 두 개의 정점을 제거해야 할 수도 있다.

 

 

코드 :

<hide/>
#include<bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t;
	for (cin >> t; t--;) {
		int n, m;
		cin >> n >> m;
		vector<int> adjcnt(n + 1, 0), cost(n + 1);
		vector<pair<int, int>> ar(m);
		for (int i = 1; i <= n; i++) cin >> cost[i];
		for (int i = 0; i < m; i++) {
			cin >> ar[i].first >> ar[i].second;
			adjcnt[ar[i].first]++;
			adjcnt[ar[i].second]++;
		}
		if (m % 2 == 0) cout << "0\n";
		else {
			int ans = 1e9;
			for (int i = 1; i <= n; i++) {
				if (adjcnt[i] % 2 && cost[i] < ans) ans = cost[i];
			}
			for (int i = 0; i < m; i++) {
				if ((adjcnt[ar[i].first] + adjcnt[ar[i].second] - 1) % 2
					&& cost[ar[i].first] + cost[ar[i].second] < ans)
					ans = cost[ar[i].first] + cost[ar[i].second];
			}
			cout << ans << '\n';
		}
	}
	return 0;
}

 

---

 

C. Color the Picture

 

문제 :

$n\times m$크기의 판과 $k$종류의 색이 있고 각각 $a_1,a_2,...,a_k$만큼 사용할 수 있다. 각 칸을 $k$개의 색 중 하나로 칠 할 수 있는데 이때 자신이 칠해진 색과 인접한 칸이 3개 이상 있어야 한다. 이 조건에 맞게 모든 칸을 색칠할 수 있는지 알아보면 된다.

 

인접하다는 것은

$x_1 - x_2 \equiv \pm1 (\bmod n)$ and $y_1=y_2$ 이거나

$y_1 - y_2 \equiv \pm1 (\bmod m)$ and $x_1=x_2$ 이다.

 

 

풀이 :

색칠된 칸에서 인접한 칸이 최소 3개가 되어야 하는데 

첫 번째 그림의 경우 1~4는 인접한 칸이 2개밖에 없으므로 반드시 두 번째 그림처럼 한 줄이 모두 같은 색으로 되어야 한다. 또 같은 색으로 채워진 줄이 2줄 이상 있어야만 인접한 칸이 3개 이상 될 수 있다. 만약 한 줄밖에 없다면 한 줄이 모두 같은 색이라 해도 인접한 칸이 모두 2개밖에 없다.

 

하지만 모두 2줄로 칠할 수 없는 경우도 있기 때문에 3줄 이상 칠 할 수 있는 색의 종류가 있는지 확인해야 한다.

 

 

코드 :

<hide/>
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
 
bool isp(){
	int n, m, k;
	cin >> n >> m >> k;
	vector<int> ar(k);
	for (int i = 0; i < k; i++) cin >> ar[i];
 
	ll sum = 0, stat = 0;
	for (int i = 0; i < k; i++) {
		if (ar[i] / n >= 2) {
			sum += ar[i] / n;
			if (ar[i] / n > 2) stat++;
		}
	}
	if (sum >= m) {
		if (m % 2 == 0 || stat) return true;
	}
 
	sum = 0, stat = 0;
	for (int i = 0; i < k; i++) {
		if (ar[i] / m >= 2) {
			sum += ar[i] / m;
			if (ar[i] / m > 2) stat++;
		}
	}
	if (sum >= n) {
		if (n % 2 == 0 || stat) return true;
	}
	return false;
}
 
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t;
	for (cin >> t; t--;) {
		if (isp()) cout << "Yes\n";
		else cout << "No\n";
	}
	return 0;
}

 

---

 

D. Rain

 

문제 : 정수로 된 직선에 $n$번 비가 오는데 $i$번째 날 $x_i$의 위치에 $p_i$만큼의 비가 온다. $a_j$가 $n$번에 걸쳐 누적된 비의 양이라 하면 $a_j = \sum_1^nmax(0,p_i-\left| x_i-j \right|)$이다. 한 곳에서라도 누적된 비의 양이 $m$을 초과하면 홍수가 나는데 각 $i$번째 날들에 대해 비를 안 오게 할 때(즉 $p_i=0$일 때) 홍수가 안 난다면 1을 출력하고 비가 안 와도 홍수가 난다면 0을 출력하면 된다.

 

 

풀이 :

 

---

 

E. XOR Triangle

 

문제 :

 

 

풀이 :