codeforces round 811 (div.3)

A. Everyone Loves to Sleep

 

문제 :

현재의 시각과 특정 시간에 울리는 $n$개의 알람이 있을 때 가장 처음으로 울리는 알람까지의 시간이 얼마나 되는지 구하면 된다. 

 

 

풀이 :

$n$개의 시각 중 현재 시각보다 작으면 하루(24시간)를 더해준다. 그리고 시간을 분 단위로 바꿔서 가장 차이가 적게 나는 값을 다시 시  분 형태로 바꿔주면 된다.

 

 

코드 :

cpp

열기 줄바꿈

#include<bits/stdc++.h>
using namespace std;
 
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t;
	for (cin >> t; t--;) {
		int n, h, m, ans = 1e9;
		cin >> n >> h >> m;
		int t = h * 60 + m;
		for (int i = 0; i < n; i++) {
			cin >> h >> m;
			int t1 = h * 60 + m;
			if (t > t1) t1 += 1440;
			if (t1 - t < ans) ans = t1 - t;
		}
		cout << ans / 60 << ' ' << ans % 60 << '\n';
	}
	return 0;
}

 

---

 

B. Remove Prefix

 

문제 :

길이가 $n$인 수열과 수열의 가장 첫 번째 원소를 지우는 연산이 있을 때 수열의 모든 원소가 최대 한 번씩만 등장하기 위해 사용해야 하는 연산의 최소 횟수를 구하면 된다.

 

 

풀이 :

$1\leq a_i\leq2\times10^5$이므로 원소가 중복되는지 검사하는 배열을 만든다. 배열은 값은 처음에 모두 0으로 하고 수열의 처음부터 끝까지 보며 각 원소의 위치를 저장한다. 이때 저장돼있던 배열의 값이 0이 아니면 원소가 중복된다는 뜻이므로 저장된 위치가 답이 될 수 있는지 확인한 후 현재의 위치 값으로 바꿔준다.

 

 

코드 :

cpp

열기 줄바꿈

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

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t;
	for (cin >> t; t--;) {
		int n, x, ans = 0;
		cin >> n;
		vector<int> inx(n + 1, 0);
		for (int i = 1; i <= n; i++) {
			cin >> x;
			if (inx[x] != 0 && inx[x] > ans) ans = inx[x];
			inx[x] = i;
		}
		cout << ans << '\n';
	}
	return 0;
}

 

---

 

C. Minimum Varied Number

 

문제 :

한자리 수들을 중복되지 않게 최소로 사용하여 합이 $s$가 되면 된다.

 

 

풀이 :

$9$부터 $1$까지 $1$씩 감소시키면서 $s$보다 작으면 $s$에서 빼준다. 빼준 숫자들을 오름차순으로 출력하면 된다.

 

 

코드 :

cpp

열기 줄바꿈

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

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t;
	for (cin >> t; t--;) {
		int x, i;
		cin >> x;
		for (i = 9;; i--) {
			if (x - i <= 0) {
				cout << x;
				break;
			}
			x -= i;
		}
		for (i++; i <= 9; i++) cout << i;
		cout << '\n';
	}
	return 0;

 

---

 

D. Color with Occurrences

 

문제 :

문자열 $t$와 $n$개의 문자열이 있을 때 $n$개의 문자열들을 최소로 사용하여 $t$를 만들 때 그 횟수를 구하면 된다.

문자열의 각 값들이 겹쳐도 된다. 예를 들어 $s_1 = ba, s_2=aba$라 했을 때 $s_1$과 $s_2$를 합쳐 $baaba$도 되지만 $baba$도 만들 수 있다.

 

 

풀이 :

$t$의 길이가 최대 $100$, $s_i$($n$개 문자열 중 $i$번째 문자열)의 길이가 최대 $10$이라 완전 탐색으로 해도 시간 안에 답이 구해진다. $t$에서 각 위치의 문자들이 한번 이상은 있어야 하기 때문에 앞에서부터 순서대로 문자를 채워간다. $t$에서 가장 마지막으로 완성된 문자의 위치를 $i-1$이라 하면 $i$번째 문자를 포함하면서 아직 포함되지 않은 문자를 가장 많이 채울 수 있는 $s_i$를 다음으로 사용하고 이를 $t$의 모든 문자가 채워질 때까지 반복하면 된다. 만약 어떤 $s_i$로도 채울 수 없다면 $-1$이 된다.

 

코드 :

cpp

열기 줄바꿈

#include<bits/stdc++.h>
using namespace std;
 
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t;
	for (cin >> t; t--;) {
		string str;
		cin >> str;
		int n;
		cin >> n;
		vector<string> ar(n);
		for (int i = 0; i < n; i++) cin >> ar[i];
 
		vector<pair<int, int>> ans;
		int inx = 0, i;
		for (i = inx; inx < str.size();) {
			int next = 0, pos1, pos2;
			for (int j = 0; j < n; j++) {
				for (int k = 0; k < ar[j].size(); k++) {
					if (inx - k < 0) break;
					if (inx - k + ar[j].size() > str.size()) continue;
					if (str.substr(inx - k, ar[j].size()) == ar[j]) {
						if (inx - k + ar[j].size() > next) {
							next = inx - k + ar[j].size();
							pos1 = j + 1;
							pos2 = inx - k + 1;
						}
						break;
					}
				}
			}
			if (next == 0) break;
			ans.push_back({ pos1,pos2 });
			inx = next;
		}
		if (inx >= str.size()) {
			cout << ans.size() << '\n';
			for (auto it : ans) cout << it.first << ' ' << it.second << '\n';
			ans.clear();
		}
		else cout << "-1\n";
	}
	return 0;
}

 

---

 

E. Add Modulo 10

 

문제 :

$n$개의 정수 수열 $a_1, a_2, ..., a_n$이 있고 어떤 원소의 $10$으로 나눈 나머지를 자신에게 더할 수 있는 연산이 있다. 예를 들어 $12$는 $2$를 더하여 $14$가 될 수 있고 또 $14$에서 $4$를 더하여 $18$이 될 수 있다. 이때 이런 수열과 연산을 통하여 모든 원소가 같은 값을 가지게 할 수 있는지 구하면 된다.

 

 

풀이 :

어떤 수가 홀수라면 짝수로 만들기 위해 $10$으로 나눈 나머지를 한번 더해준다.

(1) 어떤 수가 $5$로 나누어 떨어질 때 : $10n(0\leq n$인 정수$)$형태로 만들어 준 뒤 $10$으로 나눴을 때 나오는 몫의  종류가 $1$이하면 된다.

(2) 어떤 수가 $5$로 나누어 떨어지지 않을 때 : $2\rightarrow 4\rightarrow 8\rightarrow 6\rightarrow 2\rightarrow ...$로 반복되는데 반복될 때마다 $20$이 증가하므로 $20$으로 나눈 나머지가 같은지 보면 된다. 먼저 일의 자리를 $2$로 만들어준 뒤 $20$으로 나눈 값의 종류가 $1$이하면 된다.

 

 

코드 :

cpp

열기 줄바꿈

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

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t;
	for (cin >> t; t--;) {
		int n, x, cnt = 0;
		int temp = 0, stat5[3] = {};//0,10,10u
		int prev = 0, pcnt = 0;
		bool stat[3] = {};//0,2,12
		cin >> n;
		while (n--) {
			cin >> x;
			if (x % 5 == 0) while (x % 10) x += x % 10;
			while (x % 5 != 0 && x % 10 != 2) x += x % 10;
			if (x % 5 == 0) {
				stat[0] = true;
				if (x == 0) stat5[0] = true;
				else if (x == 10) stat5[1] = true;
				else {
					if (prev != x) pcnt++;
					prev = x;
					stat5[2] = true;
				}
			}
			else if (x % 20 == 2) stat[1] = true;
			else stat[2] = true;
		}
		if ((int)stat5[0] + stat5[1] + stat5[2] > 1 || pcnt > 1 || (int)stat[0] + stat[1] + stat[2] > 1) cout << "No\n";
		else cout << "Yes\n";
	}
	return 0;
}

 

---

 

F. Build a Tree and That Is It

 

문제 :

 

 

풀이 :

 

---

 

G. Path Prefixes

 

문제 :

$1$을 루트로 하면서 $n$개의 정점으로 구성된 트리가 있고 각 간선에는 $a_i, b_i$의 양수 가중치가 있다.

$1$부터 임의의 $u (2\leq u\leq n)$까지 가는 경로의 $\sum a_i$를 $A$라 하고,

$1$부터 $v (1$부터 $u$까지 경로 중 임의의 원소$)$까지 가는 경로의  $\sum b_i$를 $B$라 할 때

$A\geq B$를 만족하게 하는 $v$가 $1$부터 몇 개의 간선을 거쳐오는지를 구하면 된다. ($1$을 제외한 모든 원소에 대하여)

 

 

풀이 :

$1$부터 $u$까지 가는 간선의 가중치가 모두 양수이므로 이동할수록 계속 누적되는 값은 계속 증가한다. 각 정점들에 대해 1부터 자신까지의 $A(=\sum a_i)$를 구해놓고 $1$부터 트리를 dfs로 탐색하는데 각 간선의 값이 누적될 때마다 그 값을 벡터에 저장해놓는다. 그러면 어떤 정점에서 $v$를 구할 때 저장된 벡터의 값들 중 자신의 $A$값보다 작은 값들 중 제일 큰 값의 위치가 답이 된다. 이를 이분 탐색으로 빠르게 구할 수 있다.

 

 

코드 :

cpp

열기 줄바꿈

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
 
struct node {
	int p, a, b;
};
const int N = 2e5 + 2;
vector<vector<node>> adj(N);
vector<ll> ans(N), A(N), st = { 0 };
 
void getA(int inx, ll sum) {
	for (int i = 0; i < adj[inx].size(); i++) {
		getA(adj[inx][i].p, sum + adj[inx][i].a);
	}
	A[inx] = sum;
	return;
}
 
void getAns(int inx) {
	int left = 0, right = st.size() - 1;
	while (left <= right) {
		int mid = (left + right) / 2;
		if (A[inx] < st[mid]) right = mid - 1;
		else left = mid + 1;
	}
	ans[inx] = left - 1;
	for (int i = 0; i < adj[inx].size(); i++) {
		st.push_back(st.back() + adj[inx][i].b);
		getAns(adj[inx][i].p);
		st.pop_back();
	}
	return;
}
 
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	
	int t;
	for (cin >> t; t--;) {
		int n;
		cin >> n;
		for (int i = 1; i <= n; i++) {
			adj[i].clear();
			ans[i] = 0;
		}
		int p, a, b;
		for (int i = 2; i <= n; i++) {
			cin >> p >> a >> b;
			adj[p].push_back({ i,a,b });
		}
		getA(1, 0);
		getAns(1);
		for (int i = 2; i <= n; i++) cout << ans[i] << ' ';
		cout << '\n';
	}
	return 0;
}