에듀-102

그냥 오랜만에 심심해서 쓴다.

확실히 예전보다 실력이 는거 같다.

1700점대 실력은 나오는거 같다.

 

이번 라운드는 진짜 실수가 너무 많았다...

복귀해보도록 하자.

 

달달하다!

A번

 

수열에서 어떤 원소 하나를 수열 내부의 적당한 원소 2개의 합으로 바꿀수 있다.

이때 입력으로 주어진 값 이하로 모든 수열을 바꿀 수 있는지를 묻고 있다.

당연히, 제일 작은 2개의 합으로 바꾸는것이 이득이므로 그리디하게 먹는다.

그런데 이제, 수열내의 최댓값이 주어진 값 이하이면 항상 성립한다.

#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<string>
#include<cstring>
#include<stack>
#include<queue>
#include<set>
#include<map>
 
using namespace std;
using ll = long long;
const ll n_ = 300300, inf = 1e18;
 
ll n, m, a, b, c, d, t, x, y;
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> t;
	while (t--) {
		cin >> n >> d;
		vector<ll>v;
		bool ok = true;
		for (int i = 0; i < n; i++) {
			cin >> a;
			v.push_back(a);
		}
		sort(v.begin(), v.end());
		if (v[0] + v[1] <= d || v[n-1]<=d)cout << "YES";
		else cout << "NO";
		cout << '\n';
	}
 
}

B번

문자열 끼리의 곱셈으 정의하자. 문자열 * n 을 했다는 것은 문자열을 n번 이어서 쓴 것이다.

이때 두 문자열의 최소공배수를 구하여라, 만약 없다면 -1을 출력하여라.

 

문자열의 길이가 최대 20이므로, 완전탐색 돌리자.

풀이자체는 문제를 보자마자 떠올랐고, 구현도 바로 했는데

문제는 이제 구현과정에서 실수가 있어서 1번 틀렸다 ㅠ

#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<string>
#include<cstring>
#include<stack>
#include<queue>
#include<set>
#include<map>

using namespace std;
using ll = long long;
const ll n_ = 300300, inf = 1e18;

ll n, m, a, b, c, d, t, x, y;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> t;
	while (t--) {
		string A, B, C, D, ans = "-1";
		cin >> A >> B;
		a = inf;
		for (int i = 0; i < 30; i++) {
			C = A;
			for (int j = 0; j < i - 1; j++)
				C += A;
			D = B;
			for (int k = 0; k < 30; k++) {
				if (D == C) {
					if (a > D.size()) {
						ans = D;
						a = D.size();
						break;
					}
				}
				D += B;
			}
		}
		cout << ans << '\n';
	}

}

 

C번

문제가 난해하다. 난해하다는 표현은 어렵다는 표현과는 다르다. 그냥 지문 자체가 너무 읽기 어려웠다.

문제를 푸는데보다 이해하는데 오랜 시간이 걸린거 같다.

codeforces.com/contest/1473/problem/C

Problem - C - Codeforces

 

#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<string>
#include<cstring>
#include<stack>
#include<queue>
#include<set>
#include<map>
 
using namespace std;
using ll = long long;
const ll n_ = 300300, inf = 1e18;
 
ll n, m, a, b, c, d, t, x, y, base = 1;
ll tree[n_ * 4][2], psum[n_], k;
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> t;
	while (t--) {
		cin >> n >> k;
		a = k;
		c = k;
		k = n - k;
		b = n- 2*k -1;
		for (int i = 0; i < b; i++) {
			cout << i + 1 << ' ';
		}
		for (int i = 0; i < c-b; i++) {
			cout << a-- << ' ';
		}
		cout << '\n';
	}
 
}

와우!

 

D번

n번의 연산이 주어진다. + 혹은 -에 따라 0으로 초기화 되어 있는 x의 값에 +1이 되거나 -1이 된다. 

이때 각 쿼리마다 x y가 주어지는데, x부터 y까지의 연산은 무시하고 x의 값의 나올수 있는 서로 다른 개수를 구하라는 것이다.

 

우선적으로 생각해 볼 것은, 연산 자체의 변화량이 1 뿐이다. 따라서 나올 수 있는 서로 다른 x의 개수란 결국,

최댓값 -최솟값 +1 로 볼수 있다.

그럼이제 주어진 쿼리마다 x부터 y까지의 연산을 무시하고 나서 어떻게 빠르게 구하냐가 문제인데,

누적합을 이용하면 

0~ x-1까지는 주어진 누적합에서 최대 최소를 가져오면 되고

x ~ y까지 쿼리의 누적합은 pre[y]-pre[x-1]로 알 수 있다.

그리고 y+1~ n-1까지의 누적합에서 최대 최소는 x~y쿼리의 누적합을 빼준것으로 가져온다.

 

두 부분에서 가져온 최대 최소중에서, 최대 최소값이 쿼리마다 최대 최소가 될 수 있음을 알 수있다.

이때 구간별 최대최소를 구하는 연산을 해야하는데, 대가리가 깨진 나는 세그트리를 박았다.

 

0~ x-1 그리고 y+1~n-1범위에서만 구해야 하는데, 이제 0과 n-1은 고정이니까

끝에서부터 최대 최소를 저장하는 배열을 만들어서 해결하면 o(1)에 되고,

아니면 나처럼 세그 박으면 된다. ㅜ

#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<string>
#include<cstring>
#include<stack>
#include<queue>
#include<set>
#include<map>

using namespace std;
using ll = long long;
const ll n_ = 300300, inf = 1e18;

ll n, m, a, b, c, d, t, x, y, base = 1;
ll tree[n_ * 4][2], psum[n_];
ll f1(ll l, ll r) {
	l += base, r += base;
	ll ret = inf;
	while (l <= r) {
		if (l % 2)ret = min(ret, tree[l++][0]);
		if (!(r % 2))ret = min(ret, tree[r--][0]);
		l /= 2, r /= 2;
	}
	return ret;
}

ll f2(ll l, ll r) {
	l += base, r += base;
	ll ret = -inf;
	while (l <= r) {
		if (l % 2)ret = max(ret, tree[l++][1]);
		if (!(r % 2))ret = max(ret, tree[r--][1]);
		l /= 2, r /= 2;
	}
	return ret;
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> t;
	while (t--) {
		cin >> n >> m;
		string s;
		cin >> s;
		for (base = 1; base < n; base *= 2);
		for (int i = 1; i <= n; i++) {
			if (s[i - 1] == '+')c = 1;
			else c = -1;
			psum[i] = psum[i - 1] + c;
		}
		for (int i = 0; i < base; i++) {
			tree[base + i][0] = inf;
			tree[base + i][1] = -inf;
		}
		for (int i = 0; i < base; i++) {
			for (int j = 0; j < 2; j++) {
				tree[base + i][j] = psum[i + 1];
			}
		}
		for (int i = base - 1; i; i--) {
			tree[i][0] = min(tree[i * 2][0], tree[i * 2 + 1][0]);
			tree[i][1] = max(tree[i * 2][1], tree[i * 2 + 1][1]);
		}
		
		while (m--) {
			cin >> x >> y;
			c = psum[y] - psum[x - 1];
			a = 0, b = 0;
			a = min(a, f1(0, x - 2)), b = max(b, f2(0, x - 2));
			a = min(a, f1(y, n - 1) - c), b = max(b, f2(y, n - 1) - c);
			cout << b - a + 1 << '\n';
		}
	}

}