AtCoder ABC 254 풀이

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

Tasks - AtCoder Beginner Contest 254

 

 

A.

숫자를 문자열로 받은 후 s[1]과 s[2]를 출력해주면 됩니다. 

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

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	string s; cin >> s;
	cout << s[1] << s[2];
}

 

 

 

B.

파스칼 삼각형을 출력해주면 됩니다. 점화식을 친절하게 줬네요. 

#include<bits/stdc++.h>
using namespace std;
int dp[33][33];

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int n; cin >> n;
	for (int i = 1; i <= n; i++) {
		dp[i][0] = 1;
		for (int j = 1; j < i; j++) {
			dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < i; j++) {
			cout << dp[i][j] << " ";
		}
		cout << "\n";
	}
}

 

 

 

C. 

재밌는 문제입니다. 인덱스가 K 차이나는 것끼리만 swap을 할 수 있습니다. 

관찰 1. 각 순번을 K로 나눈 나머지로 묶어두면 그 묶은것끼리만 정렬할 수 있습니다.

관찰 2. 모든 묶음을 정렬후 a를 정렬한 것과 비교하여 완전히 동일하면 됩니다. 

따라서 나머지로 인덱스를 분류한 후에 순회하면서 a의 정렬과 일치하는지 확인해주면 됩니다. 

#include<bits/stdc++.h>
using namespace std;
int a[200005];
vector<int>b[200005];

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int n, k;
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		b[i % k].push_back(a[i]);
	}
	sort(a, a + n);
	for (int i = 0; i < k; i++) {
		sort(b[i].rbegin(), b[i].rend());
	}
	bool ok = true;
	for (int i = 0; i < n; i++) {
		if (b[i % k].back() != a[i]) {
			ok = false;
			break;
		}
		else {
			b[i % k].pop_back();
		}
	}
	cout << (ok ? "Yes" : "No");
}

 

 

 

D. 

정수론적 관찰을 필요로 하는 문제입니다. 

관찰 1. X=n^2 * m 으로 나타낼 수 있습니다. (n은 X를 나누는 최댓값, m은 제곱수X)

관찰2. 두 정수 X, Y를 n^2*m , i^2*j로 나타냈을 때, XY가 제곱수가 되려면 m*j가 제곱수가 되어야 합니다.

여기서 m은 제곱수가 아니므로 m은 소인수 분해시 모든 소인수의 차수는 1입니다. 

(만약 짝수지수인 소인수가 있다면 n을 더 증가시킬 수 있으므로 모순)

따라서 m과 j는 유일하게 같을 때만 제곱수가 됩니다. m과 j는 소수들의 곱으로만 이루어져 있으므로.. 

 따라서 X/n^2 이 Y/i^2 과 같은 경우의 수를 세주면 됩니다. 

f(x)를 x를 나누는 최대제곱수라고 정의합니다. 그러면 x/f(x) = y/f(y)인 (x,y)를 찾아주면 됩니다. 

x<=N이므로 f(x)는 O(sqrt(N))에 구할 수 있습니다. 따라서 값이 x/f(x)인 것의 개수를 저장하면

값이 k로 같은 순서쌍을 O(1)에 찾을 수 있습니다.

따라서 어림잡아도 O(Nsqrt(N))을 넘지 않게 처리할 수 있습니다.

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

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int n; cin >> n;
	vector<int>sq;
	vector<int>f(n + 1);
	vector<ll>cnt(n + 1);
	for (int i = 1; 1LL*i * i <= n; i++) {
		sq.push_back(i * i);
	}
	for (int i = 1; i <= n; i++) {
		for (int s : sq) {
			if (i % s == 0) f[i] = s;
		}
		cnt[i / f[i]]++;
	}
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		ans += cnt[i] * cnt[i];
	}
	cout << ans << '\n';
}

 

 

 

E. 

최대차수가 3일 때, 정점 x로부터 거리가 k이하인 점들의 인덱스 합을 구하는 문제입니다. 

k도 3이하이므로, x로부터 조건을 만족하는 점들은 최대 9개입니다. 

BFS를 하면서 방문처리하고 합을 구해준 뒤, 다시 미방문 처리를 해주면 됩니다. 

전부 초기화하면 시간복잡도가 O(NM)이 되기 때문에 9개만 방문한 점을 저장해놓으면 됩니다. 

O(9N)에 해결할 수 있습니다. D랑 E 순서를 바꿔야 할 것 같습니다. 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m, q, a, b, x, k;
vector<int>g[150005];
int d[150005];

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	while (m--) {
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	cin >> q;
	memset(d, -1, sizeof(d));
	while (q--) {
		cin >> x >> k;
		queue<int>q;
		d[x] = 0;
		q.push(x);
		vector<int>init;
		init.push_back(x);
		int ans = x;
		while (q.size()) {
			int cur = q.front(); q.pop();
			for (int nxt : g[cur]) {
				if (~d[nxt])continue;
				d[nxt] = d[cur] + 1;
				init.push_back(nxt);
				if (d[nxt] <= k) {
					ans += nxt;
					q.push(nxt);
				}
			}
		}
		for (int& u : init) d[u] = -1;
		cout << ans << '\n';
	}
}

 

 

 

F. 

정수론적 관찰을 필요로 하는 문제입니다. 

우선 1열에 대해 쿼리를 구해봅시다. 

gcd(a1+b1, a1+b2, a1+b3, ... , a1+bn) 입니다. 유클리드 호제법에 의해, 

gcd(x,y)=gcd(abs(y-x), y) 이므로, 식을 정리하면, 

gcd(a1+b1, b2-b1, b3-b2, ... , bn-bn-1) 이 됩니다. 이 때, G = gcd(b2-b1, ... , bn-bn-1)은

gcd segment tree로 O(logN)에 구해줄 수 있습니다. 이렇게 1열에 대한 값은 gcd(a1+b1, G)입니다.

이제 여러 행을 처리해봅시다. 연속된 열에서 G는 변하지 않으므로 이제 구하는건, 

gcd(a1+b1, a2+b1, ..... , an+b1)입니다. 이 식 역시 유클리드 호제법에 의해,

gcd(a1+b1, a2-a1,  ...., an-an-1)이 되고 이 때, G' = gcd(a2-a1, ...., an-an-1)은 역시

O(logN)에 구해집니다.  따라서 답은 gcd(a1+b1, G, G') 이 됩니다. 

세그 초기화는 a[i]-a[i-1]과 b[i]-b[i-1]을 gcd 세그로 init 해놓으면 됩니다. 

이번 셋은 수학적인 부분이 좀 들어가서 재밌었던 것 같습니다 :)

#include<bits/stdc++.h>
using namespace std;
const int MAX = 200005;
int a[MAX], b[MAX];
int n, q, h1, h2, w1, w2;
int atree[4*MAX], btree[4*MAX];

struct segment_tree {
	void init(int tree[], int f, int node, int s, int e) {
		if (s == e) {
			tree[node] = !f ? a[s]-a[s-1] : b[s]-b[s-1];
			return;
		}
		int m = (s + e) >> 1;
		init(tree, f, 2 * node, s, m);
		init(tree, f, 2 * node + 1, m + 1, e);
		tree[node] = gcd(tree[2 * node], tree[2 * node + 1]);
	}
	int query(int tree[], int node, int s, int e, int qs, int qe) {
		if (s > qe || e < qs) return 0;
		if (qs <= s && e <= qe) return tree[node];
		int m = (s + e) >> 1;
		int g1 = query(tree, 2 * node, s, m, qs, qe);
		int g2 = query(tree, 2 * node + 1, m + 1, e, qs, qe);
		return gcd(g1, g2);
	}
}seg;


int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> q;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) cin >> b[i];
	seg.init(atree, 0, 1, 1, n); 
	seg.init(btree, 1, 1, 1, n); 
	while (q--) {
		cin >> h1 >> h2 >> w1 >> w2;
		int x = a[h1] + b[w1];
		int y = h1 < h2 ? seg.query(atree, 1, 1, n, h1 + 1, h2) : 0;
		int z = w1 < w2 ? seg.query(btree, 1, 1, n, w1 + 1, w2) : 0;
		cout << gcd(x, gcd(y, z)) << '\n';
	}
}