본문 바로가기

프로그래밍 대회 풀이/Codeforces

[Codeforces] Round #709 (div. 2) A ~ D 풀이

728x90
반응형

2021.03.21 22:20 ~ 00:35 본 라운드 참여 (performance = 1844)

 

 

테크노컵은 뭔가 항상 어려운 느낌이다...

생각보다 퍼포먼스가 나쁘지 않게는 나왔는데, 개인적으로 요즘 코포 폼이 조금 올라왔다고 생각해서 더 아쉬운 기분이 든다. 

 

 

A. Prison Break (*800)

 

모든 칸들에서 밖으로 나갈 수 있기 위해서 제거해야 하는 벽의 수의 최소를 구하는 문제이다.


답은 가로 * 세로, 즉 칸의 개수이고 대회중에는 직관적으로 빠르게 해결했다. 

 

정확한지는 모르겠으나 증명을 하자면, 각 칸마다 해당 칸에서 시작해서 밖으로 나갈 수 있는지 없는지를 상태로 표현하고, 벽이 제거된 이웃한 칸은 하나의 칸으로 합쳐진다고 생각하자.

벽을 하나 제거했을 때 밖으로 나갈 수 없었던 2개 이상의 칸이 한번에 상태가 바뀔 수 있는지를 생각해보면 이런 경우가 존재하지 않음을 알 수 있다. 

 

따라서 한 번의 벽 제거로는 칸의 개수를 최대 1개 줄이거나 최대 한 칸을 밖으로 더 내보낼 수 있다. 

그러므로 답은 칸의 개수가 된다. 

 

[소스 코드]

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

int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int T; cin >> T;
	while (T--) {
		int a, b; cin >> a >> b;
		cout << a*b << '\n';
	}
}

 

 

B. Restore Modulo (*1500)

 

n개의 원소로 이루어진 배열이 주어질 때, a[1] = s이고, i>1일 땐 a[i] = (a[i-1] + c)%m 을 만족하는 m, c, s가 존재하는지를 구하는 문제이다.

존재한다면 가능한 m중 가장 큰 경우를 구하고, m이 무한히 클 수 있다면 0을 출력한다.

기본적으로 c가 0이상이므로 원소가 감소하는 부분이 생긴다면 m에 영향을 받았다는 의미이다.


우선 m이 무한히 클 수 있는 경우는 어떤 경우일까? 

m이 배열에 영향을 주지 않는 경우이며, 이는 입력된 배열이 등차수열이라면 가능하다. 

 

1) 배열의 원소가 모두 동일

s = a[1], c = 0인 경우이고 따라서 m > s이기만 하면 된다. 

 

2) 배열이 단조증가하는 등차수열

m보다 커지는 경우가 없다는 의미이고, 결국 m > a[n]이기만 하면 된다. 

 

3) 배열이 단조감소하는 등차수열

예를 들어 a[1], a[1] - k, a[1] - 2k, .... , a[1] - (n-1)k 로 주어진다면, c = m - k만 만족하면 된다.

따라서 m이 무한히 커지더라도 만족하는 c값인 m-k가 존재하므로 가능하다. 

 

불가능한 경우는 어떤 경우일까?

일단 이전에 고려한 단조증가하거나 단조감소하는 경우를 제외하면 반드시 a[i] > a[i-1]인 부분이 하나는 존재한다. 

c < m이기 때문에 만약 증가했다면 이 부분은 c만큼 더해졌다는 의미이다. 

그러므로 반드시 c = a[i] - a[i-1]이 되어야 한다.

따라서 만약 a[i] - a[i-1] ≥ 0인 i중에서 a[i] - a[i-1]의 값이 다른 i가 존재한다면 이를 만족하는 c가 존재하지 않게 된다. 

이 경우는 불가능하다. 

 

이를 제외하면 이제 c는 고정이 되었고, 최대의 m을 찾아주어야 한다. 최대의 m은 a[i] > a[i+1]인 i중에서 a[i]가 가장 큰 부분을 골라서 적절하게 m을 만들어주면 된다. (a[i] + c) %m = a[i+1] 이므로 m = a[i] - a[i+1] + c를 만족한다. 

 

최종적으로, 선택된 m에 대해서 a[i] < a[i-1]인 부분에 대해서 조건을 만족하는지 체크해주면 된다. 

 

[소스 코드]

#include<bits/stdc++.h>

using namespace std;
int a[100010];
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int T; cin >> T;
	while (T--) {
		int n; cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
		}
		bool ismono = true;
		for (int i = 2; i < n; i++) {
			if (a[i] - a[i - 1] != a[i + 1] - a[i]) ismono = false;
		}
		if (n == 2 || ismono) {
			cout << 0 << '\n';
			continue;
		}
		bool chk = true;
		int c = -1;
		int m = -1;
		for (int i = 2; i <= n; i++) {
			if (a[i] >= a[i - 1]) {
				if (c == -1) c = a[i] - a[i - 1];
				else if(c != a[i] - a[i-1])	chk = false;
			}
		}
		for (int i = 2; i <= n; i++) {
			if (a[i] < a[i - 1]) {
				m = max(m, c - a[i] + a[i - 1]);
			}
		}
		if (a[1] >= m) chk = false;
		if (!chk) {
			cout << -1 << '\n';
			continue;
		}
		for (int i = 2; i <= n; i++) {
			if (a[i] != (a[i - 1] + c) % m) chk = false;
		}
		if (!chk) cout << -1 << '\n';
		else cout << m << ' ' << c << '\n';
	}
}

 

C. Basic Diplomacy (*1600)

 

간단하게 요약해서, 원소 m개의 배열을 1~n 범위의 숫자들로 채우는데 각 위치마다 가능한 숫자의 후보들이 주어지고, (m+1)/2번 넘게 사용되는 숫자가 존재하면 안된다. 


그리디로 해결할 수 있는데, 정확한 증명이 어려워 증명은 생략하겠다. 

* 호프크로프트(이분매칭) 알고리즘으로 오버킬이 가능하다고 한다. 대회중에 플로우도 생각했는데 div2 C인 것도 있고 시간복잡도를 잘못 생각한 부분도 있어서 무시했다. 

 

후보의 수가 적은 순서대로 숫자를 채워나가고, 숫자를 채울 때에는 아직 (m+1)/2개를 사용하지 않은 수 중 가장 후보로 많이 존재하는 숫자를 이용한다. 

 

[소스 코드]

#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
using namespace std;
using pii = pair<int, int>;
vector<int> team[100010]; //team[i] = i번째의 후보들
int cnt[100010]; //i를 사용할 수 있는 남은 횟수
int used[100010]; //used[i] = 숫자 i를 사용한 횟수
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	// freopen("input.txt", "r", stdin);
	int T; cin >> T;
	while (T--) {
		int n, m; cin >> n >> m;
		for (int i = 1; i <= n; i++) {
			cnt[i] = 0;
			used[i] = 0;
		}
		vector<pii> round;
		for (int i = 1; i <= m; i++) team[i].clear();
		for (int i = 1; i <= m; i++) {
			int k; cin >> k;
			for (int j = 1; j <= k; j++) {
				int a; cin >> a;
				team[i].push_back(a);
				cnt[a]++;
			}
			round.push_back({ k, i });
		}
		sort(all(round));
		bool chk = true;
		vector<int> ans(m + 1);
		for (auto[a, i] : round) { //i번째 라운드
			int mx = 0;
			int idx = -1;
			for (int a : team[i]) {
				if (cnt[a] > 0 && used[a] < (m + 1) / 2) {
					if (mx < cnt[a]) {
						mx = cnt[a];
						idx = a;
					}
				}
			}
			if (idx == -1) {
				chk = false;
				break;
			}
			ans[i] = idx;
			cnt[idx]--;
			used[idx]++;
		}
		if (!chk) cout << "NO\n";
		else {
			cout << "YES\n";
			for (int i = 1; i <= m; i++) cout << ans[i] << ' ';
			cout << '\n';
		}
	}
}

 

에디토리얼의 풀이가 훨씬 간단하다. 

임의로 숫자들을 배정하고나면 (m+1)/2보다 많이 배정된 숫자를 a라고 하면 a는 최대 1개밖에 존재하지 않다는 게 자명하다. 

따라서 a가 배정된 횟수가 (m+1)/2가 되도록, a가 배정된 위치들에서 다른 후보가 존재하면 다른 후보로 바꿔주면 된다. 

이게 불가능하다면 "NO"를 출력하면 된다. 

코드상에서는 임의로 숫자를 배정하는 것을 단순하게 첫번째 입력된 숫자로 배정하였다. 

 

[소스 코드]

#include<bits/stdc++.h>
#define sz(x) (int)x.size()

using namespace std;
vector<int> v[100001];
int cnt[100001];
int n, m, mxnum, k;
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int T; cin >> T;
	while (T--) {
		cin >> n >> m;
		int mx = 0;
		for (int i = 1; i <= n; i++) cnt[i] = 0;
		for (int i = 1; i <= m; i++) v[i].clear();
		for (int i = 1; i <= m; i++) {
			cin >> k;
			while (k--) {
				int a; cin >> a;
				v[i].push_back(a);
			}
			cnt[v[i][0]]++;
			if (mx < cnt[v[i][0]]) {
				mx = cnt[v[i][0]];
				mxnum = v[i][0];
			}
		}
		if (mx > (m + 1) / 2) {
			for (int i = 1; i <= m; i++) {
				if (mxnum == v[i][0]) {
					if (sz(v[i]) > 1) {
						swap(v[i][0], v[i][1]);
						mx--;
					}
					if (mx <= (m + 1) / 2) break;
				}
			}
		}
		if (mx > (m + 1) / 2) cout << "NO\n";
		else {
			cout << "YES\n";
			for (int i = 1; i <= m; i++) cout << v[i][0] << ' ';
			cout << '\n';
		}
	}
}

 

 

D. Playlist (*?)

 

n개의 원소로 이루어진 배열이 주어지고, 1->2->...->n->1->2... 와 같이 계속 배열을 탐색한다.

a[i]차례가 되었을 때, gcd(a[i], a[i+1]) = 1이면 a[i+1]을 지우고 a[i+2]부터 다시 탐색하기 시작한다.

이때, 지워진 자리는 비워두지 않고 뒤의 원소들을 한칸씩 앞으로 당긴다. 더이상 지울 수 있는 쌍이 없을 때 종료한다.

예를 들어 예시로 [5, 9, 2, 10, 15]가 주어진다면 다음과 같이 진행된다. 

[5, 9, 2, 10, 15] -> [5, 9, 2, 10, 15] -> [5, 2, 10, 15] -> [5, 2, 10, 15] -> [5, 2, 10, 15] -> [5, 2, 10, 15] -> [5, 2, 10, 15] -> [5, 10, 15] END

최종적으로, 지워지는 원소들을 구하는 것이 문제이다. 


먼저, 각 원소들은 최대 1번 지워지므로 지울 수 있는 쌍들을 차례대로 고려해도 시간적으로 문제가 되지 않는다. 

다만 원소가 지워짐으로 인해서 뒤의 원소들이 한칸씩 앞으로 당겨지는데 이를 naive하게 구현하면 한번 당길때마다 O(n)의 시간이 소모가 된다. 

따라서 현재 원소의 다음 원소를 더 빠르게 찾을 수 있어야 한다. 이를 set (alive)으로 관리한다. 

alive에 index 번호를 모두 넣어두고, 지워지는 원소들의 index들은 제거하면서 현재 원소의 다음 원소 index는 set.lower_bound 함수로 O(logn)만에 구할 수 있다. 

 

그다음 지워야 하는 쌍들을 또다른 set (die)에 저장해둔다. 

현재 A[a] 다음에 A[b]가 있다고 하고, gcd(A[a] , A[b]) = 1이라고 가정하다. 그러면 A[b]는 지워져야 한다. 

A[b]의 다음 원소를 A[c]라고 하고, gcd(A[b], A[c]) = 1이라면 die에는 {A[b], A[c]}가 포함되어있을 것이다.

하지만 A[b]가 지워짐에 따라서 A[b]에 의해서는 A[c]는 지워지지 않는다. 이를 die에서 제거해준다. 

 

A[b]를 제거하고 나면 A[a]의 다음 원소는 A[c]가 된다. 만약 gcd(A[a], A[c]) = 1이라면 지워야하는 쌍이 새로 추가되는 것이므로 die에 {A[a], A[c]} 를 넣어준다. 

 

최종적으로 die의 원소들이 모두 제거될 때까지 수행을 반복해주면 결과를 얻을 수 있다. 

 

[소스 코드]

#include<bits/stdc++.h>
#define sz(x) (int)x.size()

using namespace std;
using pii = pair<int, int>;

int a[100001];
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int T; cin >> T;
	while (T--) {
		int n; cin >> n;
		set<int> alive;
		set<pii> die;
		for (int i = 1; i <= n; i++) cin >> a[i], alive.insert(i);
		alive.insert(n + 1);
		for (int i = 1; i < n; i++) {
			if (gcd(a[i], a[i + 1]) == 1) die.insert({ i, i + 1 });
		}
		if (gcd(a[n], a[1]) == 1) die.insert({ n , 1 });
		vector<int> ans;
		while (!die.empty()) {
			set<pii> tmp;
			for (auto[i, j] : die) {
				if (alive.find(i) == alive.end() || alive.find(j) == alive.end()) continue;
				int k = *alive.lower_bound(j+1);
				if (k == n + 1) k = *alive.begin();
				
				//i -> j -> k & erase j
				alive.erase(j);
				ans.push_back(j);
				if (die.find({ j, k }) != die.end()) die.erase({ j, k });
				if (tmp.find({ j, k }) != tmp.end()) tmp.erase({ j, k });

				if (i != j && gcd(a[i], a[k]) == 1) tmp.insert({ i, k });
				if (die.empty()) break;
			}
			die = tmp;
		}
		cout << sz(ans) << ' ';
		for (int i : ans) cout << i << ' ';
		cout << '\n';
	}
}

 

PC로 보시는 것을 권장합니다. 

피드백은 언제나 환영입니다. 댓글로 달아주세요 ^-^

728x90
반응형