AtCoder ABC 243 풀이

 

https://atcoder.jp/contests/abc243/tasks

Tasks - AtCoder Beginner Contest 243

 

 

 

A. 

샴푸가 가장 먼저 부족해지는 사람을 구하는 문제입니다. 우선 샴푸양은 1번주기에

A+B+C만큼 줄어드므로, 최대한의 주기를 거친 후 남은 값은 V%(A+B+C)입니다.

이 값이 A보다 작은 경우, A+B보다 작은 경우, 나머지 경우로 나눠주면 됩니다. 

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

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int v, a, b, c;
	cin >> v >> a >> b >> c;
	v %= (a + b + c);
	if (v < a) {
		cout << "F\n";
	}
	else if (v < a + b) {
		cout << "M\n";
	}
	else {
		cout << "T\n";
	}
}

 

 

 

B. 

2중문으로 a[i]=b[i], a[i]=b[j]인 쌍을 각각 세어주면 됩니다.

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

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int n; cin >> n;
	vector<int>a(n), b(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	for (int i = 0; i < n; i++) cin >> b[i];
	int ans1 = 0, ans2 = 0;
	for (int i = 0; i < n; i++) {
		ans1 += (a[i] == b[i]);
		for (int j = 0; j < n; j++) {
			if (j == i)continue;
			ans2 += (a[i] == b[j]);
		}
	}
	cout << ans1 << '\n';
	cout << ans2 << '\n';
}

 

 

 

C. 

y좌표를 기준으로 x좌표들을 저장해둡니다. 단, L과 R이 충돌하는 상황만 관심이 있습니다.

R중에 가장 작은 점과 L중에 가장 큰 점만 충돌하는지 확인해주면 충분합니다.

따라서 y좌표를 기준으로 x좌표의 최대, 최소만 저장해두고 각 y마다 확인해주면 됩니다.

y값이 1e9까지 가능한 반면 최대 2e5개까지 나오므로 map으로 좌표압축을 해주면 됩니다. 

#include<bits/stdc++.h>
using namespace std;
int val[200005][2];
map<int, int>ID;

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int n; cin >> n;
	vector<int>x(n), y(n);
	int idx = 0;
	for (int i = 0; i < n; i++) {
		cin >> x[i] >> y[i];
		if (!ID[y[i]]) ID[y[i]] = ++idx;
	}
	for (int i = 1; i <= idx; i++) {
		val[i][0] = 1e9 + 7;
		val[i][1] = -1;
	}
	string t; cin >> t;
	for (int i = 0; i < n; i++) {
		int idx = ID[y[i]];
		if (t[i] == 'R') {
			val[idx][0] = min(val[idx][0], x[i]);
		}
		else {
			val[idx][1] = max(val[idx][1], x[i]);
		}
	}
	for (int i = 1; i <= idx; i++) {
		if (val[i][0] < val[i][1]) {
			cout << "Yes\n";
			return 0;
		}
	}
	cout << "No\n";
}

 

 

 

D. 

navie하게 진행하면 long long 범위를 넘어가는 케이스가 가능합니다.

L이나 R을 10^6/2 번하고, U만 10^6/2 번 한다고하면, 내려가는 과정에서 오버플로우입니다.

따라서 자식으로 내려갔다가 부모로 올라오는 경우는 제때제때 지워주면 됩니다.

문자열을 순회하며 저장하는데, 만약 지금 보는 문자열이 U인데 저장한 마지막 문자가 L or R이면

벡터에서 제거해줍니다. 즉 stack을 구현하면 됩니다. 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, x;
string s; 

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> x >> s;
	vector<char>v;
	for (int i = 0; i < n; i++) {
		if (s[i] == 'U' && v.size() && v.back() != 'U') {
			v.pop_back();
		}
		else {
			v.push_back(s[i]);
		}
	}
	for (auto i : v) {
		if (i == 'U') x /= 2;
		else {
			x = 2 * x + (i == 'R');
		}
	}
	cout << x << '\n';
}

 

 

 

E.

N<=300이므로 O(N^3)까지 가능합니다. 선분을 지워도 연결그래프이면서 모든 쌍의 최단경로가 

유지되게 하고 싶습니다. 우선 모든 쌍의 최단경로는 플로이드-와샬로 O(N^3)에 찾아놨습니다.

이제 변을 지울텐데 지우는 변들은 이미 M번의 입력으로 주어졌습니다. 이제 이들을 지워나가는 과정은

단순합니다. dp[a][i]+d[i][b]가 c보다 작거나 같다면 대체 가능함을 알 수 있습니다. 

이걸 반복하면 총 O(N^3)에 해결할 수 있습니다.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, m, a, b, c, dp[303][303];
vector<tuple<ll, ll, ll>>v;

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	fill(&dp[1][1], &dp[301][301], 1e18);
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;
		v.push_back({ a, b, c });
		dp[a][b] = c;
		dp[b][a] = c;
	}
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
			}
		}
	}
	int ans = 0;
	for (auto [a, b, c]: v) {
		int temp = 0;
		for (int i = 1; i <= n; i++) {
			if (dp[a][i] + dp[i][b] <= c) {
				temp = 1;
			}
		}
		ans += temp;
	}
	cout << ans << '\n';
}