Educational Codeforces Round 130 (Rated for Div. 2) 1673 → 1699

https://codeforces.com/contest/1688

https://codeforces.com/contest/1688

!!!! 모든 답은 제 풀이일 뿐 공부를 위한 올바른 정해가 아닐 수 있습니다 !!!!

 

A. Parkway Walk

https://codeforces.com/contest/1697/problem/A

Problem - A - Codeforces

문제

 

n 과 m이 주어진다. n+1개의 벤치가 있고 각 벤치사이의 거리는 a[i] 미터이다. 1미터를 움직이려면 1 에너지가 필요하고 최초에 m 에너지를 가지고 있다. 각 벤치마다 휴식을 해서 원하는 만큼 에너지를 충전할 수 있다. n+1번째 벤치로 가기 위한 최소 충전 에너지를 출력하는 문제

 

풀이

 

n+1벤치까지 가는 거리가 m보다 많다면 그 차이를 출력해주고 아니라면 0을 출력해주면 된다.

 

코드

 

    #include <bits/stdc++.h>
    using namespace std;
    int a[101];
    int main() {
    	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    	int T;
    	cin >> T;
    	while (T--) {
    		int n, m;
    		cin >> n >> m;
    		int sum = 0;
    		for (int i = 1; i <= n; i++) {
    			cin >> a[i];
    			sum += a[i];
    		}
    		if (sum <= m) {
    			cout << 0 << '\n';
    			continue;
    		}
    		cout << sum - m << '\n';
    	}
    }

 

B. Promo

https://codeforces.com/contest/1697/problem/B

Problem - B - Codeforces

문제

 

가게에서 n개의 아이템을 팔고 있고 각 물건은 p[i]의 가격을 가지고 있다. 물건을 최소 x개 산다면 산 물품들 중에서 가장 싼 y개를 무료로 지급해준다. q개의 x,y 쿼리가 주어졌을 때 각 쿼리마다 최대로 얻을 수 있는 y개의 가격 합을 출력하는 문제

 

풀이

 

내림차순으로 정렬하여 누적합을 구해주고 인덱스를 계산하여 출력해주면 된다.

 

코드

 

    #include <bits/stdc++.h>
    using namespace std;
    long long a[200001];
    long long pre[200001];
    int main() {
    	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    	int n, q;
    	cin >> n >> q;
    	for (int i = 1; i <= n; i++)cin >> a[i];
    	sort(a + 1, a + 1 + n, greater<long long>());
    	for (int i = 1; i <= n; i++) {
    		pre[i] = pre[i - 1] + a[i];
    	}
    	while (q--) {
    		int x, y;
    		cin >> x >> y;
    		cout << pre[x] - pre[x - y] << '\n';
    	}
     
    }

C. awoo's Favorite Problem

https://codeforces.com/contest/1697/problem/C#

Problem - C - Codeforces

문제

 

n길이의 string s와 t가 주어진다. 한번에 move에 "ab"를 "ba"로 또는 "bc"를 "cb"로 바꿀 수 있다. 원하는만큼 동작했을 때 s를 t로 바꿀 수 있다면 YES 아니라면 NO를 출력하는 문제

 

풀이

i = 1 ~ n까지 하나씩 스왑하면서 맞춰간다 우선 i번째 원소가 다른데 s[i] > t[i] 라면 절대 바꿀 수없다.

그리고 t[i] 는 반드시 s[i]+1의 문자열이여야 하고 , 따로 인덱스 r을 두어 s[i+1]..부터 가장 가까운 t[i]를 찾는다. s[i]와 s[r]을 스왑해주고 만약 그사이에 s[i] 문자가 아니라면 답이될 수 없다. 이런 방식으로 r을 저장하여 계속 swap해주면서 맞는지 확인해주면 된다.

 

코드

    #include <bits/stdc++.h>
    using namespace std;
    string a, b;
    int main() {
    	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    	int T;
    	cin >> T;
    	while (T--) {
    		int n;
    		cin >> n >> a >> b;
    		if (n == 1) {
    			if (a[0] == b[0])cout << "YES\n";
    			else cout << "NO\n";
    			continue;
    		}
    		int r = 0;
    		bool flag = true;
    		for (int i = 0; i < n; i++) {
    			if (a[i] == b[i])continue;
    			if (a[i] > b[i]) {
    				flag = false;
    				break;
    			}
    			if (i == (n - 1)) {
    				flag = false;
    				break;
    			}
    			if (a[i] == 'a') {
    				if (b[i] == 'c') {
    					flag = false;
    					break;
    				}
    			}
    			r = max(i + 1, r);
    			while (r < n) {
    				if (a[r] != a[i])break;
    				r++;
    			}
    			if (r >= n) {
    				flag = false;
    				break;
    			}
    			if ((a[i] + 1) != a[r]) {
    				flag = false;
    				break;
    			}
    			swap(a[i], a[r]);
    		}
    		if (flag)cout << "YES\n";
    		else cout << "NO\n";
    	}
    }

자세한 설명에 중점을 두기보다는 대회 기록에 중점을 둔 글입니다 !

틀린 부분은 감사히 지적받겠습니다.