2022 성균관대학교 프로그래밍 경진대회 open contest

풀이가없길래 내가 푼 것만 복습 겸 글을 써본다..
https://www.acmicpc.net/problem/24523

24523번: 내 뒤에 나와 다른 수

A번. 특정 수열이 있을 때 i번째 수 다음으로 A[i]와 다른 A[j] 중 j가 가장 작은 것을 고르는 문제입니다.
맨 뒤부터 다른 수 2개를 찾아 p1, p2에 인덱스를 저장하여 맨 앞까지 반복하면서 조건에 따라 p1과 p2를 업데이트 합니다.
먼저 p1과 p2를 찾기 위해 A[N]과 다른 수를 맨뒤 부터 찾아 가면서 해당 인덱스를 p1으로 두고 p2를 p1+1 로 둡니다.
그러고 p2-1 부터 진행하여 A[i]가 p2 번째 수와 다르다면 i번째의 답은 i+1 이 되고 p1을 p2로 , p2를 i로 설정해줍니다.
만약 A[i]가 p2 번째 수와 같다면 p2를 i번째로 옮기고 i번째의 답은 p1이 됩니다.
A[i]가 p1과 p2 번째의 수와 모두 다르다면 p1이 p2가 되고 p2가 i 가 됩니다. O(N)

#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <memory.h>

using namespace std;

int n;
int a[1000001];
int ans[1000001];
int main() {

	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	ans[n] = -1;
	memset(ans, -1, sizeof(ans));
	int p1 = -1, v1;
	int p2 = -1, v2;
	for (int i = n; i > 1; i--) {
		if (a[i] != a[i - 1]) {
			ans[i - 1] = i;
			p2 = i - 1;
			v2 = a[i - 1];
			p1 = i;
			v1 = a[i];
			break;
		}
	}
	
	for (int i = p2 - 1; i > 0; i--) {
		if (a[i] != v2 && a[i] != v1) {
			ans[i] = p2;
			p1 = p2;
			v1 = v2;
			p2 = i;
			v2 = a[i];
		}
		else if (a[i] != v2) {
			ans[i] = p2;
			p1 = p2;
			v1 = v2;
			p2 = i;
			v2 = a[i];
		}
		else {
			ans[i] = p1;
			p2 = i;
			v2 = a[i];
			
		}
	}

	for (int i = 1; i <= n; i++) {
		cout << ans[i] << " ";
	}
	return 0;
}

https://www.acmicpc.net/problem/24524

24524번: 아름다운 문자열

B번. 문자열 S와 중복된 알파벳이 없는 문자열 T가 주어질때 S에서 등장하는 순서를 유지하면서 부분 문자열을 뽑아서 T와 같은 부분문자열을 총 몇개나 만들 수 있는지 구하는 문제입니다. (한번 사용한 문자는 더이상 사용할 수 없습니다.)
S[i]가 T에 등장하는지 검사하여, 만약 S[i]가 T 문자열의 k 번째 알파벳이라면 T의 0~K-1 번째의 문자가 S[i] 이전에 몇번씩 등장했는지를 검사합니다. 등장한 횟수가 가장 작은 문자의 개수와 S[i] 문자의 개수 + 1 중 작은 값으로 S[i]의 개수를 정하면 됩니다. S[i]가 T 문자열의 마지막 문자인 경우, 모든 문자의 개수가 1 이상이라면 T에 속한 모든 문자의 개수를 1 빼주고 정답을 1 증가시키면 됩니다. O(NMM)

만약 문자열 S가 "abbacb" 고 문자열 T가 "abc" 라면 

i = 0 일 때, S[i] = a 이고, 문자열 T의 0번째에 등장하므로 cnt[a] = 1 
cnt[a] = 1, cnt[b] = 0, cnt[c] = 0 

i = 1 일 때, S[i] = b 이고, 문자열 T의 1번째 등장하므로 cnt[b] = min(cnt[a], cnt[b] +1 ) = min(1,1) = 1 
cnt[a] = 1, cnt[b] = 1, cnt[c] = 0 

i = 2 일 때, S[i] = b 이고, 문자열 T의 1번째 등장하므로 cnt[b] = min(cnt[a], cnt[b] +1 ) = min(1,2) = 1 
cnt[a] = 1, cnt[b] = 1, cnt[c] = 0 

처럼 반복하면 됩니다.

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

string a, b;
int m;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> a >> b;
	m = b.length();
	int answer = 0;
	int cnt[26] = { 0, };
	for (auto it : a) {
		int num = (int)(it - 'a');
		int min_cnt = cnt[b[0] - 'a'];
		for (int i = 0; i < m; i++) {
			int num2 = (int)(b[i] - 'a');
			if (it == b[i]) {
				if (i == 0) {
					cnt[num2] += 1;
				}
				else {
					cnt[num2] = min(cnt[num2] + 1,min_cnt);
				}
				if (i == m - 1) {
					for (int j = 0; j < m; j++) {
						int num3 = (int)(b[j] - 'a');
						cnt[num3] -= 1;
					}
					answer += 1;
				}
				break;
			}
			if (cnt[num2] == 0) {
				break;
			}
			else {
				min_cnt = min(min_cnt, cnt[num2]);
			}
		}
	}
	cout << answer;
}

https://www.acmicpc.net/problem/24526

24526번: 전화 돌리기

D번. 처음에 문제 이해가 잘 안돼서 전혀 이상한 정답을 제출했던 문제.
누군가 나에게 전화를 돌렸을 때, 그 전에 누군가 나에게 전화를 돌린 적 있다면 보스는 해당 전화를 돌린 모든 부원에게 (나 포함) 전화를 돌릴 수 없습니다.
dfs로 중복되어 전화를 받은 사람이 다시 전화를 받은 경우 true를 반환하게 하여 모든 결과를 or 연산으로 처리하고, 중복된 탐색을 방지하기 위해 메모이제이션을 사용하여 빠르게 처리할 수 있습니다.

#include <bits/stdc++.h>

using namespace std;

int n, m;
int visited[100001] = { 0, };
set<int> s[100001];
int dp[100001]; //각 노드의 capacity

int dfs(int node) {
	if (visited[node] == 1) { // 이전에 이미 방문함
		return 1;
	}
	int& ret = dp[node];
	if (~ret) return ret;

	visited[node] = 1; // 현재 노드 방문.
	ret = 0;
	for (auto it : s[node]) {
		ret |= dfs(it);
	}
	visited[node] = 0;
	return ret;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		s[a].insert(b);
	}
	memset(dp, -1, sizeof(dp));
	int answer = 0;
	for (int i = 1; i <= n; i++) {
		dfs(i);
	}
	for (int i = 1; i <= n; i++) {
		if (!dp[i]) {
			answer += 1;
		}
	}
	cout << answer;
}

https://www.acmicpc.net/problem/24527

24527번: 이상한 나라의 갈톤보드

E번. 갈톤 보드라는게 있는데 원래는 정규분포처럼 떨어지지만 이 문제에서는 균일하게 떨어진다고 합니다.
처음 높이 H가 주어지면 H(H+1)/2 만큼의 못이 존재하여 양옆으로 보낼 수 있습니다.
x번째 못이 몇 번째 높이(h)의 몇 번째 위치(t) 에 등장하는지 이분탐색으로 빠르게 구할 수 있으며, x번째 못에서 도착할 수 있는 도착 지점의 범위를 [t : t + H - h +1] 로 구할 수 있습니다. 이러고 구간 합에 대하여 segment tree lazy propagation을 사용하여 업데이트와 쿼리를 빠르게 처리 가능합니다. (더 간단하게 푸신 분들도 많지만 제 머리 한계는 여기까지..)

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

int H;
int Q, R;
ll psum[100002] = { 0, };

struct node {
	int s;
	int e;
	double lz;
	double sum;
	node* left;
	node* right;
};
node* mk(node* cur, int l, int r) {
	cur = new node();
	cur->s = l;
	cur->e = r;
	cur->lz = 0;
	cur->sum = 0;
	if (l == r) {
		return cur;
	}
	int mid = (l + r) / 2;
	cur->left = mk(cur->left, l, mid);
	cur->right = mk(cur->right, mid + 1, r);
	return cur;
}
node* lz(node* cur) {
	if (cur->lz) {
		if (cur->s != cur->e) {
			cur->left->lz += cur->lz;
			cur->right->lz += cur->lz;
		}
		cur->sum += ((double)cur->e - (double)cur->s + 1.0) * cur->lz;
		cur->lz = 0.0;
	}
	return cur;
}
node* up(node* cur, int l, int r, double cnt) { // l~r 구간에 cnt개 추가
	cur = lz(cur);
	if (cur->s == l && cur->e == r) {
		cur->lz += cnt;
		return cur;
	}
	int mid = (cur->s + cur->e) / 2; 
	cur->sum += (double)(r - l + 1) * cnt;
	if (mid >= r) {
		cur->left = up(cur->left, l, r, cnt);
	}
	else if (mid < l) {
		cur->right = up(cur->right, l, r, cnt);
	}
	else {
		cur->left = up(cur->left, l, mid, cnt);
		cur->right = up(cur->right, mid + 1, r, cnt);
	}
	return cur;
}

double query(node* cur, int l, int r) {
	cur = lz(cur);
	if (cur->s == l && cur->e == r) {
		return cur->sum;
	}
	int mid = (cur->s + cur->e) / 2;
	if (mid >= r) {
		return query(cur->left, l, r);
	}
	else if (mid < l) {
		return query(cur->right, l, r);
	}
	else {
		return query(cur->left, l, mid) + query(cur->right, mid + 1, r);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	node* r = nullptr;
	
	cin >> H >> Q >> R;
	psum[1] = 1;
	ll inc = 2;
	for (int i = 2; i <= H; i++) {
		psum[i] = psum[i - 1] + inc;
		inc += 1;
	}
	r = mk(r, 1, H + 1);
	for (;Q--;) {
		ll a, b; // a번에서 b 개 떨굼
		cin >> a >> b;

		int h = lower_bound(psum, psum + H + 1, a) - psum;
		int t = a - psum[h - 1];
		// 나는 h층에 t번째 있음
		double w = (double)(H - h + 2.0);
		double ave = (double)b / w;
		r = up(r, t, t + H - h + 1, ave);		
	}
	for (;R--;) {
		int a, b;
		cin >> a >> b;
		cout << query(r, a, b) << "\n";
	}
}

어렵네요.