AtCoder Beginner Contest 131 풀이

https://atcoder.jp/contests/abc131

https://img.atcoder.jp/abc131/editorial.pdf

 

 

앳코더 비기너 컨테스트 131 문제들 풀이입니다.

 

오랜만에 PS 문제좀 풀어볼려고 앳코더에서 비교적 난이도가 쉬운 beginner contest 를 하나 골라서 업솔빙 해보았습니다.

 

원래 컨테스트일때는 참여 자체를 안하고, 남는 시간에 하나하나 풀어보았는데, D번까지는 쉽게 풀었고, E번부터는 힌트가 꽤 필요했습니다.

 

Editorial을 찾아보았는데, 일본어 버전만 제공되는 것 같아서 한국어로 풀이를 작성해보도록 하겠습니다.

 

https://atcoder.jp/contests/abc131/tasks/abc131_a

A - Security

A번 문제입니다. 인접한 녀석이 같은 값이 있는지 아닌지만 확인하면 되므로, 매우 간단한 문제입니다. 그냥 그대로 구현하면 됩니다.

 

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
int main() {
	string s;
	cin >> s;
	char p = s[0];
	for (size_t i = 1; i < s.length(); i++) {
		if (s[i] == p) {
			cout << "Bad";
			return 0;
		}
		p = s[i];
	}
	cout << "Good";
}

 

https://atcoder.jp/contests/abc131/tasks/abc131_b

B - Bite Eating

B번 문제입니다. 사과의 풍미(flavor) 값은 연속된 수열 값으로 나타납니다. 전체 값 중에서 사과 하나를 뺏을 때 차이가 가장 적을려면, 전체 값 중에 절대값이 가장 작은 것을 하나 빼버리면 됩니다.

O(N)으로 해결할 수 있습니다.

 

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
int main() {
	int N, L;
	cin >> N >> L;
	int S = (N - 1) * N / 2 + N * L;
	int dect = 987654321;
	for (int i = 0; i < N; i++) {
		int cand = i + L;
		if (abs(cand) < abs(dect)) {
			dect = cand;
		}
	}
	cout << (S - dect) << endl;
}

https://atcoder.jp/contests/abc131/tasks/abc131_c

C - Anti-Division

C번 문제입니다. 포함배제 Counting 문제입니다.

 

값 C로도 나누어 떨어지지 않고 D로도 나누어 떨어지지 않는 수의 개수는

(전체) - (C로 나누어 떨어지는 수) - (D로 나누어 떨어지는 수) + (C와 D 둘다 나누어 떨어지는 수)

가 됩니다.

 

C와 D 둘다 나누어 떨어지는 수는 C와 D의 LCM(최소공배수)으로 나누어 떨어지는 수와 같습니다.

C와 D의 최소 공배수는 C*D / gcd(C, D)와 같습니다.

gcd(C, D)는 C와 D의 최대공약수를 뜻합니다.

#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
template<class T>
T gcd(T a, T b)
{
	if (b == 0) return a;
	a %= b;
	return gcd(b, a);
}
int main() {
	ll A, B, C, D;
	cin >> A >> B >> C >> D;
	ll total = B - A + 1;
	ll Cdiv = B / C - ((A - 1) / C);
	ll Ddiv = B / D - ((A - 1) / D);
	ll LCM = C * D / gcd(C, D);
	ll CDdiv = B / LCM - ((A - 1) / LCM);
	ll ans = total - Cdiv - Ddiv + CDdiv;
	cout << ans << endl;
}

https://atcoder.jp/contests/abc131/tasks/abc131_d

D - Megalomania

D번 문제입니다. 모든 일을 다 끝낼 수 있는지 아닌지만 알아내면 됩니다.

단순한 그리디 문제입니다. 데드라인이 앞에 있는, 녀석들을 먼저 끝내는 식으로 진행을 하고, 그 중간에 데드라인을 넘어가는 녀석이 생기면 실패, 아니면 성공입니다.

 

이를 어떻게 알 수 잇냐면, 데드라인이 빠른녀석을 먼저 처리하지 않는 경우를 고려했을때,

데드라인이 빠른 녀석을 먼저 처리하는 경우로 변형이 가능하고, 변형을 했을 때 변형하기 전 보다 무조건 상태가 비슷하거나 나아진다는 것을 증명하면 됩니다.

 

데드라인이 빠른 순서대로 sorting이 되어 있는 상태라고 가정해 봅시다.

뭐 다음과 같이 있겠죠

 

$$b_{1},\space b_{2},\space b_{3},\space b_{4},\space b_{5},\space b_{6}\space ... \space b_{n-1},\space b_{n}$$

데드라인이 더 느린 녀석을 먼저 하나 처리를 했는데도 모두 처리를 가능한 상황이라고 가정해 보겠습니다.

$$b_{1},\space b_{2},\space b_{6},\space b_{4},\space b_{5},\space b_{3}\space ... \space b_{n-1},\space b_{n}$$

6번이랑 3번이 순서가 바뀌어서 처리 되어도 모두 처리가능한 상황이라는 것이죠.

 

여기서 다시 원래 순서, 1,2,3,... 순서로 바꾼다고 가정해봅시다. 3과 6번을 다시 순서를 바꾸는거죠

 

일단 바뀌는 두 당사자 뒤에 처리되는 녀석들은, 즉 6번 이후 녀석들은 처리되는 시기가 변화가 없으므로 상관이 없습니다. 처리되는 시기는 1번 부터 6번의 처리시간을 다 합친 이후에 처리가 될 것이므로 변화가 없습니다.

 

데드라인이 빠른 녀석(3)은 늦게 처리되어도 되던 상황에서 더 빨리 처리가 되었고,

그래서 그 녀석 때문에 문제가 될 일은 없습니다.

 

데드라인이 느린 녀석(6)은 더 뒤에 처리되게 되었는데, 자신보다 데드라인이 빠른 녀석도 처리가 되었던 위치이므로, 문제없이 처리가 되게 됩니다.

 

따라서 둘의 위치를 바꾸더라도 문제없이 처리가 가능합니다.

 

두번째 경우는 아래 순서로 처리할 경우 실패하는 경우입니다.

$$b_{1},\space b_{2},\space b_{6},\space b_{4},\space b_{5},\space b_{3}\space ... \space b_{n-1},\space b_{n}$$

위 순서대로 처리를 하면 실패를 합니다.

다시 그래서 3번과 6번을 바꾸어서 처리한다고 봅시다.

마찬가지로 6번 이후 녀석들은 처리 시기가 바뀌지 않아서 신경 쓸 필요가 없습니다. 3번 이전 녀석도 마찬가지죠.

3번이 앞으로 오게 되는데, 3번이 앞으로 오면서 여기서 만약 데드라인이 걸린다고 칩시다.

그런데 기존에는 6번이 3번째 자리에 있었는데, 6번의 데드라인이 3번 데드라인보다 길기 때문에 3번이 앞으로 와서 데드라인이 걸렸다면, 6번 자리에 있었을 경우에도 무조건 데드라인이 걸렸을 것입니다.

따라서 3번이 바뀐 자리때문에 걸렸다면 어차피 걸릴 상황이란거죠. 따라서 밑져야 본전인 상황입니다.

 

6번이 뒤로 가면서 걸렸다면 3번이 뒤에 있었을 때도 걸렸을 것입니다. 3번의 데드라인이 더 짧거든요. 이 경우에도 밑져야 본전입니다.

 

그리고 바꾸기 전에는 3번이 6번자리에서 데드라인에 걸리지만, 바꾸고 나서는 안걸리는 케이스가 있을 수 있습니다. 따라서 이 경우에는 기존에는 실패지만, 바꾸고 나서 성공이 되므로 좀 더 나은 경우이죠.

 

약간 증명이 중구난방이긴한데 어쨋든, 이런식으로 증명이 가능합니다.

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
 
int main() {
	int n;
	cin >> n;
	vector<pii> a(n); // deadline, duration
	for (int i = 0; i < n; i++) {
		cin >> a[i].second >> a[i].first;
	}
	sort(a.begin(), a.end());
	int elap = 0;
	for (int i = 0; i < n; i++) {
		elap += a[i].second;
		if (elap > a[i].first) {
			cout << "No";
			return 0;
		}
	}
	cout << "Yes";
	return 0;
}

 

 

 

https://atcoder.jp/contests/abc131/tasks/abc131_e

E - Friendships

E번 문제입니다. 문제 내용을 잘못 이해해서 좀 해맸었는데, 일단 N개의 vertex로 shortest path = 2인 pair를 최대한 많이 만드는 구성을 한번 생각해봤습니다.

 

N=7이라 한다면, 대충 위와 같이 생겼을 때 가장 많은 shortest path = 2인 쌍이 생깁니다. 1을 제외한 모든 조합들이 가능한거죠.

즉 //(\dbinom{6}{2}//)개 만큼 생깁니다. 

 

N에 대하여 일반화를 하면 //(\dbinom{N-1}{2}//)가지가 나오는 것이죠. 요렇게 나오는 경우가 최대 경우입니다.

 

따라서 //(K > \dbinom{N-1}{2} //)이면 불가능한 경우입니다.

 

그렇다면 저 최대값 이하의 값은 다 만들수가 있느냐? 

 

이에 대한 답은 Yes입니다. 위 그림에서 예를 들어 4와 5를 연결해버리면, 4에서 5로 가는 최단거리가 1이 되어서, 만족하는 쌍의 수가 하나 줄게 됩니다. 그리고 그 추가된 Edge는 다른 pair들에는 전혀 영향을 끼치지 않죠. 이런식으로 하나하나씩 줄여서 K값을 0으로 만들수도 있습니다.

 

따라서 N값에 따라서 0~최대값까지 죄다 만들 수 있는 것이죠. 이 범위 안에 들어있다면 저런 형태의 graph를 리턴하고, 그렇지 않다면 불가능하다라고 출력하면 됩니다.

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
int main() {
	int N, K;
	cin >> N >> K;
	int maxi = (N - 1)*(N - 2) / 2;
	if (K > maxi) {
		cout << -1;
		return 0;
	}
	int M = N - 1;
	int diff = maxi - K;
	cout << (M + diff) << endl;
	for (int i = 0; i < M; i++) {
		cout << 1 << ' ' << i + 2 << endl;
	}
	int src = 2;
	int dst = 3;
	for (int i = 0; i < diff; i++) {
		cout << src << ' ' << dst << endl;
		dst++;
		if (dst == N + 1) {
			src++;
			dst = src + 1;
		}
	}
}

 

https://atcoder.jp/contests/abc131/tasks/abc131_f

F - Must Be Rectangular!

F번입니다. 꽤나 어려웠는데요. 규칙을 찾아내면 생각보다는 간단합니다.

 

코드포스에서 풀이 올리신분들의 이야기를 보면 대충 다음과 같은 식으로 풀이합니다.

 

1. 점들을 graph로 모델링한다

2. 각각의 점은 vertex

3. 각각의 점과 같은 x좌표 혹은 y좌표에 있는 점 사이에 edge가 있다고 친다.

4. component들을 dfs혹은 bfs로 찾아낸다.

5. 각각 component에서 서로 다른 x좌표 개수와 y좌표 개수를 샌 뒤 그 둘을 곱한 개수를 모두 더한다.

6. 모두 더한 그 수가, 해당 operation을 최대한 사용해서 만들 수 있는 점들의 개수이다.

7. 여기서 원래 있던 점 수를 빼면 정답

 

요녀석이 왜 되는지 한번 생각을 해 보도록 합시다. 직접 종이에 그려보다 보면 대충 규칙성이 보입니다.

 

같은 x좌표, y좌표에 2개 이상의 점이 있으면, operation으로 한 점을 더 만들고, 그녀석으로 또 만들고 이러한 반복 작업을 통해서 바둑판식으로 점들을 모두 매워버릴 수 있습니다.

 

이런 성질을 관찰함으로써 위와 같은 풀이가 나오게 됩니다.

 

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
#define MAXN 100005
bool chkX[MAXN], chkY[MAXN], visit[MAXN];
vector<int> xline[MAXN], yline[MAXN];
int X[MAXN], Y[MAXN];
int main() {
	int N;
	cin >> N;
	ll ans = -N;
 
	for (int i = 0; i < N; i++) {
		int x, y;
		cin >> x >> y;
		X[i] = x;
		Y[i] = y;
		xline[x].push_back(i);
		yline[y].push_back(i);
	}
 
	for (int i = 0; i < N; i++) {
		if (visit[i]) continue;
		visit[i] = true;
		set<int> xdist, ydist;
		xdist.clear();
		ydist.clear();
 
		queue<int> q;
		q.push(i);
		while (q.size()) {
			int c = q.front(); q.pop();
			int x = X[c];
			int y = Y[c];
			xdist.insert(x);
			ydist.insert(y);
 
			if (chkX[x] == false) {
				chkX[x] = true;
				for (auto nx : xline[x]) {
					if (visit[nx] == false) {
						visit[nx] = true;
						q.push(nx);
					}
				}
			}
 
			if (chkY[y] == false) {
				chkY[y] = true;
				for (auto ny : yline[y]) {
					if (visit[ny] == false) {
						visit[ny] = true;
						q.push(ny);
					}
				}
			}
		}
 
		ans += (ll)xdist.size() * (ll)ydist.size();
	}
 
	cout << ans << endl;
	return 0;
 
}