2022 충남대학교 SW-IT Contest - Division 1 풀이

 

https://www.acmicpc.net/category/detail/3193

2022 충남대학교 SW-IT Contest - Division 1

 

A.

햄버거를 1개 만들기 위해 빵 2개와 패티 1개가 필요합니다.

따라서 빵의 개수/2 와 패티 중 작은 값이 최대로 만드는 버거의 개수가 됩니다.

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

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int a, b; cin >> a >> b;
	cout << min(a / 2, b);
}

 

 

B.

마음대로 정렬할 수 있으므로 짝수, 홀수의 개수만 맞춰주면 됩니다.

짝수는 n/2개가 나오면 됩니다.  

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

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int n; cin >> n;
	int even = 0;
	for (int i = 1; i <= n; i++) {
		int x; cin >> x;
		if (!(x&1))even++;
	}
	cout << (even == n / 2 ? 1 : 0) << '\n';
}

 

 

C.

팰린드롬을 만들어주면 됩니다.

이미 같은건 패스하고 문자가 다른 쌍만 세주면 됩니다.

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

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

 

 

 

D.

크기순으로 배열했다고 가정합시다. 그럼 같은 값이 나오기 전까지 큰 것에 계속 넣을 수 있습니다.

x x x x+1 x+2 .... y 이런 꼴이라면 결국 x x x 이렇게 줄어들게 됩니다. 그리고 이 둘은 서로 넣을 수 없습니다.

따라서 그냥 x의 개수만큼 남습니다. 즉 값 x의 개수의 최댓값을 구해주면 됩니다.

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

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int n; cin >> n;
	multiset<int>s;
	for (int i = 0; i < n; i++) {
		int x; cin >> x;
		s.insert(x);
	}
	int ans = 0;
	for (int i : s) {
		ans = max(ans, (int)s.count(i));
	}
	cout << ans << '\n';
}

 

 

E.

우선 둘이 겹치는 소수가 없다고 합시다. A의 소수 개수를 cnt1, B의 소수 개수를 cnt2라 하면,

항상 A가 선공이므로 A>B여야 A가 승리합니다. 만약 겹치는 소수가 있다면 선공이 달라집니다.

겹치는 소수가 홀수개라면 겹치는걸 전부 지운 상태에선 선공이 B로 바뀝니다. 

따라서 그 경우에는 A<B여야  B가 승리합니다. 소수 판정은 값들이 작으므로 O(sqrt(N))에 판단해줘도 됩니다.

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

int prime(int x) {
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0) return 0;
	}
	return 1;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	int cnt1 = 0, cnt2 = 0, cnt3 = 0;
	for (int i = a; i <= b; i++) {
		if (prime(i))cnt1++;
	}
	for (int i = c; i <= d; i++) {
		if (prime(i))cnt2++;
	}
	for (int i = min(b, c); i <= max(b, c); i++) {
		if (prime(i)) cnt3++;
	}
	if (b < c || d < a || !(cnt3 % 2)) {
		cout << (cnt1 > cnt2 ? "yt" : "yj");
	}
	else {
		cout << (cnt2 > cnt1 ? "yj" : "yt");
	}
}

 

 

 

F.

풀이 예정

 

 

 

G.

[i....j]를 바꾼다고 합시다. 켜진(1)상태의 누적합을 s1, 꺼진(0)상태의 누적합을 s2라고 하면, 

결과값은 s1[i-1]+s1[j+1...N]+s2[i...j] = (s1[i-1]-s2[i-1])+(s2[j]-s2[j])+s1[N]이 됩니다.

Let T[i]=s2[i]-s1[i]로 놓으면, 구하는 값은 T[j]-T[i-1]+s1[N]의 최댓값입니다.

이는 스위핑으로 O(N)에 구할 수 있음은 well-known입니다. 

#include<bits/stdc++.h>
using namespace std;
int n, x, a[200002], dp[200002];

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	int sum = 0;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) {
		cin >> x;
		if (x & 1) sum += a[i];
		dp[i] = dp[i - 1] + (x & 1 ? -1 : 1) * a[i];
	}
	int ans = -1e9;
	int mn = 1e9;
	for (int i = 1; i <= n; i++) {
		mn = min(mn, dp[i - 1]);
		ans = max(ans, dp[i] - mn);
	}
	cout << ans + sum << '\n';
}

 

 

 

H.

제일 큰 값이 나머지 n-1개의 합+1이하라면 모두 이용할 수 있습니다.

그렇지 않다면, 제일 큰 값은 나머지 n-1개의 합 + 1까지만 이용할 수 있고 나머진 모두 이용가능합니다.

#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;
	ll maxi = -1, sum = 0;
	for (int i = 0; i < n; i++) {
		ll x; cin >> x;
		sum += x;
		maxi = max(maxi, x);
	}
	sum -= maxi;
	cout << min(maxi, sum + 1) + sum << '\n';
}

 

 

 

I.

다익스트라를 돌리면서 water 배열도 만들고 갱신해줍니다. 최단경로가 우선이니, 

dist[nx]>dist[x]+w라면 water은 무조건 갱신해줍니다.

만약 dist[nx]=dist[x]+w라면 water이 큰 경우에만 갱신해줍니다. 

우선순위큐를 minheap tuple로 써서 water 를 큐에 넣고 뺄 땐 음의 부호로 해줘야

max 값이 top으로 가게 됩니다. 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using tp = tuple<ll, ll, ll>;
ll n, m, u, v, S, T, w;
ll a[100010], dist[100010], water[100010];
vector<pll>g[100010];

void dijk(int S, int T) {
	priority_queue<tp, vector<tp>, greater<tp>>pq;
	fill(dist, dist + n + 1, 1e18);
	dist[S] = 0;
	pq.push({ 0, -a[S], S });
	while (pq.size()) {
		auto [d, wt, x] = pq.top(); pq.pop();
		if (dist[x] != d)continue;
		if (x == T) {
			cout << d << " " << -wt << '\n';
			return;
		}
		for (auto [nx,w] : g[x]) {
			if (dist[nx] > dist[x] + w) {
				dist[nx] = dist[x] + w;
				water[nx] = -wt + a[nx];
				pq.push({ dist[nx], -water[nx], nx });
			}
			else if (dist[nx] == dist[x] + w) {
				if (water[nx] < -wt + a[nx]) {
					water[nx] = -wt + a[nx];
					pq.push({ dist[nx], -water[nx], nx });
				}
			}
		}
	}
	cout << -1;
	return;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++)cin >> a[i];
	cin >> m;
	while (m--) {
		cin >> u >> v >> w;
		g[u].push_back({ v, w });
		g[v].push_back({ u, w });
	}
	cin >> S >> T;
	dijk(S, T);
}

 

 

J.

풀이 예정

 

 

K.

"경유"하는 경로의 개수를 구해야 합니다. 우선 dfs를 통해 i를 루트로 하는 서브트리의 빨간색과

파란색의 개수를 갱신해둡니다. O(N)에 해줄 수 있습니다. 

경로 생성의 케이스는 2가지입니다.

case 1. 하나는 u의 서브트리, 나머지 하나는 그 외에서 선택하는 경우

case 2. 서로 다른 u의 서브노드에서 빨, 파를 선택하는 경우

각 경우 구하는 방법은 아래 그림을 참고합시다. 모두 dfs를 해주면서 구할 수 있습니다. 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 100001;
vector<int>g[N];
int n, u, v, w, q, a[N];
ll r[N], b[N], s[N], dp[N];

void dfs1(int i, int p) {
	r[i] = (a[i] == 1);
	b[i] = (a[i] == 0);
	for (int j : g[i]) {
		if (j == p)continue;
		dfs1(j, i);
		r[i] += r[j];
		b[i] += b[j];
	}
}

void dfs2(int i, int p) {
	for (int j : g[i]) {
		if (j == p)continue;
		dfs2(j, i);
		dp[i] -= r[j] * b[j];
	}
	ll R = r[i] - (a[i] == 1);
	ll B = b[i] - (a[i] == 0);
	dp[i] += R * B;
	dp[i] += (r[1] - r[i]) * B;
	dp[i] += (b[1] - b[i]) * R;
}

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 = 1; i < n; i++) {
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs1(1, -1);
	dfs2(1, -1);
	cin >> q;
	while (q--) {
		cin >> w;
		cout <<  dp[w] << '\n';
	}
}

 

 

L.

누가 봐도 세그문제입니다. i<=j 순서가 없다면 그냥 최대, 최소만 관리하면 쉽게 풀립니다.

이 문제는 i<=j  순서를 부여했습니다. 이제 구간 최대 상승 값을 어떻게 log시간에 갱신할지가 문제입니다.

구간 연속 부분합의 log 갱신 등 이런 스타일의 문제는 이미지로 세그먼트 트리를 구성해보면 쉽습니다.

일단 최댓값과 최솟값을 관리해줍니다. 그리고 각 구간노드마다 구간 상승 최댓값을 가지고 있다고 합시다.

그럼 두개의 구간노드를 하나로 합칠 때, 구간 상승 최댓값은 세 가지 중 하나가 됩니다.

1. 왼쪽 노드의 구간 상승 최댓값

2. 오른쪽의 구간 상승 최댓값

3. 오른쪽의 최댓값 - 왼쪽의 최솟값 

따라서 이렇게 3개를 구조체로 관리하여 세그를 만들어주면 log시간에 쿼리를 처리할 수 있습니다.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAX = 100001;
const ll INF = 1e18;
int n, q, a[MAX];

struct Node {
	ll mn, mx, val;
};
Node tree[4 * MAX];

Node merge(Node x, Node y) {
	Node z;
	z.mn = min(x.mn, y.mn);
	z.mx = max(x.mx, y.mx);
	z.val = max({ x.val, y.val, y.mx - x.mn });
	return z;
}

struct segment_tree {
	void upd(int node, int s, int e, int idx, ll v) {
		if (idx<s || idx>e) return;
		if (s == e) {
			tree[node] = { v,v,0 };
			return;
		}
		int m = (s + e) >> 1;
		upd(2 * node, s, m, idx, v);
		upd(2 * node + 1, m + 1, e, idx, v);
		tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
	}
	Node query(int node, int s, int e, int qs, int qe) {
		if (s > qe || e < qs) return { INF, -INF, 0 };
		if (qs <= s && e <= qe) return tree[node];
		int m = (s + e) >> 1;
		Node L = query(2 * node, s, m, qs, qe);
		Node R = query(2 * node + 1, m + 1, e, qs, qe);
		return merge(L, R);
	}
}seg;

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		seg.upd(1, 1, n, i, a[i]);
	}
	cin >> q;
	while (q--) {
		int op; cin >> op;
		if (op == 1) {
			ll k, x;
			cin >> k >> x;
			seg.upd(1, 1, n, k, x);
		}
		else {
			int l, r;
			cin >> l >> r;
			cout << seg.query(1, 1, n, l, r).val << '\n';
		}
	}
}