Atcoder Beginner Contest 303

 

 

 

 

https://atcoder.jp/contests/abc303

NS Solutions Corporation Programming Contest 2023（AtCoder Beginner Contest 303） - AtCoder

 

 

A. Similar String

 

 

요약

 

 

주어지는 문자열에서 1은 'l'로, 0은 'o'로 대체되어 similar string이 될 수 있다고 한다.

두 문자열이 주어졌을 때, similar string인지 판단한다.

---

모든 1과 'l', 0, 'o'에 대하여 판별하여 보자.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

int N;
string S, T;

void solve() {
	cin >> N;
	cin >> S;
	cin >> T;
	for (int i = 0; i < N; i++) {
		if (S[i] == '1') {
			if (T[i] == '1' || T[i] == 'l') continue;
			else {
				cout << "No";
				return;
			}
		}
		else if (S[i] == 'l') {
			if (T[i] == '1' || T[i] == 'l') continue;
			else {
				cout << "No";
				return;
			}
		}
		else if (S[i] == '0') {
			if (T[i] == '0' || T[i] == 'o') continue;
			else {
				cout << "No";
				return;
			}
		}
		else if (S[i] == 'o') {
			if (T[i] == '0' || T[i] == 'o') continue;
			else {
				cout << "No";
				return;
			}
		}
		else {
			if (S[i] == T[i]) continue;
			else {
				cout << "No";
				return;
			}
		}
	}

	cout << "Yes";
	return;
}

int main(void) {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while (t--) solve();
	return 0;
}

 

 

 

B. Discord

 

 

요약

 

 

N명의 사람이 존재하고, M번의 사진촬영이 발생한다.

모든 사진촬영을 통틀어서 한 번도 인접하여 위치하지 않은 두 쌍의 사람은 'bad mood'가 된다고 한다.

서로 'bad mood'인 사람의 쌍을 구해보자.

---

N의 범위가 50 이하이므로, 50 * 50의 인접 행렬에 서로 인접한지 여부를 저장할 수 있다.

모든 사진 촬영에 대해 인접 여부를 저장하고, $O(N^{2})$에 counting을 수행한다.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

int N, M;
int arr[55][55];

void solve() {
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		vector <int> v;
		for (int j = 0; j < N; j++) {
			int a; cin >> a;
			v.push_back(a);
		}

		for (int j = 1; j < N; j++) {
			arr[v[j]][v[j - 1]] = 1;
			arr[v[j - 1]][v[j]] = 1;
		}
	}


	int cnt = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = i + 1; j <= N; j++) {
			if (arr[i][j] == 0) cnt++;
		}
	}

	cout << cnt;
	return;
}

int main(void) {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while (t--) solve();
	return 0;
}

 

 

 

C. Dash

 

 

요약

 

 

2차원 평면에서 N번의 움직임을 수행한다. 한 번의 움직임에서 상, 하, 좌, 우 중 한 곳으로 이동하게 되고, 이 과정에서 체력이 1 소모된다.

 

특정한 좌표에는 아이템이 존재하여 체력이 K 미만일 때, 강제로 사용되어 체력을 K로 맞추어 준다.
N번의 움직임을 저장한 문자열과 아이템의 위치가 주어질 때 움직임을 끝까지 마칠 수 있는지 확인하자.

---

단순히 그래프 탐색을 수행하여 중간에 체력이 음수가 되지 않고 끝까지 움직임을 수행할 수 있는지 시뮬레이션하자.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };

int N, M, H, K;
set <pii> item;
string S;

void solve() {
	cin >> N >> M >> H >> K;
	cin >> S;
	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		item.insert({ a,b });
	}

	pii pos = { 0,0 };

	for (int i = 0; i < S.length(); i++) {
		int move = 0;
		if (S[i] == 'R') move = 0;
		else if (S[i] == 'L') move = 1;
		else if (S[i] == 'U') move = 2;
		else move = 3;

		H--;
		if (H < 0) {
			cout << "No";
			return;
		}

		pos.first += dx[move];
		pos.second += dy[move];

		if (H < K) {
			if (item.count(pos)) {
				H = K;
				item.erase(pos);
			}
		}
	}

	cout << "Yes";
	return;
}

int main(void) {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while (t--) solve();
	return 0;
}

 

 

 

D. Shift vs. CapsLock

 

 

요약

 

 

소문자 'a'와 대문자 'A'로만 이루어진 문자열을 작성하려고 한다.

다음 세 가지 operation과 그에 상응하는 비용이 주어진다.

 

1. 키보드의 'a/A' 위치의 버튼을 누르기, X의 비용.

2. 쉬프트키와 키보드의 'a/A'버튼을 같이 누르기, Y의 비용.

3. Caps Lock 키 누르기, Z의 비용.

 

초기에 text는 비어있고, Caps Lock키는 눌려있지 않아 소문자 'a'가 나온다고 할때 주어진 문자열을 완성하는 최소의 비용을 찾아보자.

---

1. 문자열이 aaAAaaAa이고 현재 aa까지 문자열을 완성했다고 하자. aa를 어떤 비용에 완성했던지, 앞으로 구성해야 할 AAaaAa에는 영향을 미치지 않는다. 다만, 현재 Caps Lock 키가 눌려있는지 여부는 비용에 영향을 미칠 수 있다.

 

2. 여태껏 풀었던 부분문제가 앞으로 풀어야 할 부분문제에 영향을 미치지 않으므로 DP를 이용하여 문제를 해결할 수 있다.

 

3. DP state를 다음과 같이 정의한다.

table[len][mode] : 현재 len - 1 문자열까지 작성을 완료하였고, Caps Lock 키가 on(1)/off(1) 되어 있을 때, 앞으로 지불해야 하는 비용

 

4. base case는 table[S.length()][0] = table[S.length()][1] = 0이다.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;

ll X, Y, Z;
string S;
int arr[300005];
ll table[300005][2];

ll DP(int pos, int type);

void solve() {
	cin >> X >> Y >> Z;
	cin >> S;
	for (int i = 0; i < S.length(); i++) {
		if (S[i] == 'a') arr[i] = 0;
		else arr[i] = 1;
	}

	memset(table, -1, sizeof(table));
	cout << DP(0, 0);

	return;
}

int main(void) {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while (t--) solve();
	return 0;
}

ll DP(int pos, int type) {
	if (pos == S.length()) return 0;
	ll& ret = table[pos][type];
	if (ret != -1) return ret;
	ret = INF;
	
	if (arr[pos] == type) ret = min(ret, X + DP(pos + 1, type));
	if (arr[pos] != type) ret = min(ret, Y + DP(pos + 1, type));
	
	ret = min(ret, Z + DP(pos, type ^ 1));

	return ret;
}

 

 

 

E. A Gift From the Stars

 

 

요약

 

 

다음과 같은 그래프를 level-k ($k \geq  2$) star라고 하자.

Star의 중심이 되는 정점이 하나 있고, 그와 간선으로 연결된 K개의 정점이 있다. K개의 정점은 중심 정점 이외에 아무 정점과도 연결되어 있지 않다.

 

여러 개의 star이 존재한다고 할 때, star에서 degree가 1인 정점들을 골라 서로 연결하면 이는 트리 구조가 된다.

 

트리가 하나 주어졌을 때, 이를 여러 개의 star로 분해해보자.

---

1. level-k star은 K + 1개의 정점으로 이루어져 있다. (중심 1, K개의 꼭짓점)

 

2. 어느 한 star의 꼭짓점에서 탐색을 진행했을 때, 거리가 1인 정점은 항상 중심이고, 거리가 2인 정점은 항상 그 star의 다른 꼭짓점, 거리가 3 이상인 star은 다른 star의 꼭짓점에 해당하는 정점이다.

 

3. degree가 1인 임의의 정점에서 탐색을 시작하여, 거리가 1, 2인 정점은 같은 star로 묶어주고, 거리가 3인 정점부터는 다른 star로 인식하여 탐색을 계속하면 트리를 여러 개의 star로 분해할 수 있다.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

int N, cnt;
vector <int> tree[200005];
int degree[200005], mark[200005];
int ans[2000005];

void DFS(int node, int id, int depth);

void solve() {
	cin >> N;
	for (int i = 0; i < N - 1; i++) {
		int a, b;
		cin >> a >> b;
		tree[a].push_back(b);
		tree[b].push_back(a);
		degree[a]++;
		degree[b]++;
	}

	for (int i = 1; i <= N; i++) {
		if (mark[i] == 0 && degree[i] == 1) {
			cnt++;
			DFS(i, cnt, 0);
		}
	}

	vector <int> v;
	for (int i = 1; i <= cnt; i++) v.push_back(ans[i]);

	sort(v.begin(), v.end());

	for (int i = 0; i < v.size(); i++) cout << v[i] - 1 << " ";

	return;
}

int main(void) {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while (t--) solve();
	return 0;
}

void DFS(int node, int id, int depth) {
	if (mark[node]) return;
	ans[id]++;
	mark[node] = 1;

	for (int i = 0; i < tree[node].size(); i++) {
		int next = tree[node][i];
		if (mark[next]) continue;
		if (depth == 2) {
			cnt++;
			DFS(next, cnt, 0);
		}
		else DFS(next, id, depth + 1);
	}

	return;
}