Educational Codeforces Round 102 (Rated for Div. 2)
문제 링크
Dashboard - Educational Codeforces Round 102 (Rated for Div. 2) - Codeforces
codeforces.com
A. Replacing Elements
문제
양의 정수로 이루어진 수열 a가 주어질 때, 다음과 같은 작업을 할 수 있다.
- 서로 다른 인덱스 i, j, k를 고른 후, ai = aj + ak 로 바꿀 수 있다.
이 작업을 무한정 할 수 있다고 할 때, 수열 a의 모든 수를 d보다 작거나 같게 만들 수 있는가?
풀이 1
이 문제의 경우 두 가지 case일 때, 문제 조건을 만족시킬 수 있습니다.
1. 모든 수가 d보다 작거나 같을 때, 작업을 하지 않고 그대로 정답이 됩니다.
2. 수열 a에 포함된 어떤 두 수의 합이 d보다 작거나 같을 때. 이때 이 두 수를 이용해 다른 원소들도 모두 d보다 작거나 같게 만들 수 있습니다.
따라서 우선 수열 a를 오름차순으로 정렬한 후, 맨 마지막 수가 d보다 작거나 같으면 바로 yes를 출력,
그렇지 않다면 맨 앞 두 수의 합이 d보다 작거나 같으면 yes, 그렇지 않다면 no를 출력하면 됩니다.
소스 코드 1
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t; cin >> t;
while (t--)
{
int n, d;
cin >> n >> d;
vector<int>v(n);
for (int i = 0; i < n; i++) cin >> v[i];
sort(v.begin(), v.end());
if (v[v.size() - 1] <= d) cout << "YES\n";
else {
if (v[0] + v[1] <= d) cout << "YES\n";
else cout << "NO\n";
}
}
}
B. String LCM
문제
문자열 a와 정수 x의 곱을 다음과 같이 정의하자.
예를 들어 a가 "abc", x가 2라면, a * x = "abcabc", "a" * 5 = "aaaaa"
그리고, 두 문자열 s, t의 최소공배수 LCM(s, t) = k 는 s * x = k, t * x = k 를 만족하여야 한다.
LCM(s, t)를 구하거나, 없다면 -1을 출력하라.
풀이 1
최소공배수란 두 수의 공배수 중 최소값이며, 모든 공배수의 약수가 되는 수입니다.
따라서 두 문자열 s, t 길이의 최소공배수를 구한 후, 그 길이만큼 문자열 s, t를 늘여준 후
둘을 비교했을 때 같지 않다면, 다음 공배수때도 같지 않을 것이기 때문에 -1을 출력하고
같다면 그대로 길어진 문자열을 출력하면 됩니다.
*참고 - 최소공배수 구하는 법
1. 우선 두 수의 최대공약수를 구한다. (유클리드 호제법으로, 생략)
2. 두 수의 곱에 1번에서 구한 최대공약수를 나누어주면 된다.
소스 코드 1
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int gcd(int a, int b) {
while (b != 0) {
int r = a % b;
a = b;
b = r;
}
return a;
}
int lcm(int a, int b) {
return a * b / gcd(a, b);
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t; cin >> t;
while (t--)
{
string s, t;
cin >> s >> t;
int lc = lcm(s.size(), t.size());
int s_cnt = lc / s.size();
int t_cnt = lc / t.size();
string tmp = "";
for (int i = 0; i < s_cnt; i++) tmp += s;
s = tmp;
tmp = "";
for (int i = 0; i < t_cnt; i++) tmp += t;
t = tmp;
if (s == t) {
cout << s << "\n";
}
else cout << "-1\n";
}
}
C. No More Inversions
문제
n개의 원소를 갖는 수열 a는 다음과 같은 모양을 갖습니다.
1, 2, 3, ..., k-1, k, k-1, k-2, ..., k - (n - k)
또한 "inversion"은 다음과 같은 상황을 말합니다.
인덱스 i, j가 i < j 이고, a[i] > a[j] 일 때
k개의 원소로 이루어진 수열 p가 있고, n개의 원소로 이루어진 수열 b는 다음을 만족하며 이루어집니다.
-> b[i] = p[a[i]]
수열 b의 "inversion"이 수열 a의 "inversion"을 넘지 않는 상황에서 수열 b의 사전 순이 최대가 되도록 하는 수열 p를 출력하시오.
풀이 1
개인적으로 상당히 어려웠던 문제였습니다.
결론부터 말하면 그리디 문제이고, 1... k로 구성된 수열 p에서 뒤에서 n-k 개를 거꾸로 뒤집으면 되는 문제입니다.
이러한 문제의 경우, 직접 만들어보는 것도 정말 큰 힌트가 될 수 있습니다.
직접 permutation을 돌려서 정답이 되는 수열 p, b를 만들어 볼게요.
다음과 같은 코드로 말이죠.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n, k;
cin >> n >> k;
vector<int>a;
for (int i = 1; i <= k; i++) a.push_back(i);
for (int i = k - 1; i >= k - (n - k); i--) a.push_back(i);
int inv = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (a[i] > a[j]) inv++;
}
}
vector<int>p;
for (int i = k; i >= 1; i--) p.push_back(i);
vector<int>b(n);
do {
int p_inv = 0;
for (int i = 0; i < n; i++) {
b[i] = p[a[i] - 1];
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (b[i] > b[j]) p_inv++;
}
}
if (p_inv <= inv) break;
} while (prev_permutation(p.begin(), p.end()));
for (int i = 0; i < k; i++) cout << p[i] << " ";
cout << "\n";
for (int i = 0; i < n; i++) cout << b[i] << " ";
cout << "\n";
}
이 코드를 이용해 몇 번 돌려보면 위 결론에 해당하는 규칙이 나오게 됩니다. 하지만 풀이라기엔 좀 아쉽네요.
그래서 좀 더 인간적인 설명을 하자면..
a = 1, 2, ..., k-1, k, k-1, k-2 가 있다고 해볼게요. 저는 1...k 이후에 나오는 수들은 밑줄을 치고 수를 셀 거예요.
수열 a에서 해당하는 부분은 2개가 있네요.
그렇다면 수열 a에서 k-2, k-1, k, k-1, k-2 이렇게 5개의 수는
수열 p = [..., k-2, k-1, k] 여기 마지막 3가지 수의 영향을 받아 수열 b가 만들어지겠죠!
그렇다면 수열 b는 1, 2, ..., k-2, k-1, k, k-1, k-2 가 되고 이는 수열 a와 같습니다.
그럼 이번엔 수열 p에서 밑줄 친 부분을 뒤집어 보겠습니다.
수열 b는 1, 2, ..., k, k-1, k-2, k-1, k 가 되고 여기서 "inversion"을 계산할 때 기존 수열 a와 다른 부분은
마지막 5가지 수에 대한 쌍 밖에 없습니다.
그럼 따로 떼어놓고 생각해볼게요.
k-2, k-1, k, k-1, k-2 -> [0, 1, 2, 1, 0]
k, k-1, k-2, k-1, k -> [3, 1, 0, 0, 0]
차이가 보이시나요? 수열은 다르지만, 저 숫자들(inversion)에 영향을 미치는 숫자는 같습니다.
inversion은 어떤 수 x가 있을 때, 그 수 앞에 x보다 더 큰 수와 뒤에 x보다 더 작은 수의 합이 되기 때문이죠.
다른 수열도 볼게요.
k-1, k, k-2, k, k-1 -> [1, 2, 0, 1, 0]
이 수열도 결국 합은 똑같습니다. 따라서 가장 이득이 되려면 p는 밑줄 구간을 반대로 뒤집어야 하고
b는 그 값을 그대로 출력해주면 됩니다.
소스 코드 1
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t; cin >> t;
while (t--)
{
int n, k;
cin >> n >> k;
int dist = n - k;
int ptr = 1;
for (int i = 1; i < k - dist; i++) {
cout << i << " ";
ptr++;
}
for (int i = k; i >= ptr; i--) {
cout << i << " ";
}
cout << "\n";
}
}
D. Program
문제
'+', '-' 로 이루어진 n개의 연산자가 주어집니다.
현재 수는 0부터 시작하며 +를 만나면 +1, -를 만나면 -1을 더해주면 됩니다.
이때 쿼리 l, r이 주어지면 n개의 연산자 중 [l, r] 구간 연산자는 무시한 채 결괏값을 출력하는 문제입니다.
풀이 1
우선 이 문제는 n, m이 최대 20만이기 때문에 브루트 포스로 풀 순 없겠네요.
사실 대부분의 쿼리 문제는 무식하게 푸는 방법이 성립되기란 쉽지 않은 것 같습니다.
이 문제도 결론부터 말하자면 prefix, suffix (접두사, 접미사)를 사용해 푸는 문제입니다.
왜 그러느냐.. 하면 오랜만에 아이패드를 집으로 가져왔으니 직접 그려서 나타낼래요!
펜슬을 너무 안 쓰다 보니 글씨가 엉망이네요 ㅠㅠ
결과적으로 특정 쿼리 l, r이 주어진다면
미리 구해둔 prefix [l-1]에서 min, max, 현재 값을 뽑은 후,
suffix [r+1]에서 min, max값을 prefix에서 구한 현재 값에 비교해 min, max값을 뽑으면 됩니다.
그렇게 되면 구간 [l, r]을 바로 삭제할 수 있죠.
정답은 max - min + 1을 한 값이 됩니다.
소스 코드 1
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t; cin >> t;
while (t--)
{
int n, m;
cin >> n >> m;
//접두사(max, min), 접미사(max, min)
vector<pair<int, int> >pre(n), post(n);
vector<int>pre_sum(n);
string s; cin >> s;
int mini = 0, maxi = 0;
int ptr = 0;
for (int i = 0; i < n; i++) {
if (s[i] == '-') ptr--;
else ptr++;
mini = min(mini, ptr);
maxi = max(maxi, ptr);
pre[i] = { maxi, mini };
pre_sum[i] = ptr;
}
mini = 0, maxi = 0, ptr = 0;
for (int i = n - 1; i >= 0; i--) {
if (i == n - 1) {
if (s[i] == '+') post[i] = { 1, 0 };
else post[i] = { 0, -1 };
}
else {
if (s[i] == '+') {
if (post[i + 1].second == 0) post[i] = { post[i + 1].first + 1, 0 };
else post[i] = { post[i + 1].first + 1, post[i + 1].second + 1 };
}
else
{
if (post[i + 1].first == 0) post[i] = { 0, post[i + 1].second - 1 };
else post[i] = { post[i + 1].first - 1, post[i + 1].second - 1 };
}
}
}
for (int i = 0; i < m; i++)
{
int l, r; cin >> l >> r;
if (l == 1 && r == n)
{
cout << 1 << "\n";
}
else if (l == 1)
{
cout << post[r ].first - post[r ].second + 1 << "\n";
}
else if (r == n)
{
cout << pre[l - 2].first - pre[l - 2].second + 1 << "\n";
}
else
{
ptr = pre_sum[l - 2]; //cout << ptr << "\n";
maxi = pre[l - 2].first; //cout << maxi << "\n";
mini = pre[l - 2].second; //cout << mini << "\n";
maxi = max(maxi, ptr + post[r ].first); //cout << maxi << "\n";
mini = min(mini, ptr + post[r].second); //cout << mini << "\n";
cout << maxi - mini + 1 << "\n";
}
}
}
}