AtCoder ABC 283 풀이

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

Tasks - UNIQUE VISION Programming Contest 2022 Winter(AtCoder Beginner Contest 283)

 

 

 

 

A.

\(a^b \) 를 출력해주면 됩니다. 최대 \(9^9 \) 이므로 \(int \) 자료형으로도 됩니다.

 

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

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int a, b;
	cin >> a >> b;
	int ret = 1;
	while (b--) {
		ret *= a;
	}
	cout << ret << '\n';
}

 

 

 

B.

그냥 배열 값을 변경해주면 됩니다. 

 

#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 + 1);
	for (int i = 1; i <= n; i++)cin >> a[i];
	int q; cin >> q;
	while (q--) {
		int op; cin >> op;
		if (op == 1) {
			int k, x;
			cin >> k >> x;
			a[k] = x;
		}
		else {
			int k; cin >> k;
			cout << a[k] << '\n';
		}
	}
}

 

 

 

 

C.

핵심은 0과 00을 사용할 수 있다는 점입니다. 그러므로 연속한 0이 나올 때, 

그리디하게 00을 최대한 써주면 됩니다. 0으로 이루어진 길이가 \(L\) 인 문자열을

0 2개와 1개를 이용해 지우는 최소 횟수는 \( \left \lceil \frac{L}{2}\right \rceil\) 번이 됩니다.

0이 아닌 값들은 무조건 1번씩 지워야 합니다. 두 값을 더해주면 됩니다.

주의할 점은 마지막에 0이 연속으로 나오는 경우가 있으므로 문자열을 전부 순회한 후에

다시 한 번  마지막으로 갱신된 \(L\) 에 대해 \(\left \lceil \frac{L}{2}\right \rceil\) 을 더해줘야 합니다.

 

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

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	string s; cin >> s;
	int z = 0;
	int ans = 0;
	for (auto i : s) {
		if (i != '0') {
			ans += (z + 1) / 2 + 1;
			z = 0;
		}
		else z++;
	}
	cout << ans + (z + 1) / 2 << '\n';
}

 

 

 

 

D. 

문제를 요약하면 상자에 알파벳을 순차적으로 넣는데 어느 경우라도 같은 알파벳이 또 들어가면

안됩니다. 또한 괄호로 둘러쌓인 문자열은 괄호가 끝나는 순간 상자에서 전부 빼낼 수 있습니다.

이걸 문자열이 끝날 때까지 진행할 수 있는지 여부를 묻는 문제입니다.  단순하게 해결할 수 있습니다. 

   1. ' ( ' 와 그 사이 문자열 \(s\) 와 ' ) ' 로 이루어진 쌍을 저장해 놓습니다.

   2.  문자열 \(s\)안에서 중복된 알파벳이 있으면 중단됩니다. 순회하며 방문 표기를 해줍니다.

   3. ' ) ' 가 나오면 저장해논 \(s\)를  순회하며 방문을 초기화해줍니다.

   4. 이제 그 이전 괄호 쌍이 남게 됩니다. 따라서 저장한 쌍의 인덱스를 감소시켜 줍니다. 

총 시간복잡도는 길이 \(|S| \)인 문자열에 대해  각 문자를 최대 2번 방문하게 되므로, 

\(O(|S|)\) 시간에 해결할 수 있습니다. 

 

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

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	string s; cin >> s;
	int n = s.size();
	vector<vector<char>> v(n);
	vector<bool> vis(30);
	int idx = 0;
	for (int i = 0; i < n; i++) {
		char x = s[i];
		if (x == '(') idx++;
		else if (x == ')') {
			for (char c : v[idx]) vis[c - 'a'] = 0;
			v[idx].clear();
			idx--;
		}
		else {
			if (vis[x - 'a']) {
				cout << "No\n";
				return 0;
			}
			v[idx].push_back(x);
			vis[x - 'a'] = 1;
		}
	}
	cout << "Yes\n";
	return 0;
}

 

 

 

 

E.

풀이 예정

 

 

 

 

 

 

F.

우리가 최소화하려는 식을  \(j\)에 따라 정리하면, 

 

$$D[i]=\begin{cases}\min(|P_i-P_j|+i-j ) & (j<i)\\
\min(|P_i-P_j|+j-i)& (j >i)\end{cases} $$

 

가 됩니다.  그러면 \(j<i\)인 경우는 세그먼트 트리로 뭔가 될 것 같습니다.

두 제약이 걸린 이런 문제에서 \(j<i\)란 조건은 작은 것부터 순회하면서 세그트리를 만들어주면

된다는 의미입니다.  \(P_i\)가 \(N\) 이하다... 겹치지 않는다.. 이런건 \(P_i\)를 인덱스로 하는 세그를

만들라는 감이 딱 옵니다. \(j<i\)인 경우 식을 더 정리하면, 

 

$$  D[i]=\begin{cases} (i+P_i)+\min(-P_j-j ) & (P_j<P_i)\\
 (i-P_i)+\min(P_j - j)& (P_j >P_i)\end{cases}  $$

 

가 됩니다. 그럼 윗 부분은 \([1, P_i ]\) 에서 세그트리의 최솟값을 구해주면 되고, 

아랫 부분은 \([P_i+1, N ]\) 에서 세그트리의 최솟값을 구해주면 됩니다. 

둘 중 작은 값이 \(j<i\)일 때, \(D[i]\) 가 됩니다. 

이제 \(j>i\) 인 경우는 뒤에서부터 순회해주면 됩니다. 귀찮으니 뒤집어줍시다. 

뒤집은 수열에서 구한 \(D'[i]\) 들에서 실제 인덱스 \(i\) 에 대응되는 값은 \(D'[n+1-i]\) 가 됩니다.

따라서 답은 \(\min(D[i] , D'[n+1-i])\) 가 됩니다. 

총 시간복잡도는 \(O(N\log_{}{N})\) 이 됩니다. 

 

#include<bits/stdc++.h>
using namespace std;
const int MAX = 200005;
int n, a[MAX], tree[4][4 * MAX], D[2][MAX];

void upd(int tree[], int node, int s, int e, int idx, int v) {
	if (idx<s || idx>e) return;
	if (s == e) {
		tree[node] = v;
		return;
	}
	int m = (s + e) / 2;
	upd(tree, 2 * node, s, m, idx, v);
	upd(tree, 2 * node + 1, m + 1, e, idx, v);
	tree[node] = min(tree[2 * node], tree[2 * node + 1]);
}

int min_query(int tree[], int node, int s, int e, int qs, int qe) {
	if (s > qe || e < qs) return 1e9;
	if (qs <= s && e <= qe) return tree[node];
	int m = (s + e) / 2;
	int l = min_query(tree, 2 * node, s, m, qs, qe);
	int r = min_query(tree, 2 * node + 1, m + 1, e, qs, qe);
	return min(l, r);
}

void solve(int flag, int tree1[], int tree2[], int a[]) {
	for (int i = 1; i <= n; i++) {
		int val1 = min_query(tree1, 1, 1, n, a[i], n) + (i - a[i]);
		int val2 = min_query(tree2, 1, 1, n, 1, a[i]) + (i + a[i]);
		D[flag][i] = min(val1, val2);
		upd(tree1, 1, 1, n, a[i], a[i] - i);
		upd(tree2, 1, 1, n, a[i], -a[i] - i);
	}
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++)cin >> a[i];

	for (int i = 0; i < 4; i++) {
		fill(tree[i], tree[i] + 4 * MAX, 1e9);
	}

	solve(0, tree[0], tree[1], a);
	reverse(a + 1, a + n + 1);
	solve(1, tree[2], tree[3], a);

	for (int i = 1; i <= n; i++) {
		if (i == 1) {
			cout << D[1][n] << " ";
		}
		else if (i == n) {
			cout << D[0][n] << " ";
		}
		else {
			cout << min(D[0][i], D[1][n + 1 - i]) << " ";
		}
	}
}