AtCoder ABC 276 풀이

https://atcoder.jp/contests/abc276

AtCoder Beginner Contest 276 - AtCoder

D, F가 재밌었던 셋입니다. 

 

 

 

 

A.

알파벳 $a$가 등장하는 마지막 인덱스를 찾아주면 됩니다.

 

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

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	string s; cin >> s;
	int ans = -1;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == 'a') ans = i;
	}
	if (ans != -1) ans++;
	cout << ans << '\n';
}

 

 

 

B.

각 원소에 대한 인접리스트를 정렬하고 출력해주면 됩니다.

매번 정렬하면 $O(N^2\log N_{})$ 같지만, $\sum n_i=N$ 일 때, 

$O(\sum n_i\log {n_i}_{})=O(N\log N_{})$ 이므로 시간 안에 해결할 수 있습니다.

 

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

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int n, m;
	cin >> n >> m;
	vector<vector<int>>g(n + 1);
	while (m--) {
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	for (int i = 1; i <= n; i++) {
		sort(g[i].begin(), g[i].end());
		cout << g[i].size() << " ";
		for (auto j : g[i]) {
			cout << j << " ";
		}
		cout << "\n";
	}
}

 

 

 

C.

이전 순열을 출력하는 문제입니다. std::prev_permutation 이라는 자료구조를 써줍시다.

이거 없이 푸는건 좀 귀찮을 것 같습니다. 에디토리얼에 설명이 있으니 참조

 

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

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int n; cin >> n;
	vector<int>p(n);
	for (int i = 0; i < n; i++)cin >> p[i];
	std::prev_permutation(begin(p), end(p));
	for (int i = 0; i < n; i++) {
		cout << p[i] << " ";
	}
}

 

 

 

 

D. 

재밌는 문제입니다. 2의 배수거나 3의 배수면 마음대로 나눠도 될 때, 모든 수가 같아질 수 있는가?

가능하다면 최소 횟수를 묻고 있습니다. 우선 같아질 수 있는지 여부부터 판단해봅시다.

 

관찰 1. 모든 수가 2와 3의 구성으로 이루어지면 모든 수가 같아질 수 있습니다.

2의 최소지수 $p$와 3의 최소지수 $q$에 대해 $2^p{3}^q$가 될 때까지 모든 수를 적절히 나눠주면

같아질 수 있고 이게 최소 횟수이기도 합니다. 

 

관찰 2. 2와 3을 제외한 나머지 소인수전개는 모두 같아야 합니다.

이것역시 자명합니다. 2와 3을 제외한 소인수전개는 그대로 둘 수 밖에 없으므로 결국 2와 3을

적절히 모두 같아지게 한 후엔 나머지가 같아야만 모든 수가 같아지게 됩니다.

 

이제 모든 수를 2랑 3으로 전부 나눠서 각 수의 2의 지수와 3의 지수를 저장해둡니다. 

모든 수가 같아지려면 모두 나눈 결과가 같아야 합니다.

이제 최소횟수는 2의 지수 $(p_1,p_2,...,p_n)$ 와 3의 지수 $(q_1,q_2,...,q_n)$ 에 대해, 

$$\sum _{i=1}^n(p_i-p_{min})+\sum _{i=1}^n(q_i-q_{min})$$ 

가 됨을 알 수 있습니다.  시간복잡도는 $O(N\log {max(A)}_{})$ 가 됩니다. 

 

#include<bits/stdc++.h>
using namespace std;
int n, a[1001], two[1001], three[1001];

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		while (a[i] % 2 == 0) {
			a[i] /= 2;
			two[i]++;
		}
		while (a[i] % 3 == 0) {
			a[i] /= 3;
			three[i]++;
		}
	}
	for (int i = 2; i <= n; i++) {
		if (a[i] != a[1]) {
			cout << -1;
			return 0;
		}
	}
	int s1 = 0, s2 = 0;
	int mn1 = 100, mn2 = 100;
	for (int i = 1; i <= n; i++) {
		s1 += two[i];
		s2 += three[i];
		mn1 = min(mn1, two[i]);
		mn2 = min(mn2, three[i]);
	}
	s1 -= n * mn1;
	s2 -= n * mn2;
	cout << s1 + s2 << '\n';
}

 

 

 

E. 

시작점에서 출발하여 다시 되돌아올 수 있는지 묻는 문제입니다.  

$NM$가 ${10}^6$이하라는 조건으로부터 대충 $O(NM)$ 정도로 풀라는 것 같습니다.

우선 직선 경로 형태를 유니온 파인드로 합쳐주면서 진행합니다. 

인접한 두 점을 모두 돌면서 합쳐줘도 시간안에 연결해줄 수 있습니다. 

그럼 시작점 $S$로부터 한 칸 간 네 점에서 적어도 한 쌍은 조상이 같으면 경로가 존재합니다.

그렇지 않으면 경로가 존재하지 않습니다. 끝입니다. 

D랑 자리가 바뀐 것 같네요.  

 

#include<bits/stdc++.h>
using namespace std;
int h, w, par[1000001];

int idx(int i, int j) { return w * i + j; }

bool in(int i, int j) {
	return (i >= 0 && j >= 0 && i < h&& j < w);
}

int find(int x) {
	return !~par[x] ? x : par[x] = find(par[x]);
}

void uni(int x, int y) {
	x = find(x), y = find(y);
	if (x != y) par[y] = x;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> h >> w;
	int sx = 0, sy = 0;
	vector<vector<char>>a(h, vector<char>(w));
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cin >> a[i][j];
			if (a[i][j] == 'S') {
				sx = i;
				sy = j;
			}
		}
	}
	memset(par, -1, sizeof(par));
	for (int i = 0; i < h; i++) {
		for (int j = 0; j + 1 < w; j++) {
			if (a[i][j] == '.' && a[i][j + 1] == '.') {
				uni(idx(i, j), idx(i, j + 1));
			}
		}
	}
	for (int i = 0; i + 1 < h; i++) {
		for (int j = 0; j < w; j++) {
			if (a[i][j] == '.' && a[i + 1][j] == '.') {
				uni(idx(i, j), idx(i + 1, j));
			}
		}
	}
	vector<int>dir;
	if (in(sx + 1, sy) && a[sx + 1][sy] == '.') dir.push_back(idx(sx + 1, sy));
	if (in(sx - 1, sy) && a[sx - 1][sy] == '.') dir.push_back(idx(sx - 1, sy));
	if (in(sx, sy + 1) && a[sx][sy + 1] == '.') dir.push_back(idx(sx, sy + 1));
	if (in(sx, sy - 1) && a[sx][sy - 1] == '.') dir.push_back(idx(sx, sy - 1));

	for (int x : dir) for (int y : dir) {
		if (x != y && find(x) == find(y)) {
			cout << "Yes\n";
			return 0;
		}
	}
	cout << "No\n";
	return 0;
}

 

 

 

F.

좋은 문제입니다. 우선 $k=K$일 때 기댓값을 식으로 나타내면, 

$$E[K]=\frac{max{}_{x,y\in c_1,...,c_K}(x,y)}{K^2}$$ 

입니다. 모든 $K$에 대해 이 값을 구해야하니 한 값을 구하는데 $O(\log N_{})$ 이하가 걸려야 합니다. 

$f(K)=max{}_{x,y\in c_1,...,c_K}(x,y)$ 이 부분을 점화식으로 구성할 수 있을 것 같습니다. 

이 값을 계산하는데 미리 계산된 $f(K-1)$ 일 때 값을 알고 있다면, 

$$f(K-1)+c_K+2\sum _{x\in c_1,...,c_{K-1}}^{}max(x,c_K)$$

로 나타낼 수 있습니다.   $c_K$는 $x=y=c_K$인 상황이고,   $2\sum _{x\in c_1,...,c_{K-1}}^{}max(x,c_K)$ 는

하나는 $c_1,...,c_{K-1}$에 속하고  하나가 $c_K$인 $(x,y)$ 쌍의 경우들을 나타낸 것입니다.

그럼   $\sum _{x\in c_1,...,c_{K-1}}^{}max(x,c_K)$ 만 잘 구해주면 됩니다. 이 식을 다시 쓰면, 

$$\sum _{x<c_K}^{}{c}_K+\sum _{x\ge c_K}^{}x$$

가 됩니다. 그럼 왼쪽식은 $x<c_K$ 인 $x$의 개수를 세그먼트 트리로 찾아주면 되겠네요.

오른쪽 식은 $x\ge c_K$인 $x$들의 합을 역시 세그먼트 트리로 찾아줄 수 있습니다. 

개수를 세주는 트리와 합을 세주는 트리 2개를 만들어서 진행해주면 됩니다. 

값을 계산한 후엔 $c_K$ 를 인덱스로 하여 각각 1과 $c_K$를 업데이트해주면 됩니다.

주의할 점은 $c_1,...,c_N$이 모두 다르다는 조건이 없습니다. 

마지막 분수 계산은 mod 값이 소수라는 조건으로부터 페르마 소정리에 의해, 

$$a^{p-1}\equiv 1\to a^{-2}\equiv a^{p-3}$$

가 성립함을 이용해주면 됩니다. 

 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 998244353;
const ll MAX = 200005;
ll n, c[MAX];
ll cnt_tree[MAX], sum_tree[MAX];

struct fenwick_tree {
	void upd(ll tree[], int i, ll v) {
		while (i < MAX) {
			tree[i] = (tree[i] + v) % mod;
			i += i & -i;
		}
	}
	ll query(ll tree[], int i) {
		ll ret = 0;
		while (i) {
			ret = (ret + tree[i]) % mod;
			i -= i & -i;
		}
		return ret;
	}
	ll sum(ll tree[], int l, int r) {
		return query(tree, r) - query(tree, l - 1);
	}
}fw;

ll pow(ll a, ll b) {
	ll ret = 1;
	while (b) {
		if (b & 1) ret = ret * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ret;
}

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

	ll F = 0;
	for (ll i = 1; i <= n; i++) {
		ll S = fw.sum(sum_tree, c[i], MAX - 1);
		ll C = fw.sum(cnt_tree, 1, c[i] - 1);
		F += 2ll * (S + c[i] * C) + c[i];
		F %= mod;
		cout << pow(i, mod - 3) * F % mod << '\n';
		fw.upd(sum_tree, c[i], c[i]);
		fw.upd(cnt_tree, c[i], 1);
	}
}