Codeforces Round #696 (Div. 2)
문제 링크
Dashboard - Codeforces Round #696 (Div. 2) - Codeforces
codeforces.com
A. Puzzle From the Future
문제
이진수 두 개를 가능한 한 크게 만드는 또 다른 이진수를 구하는 문제이다.
단, 연속된 수가 있으면 압축이 된다.
풀이 1
이 문제는 그리디하게 해결할 수 있습니다.
우선, 연속된 수에 대한 "아주 강렬한" 조건이 있기 때문에 직감적으로 이진수를 연속되게 만들면 안 될 것 같네요.
이미 이진수 하나가 주어져있기 때문에, 우리는 나머지 정답이 될 이진수는 연속되지 않도록 만들 수 있습니다.
또한 "가장 크게 만드는" 조건이 있으므로 최대한 2를 만들도록 노력해야겠죠.
테스트 케이스 4번의 경우 주어진 이진수는 "111000" 입니다.
우선 첫 수는 반드시 2를 만들 수 있으니 "1"
그다음 수는 2를 만들면 연속되므로 "10"
그다음수는 다시 2를 만들 수 있으니 "101"
다음은 1이 최대이므로 "1011"
...
이런 식으로 그 이전에 만들어 준 수와 비교해서 가장 크도록 그리디 하게 만들어주면 됩니다.
소스 코드 1
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
int t; cin >> t;
while (t--)
{
int n; cin >> n;
string b; cin >> b;
string a = "";
int pre = 0;
a += '1';
for (int i = 1; i < n; i++)
{
int pre = (b[i - 1] - '0') + (a[i - 1] - '0');
if (b[i] == '0')
{
if (pre == 2) {
a += '1'; pre = 1;
}
else if (pre == 1) {
a += '0'; pre = 0;
}
else {
a += '1'; pre = 1;
}
}
else
{
if (pre == 2) {
a += '0'; pre = 1;
}
else if (pre == 1) {
a += '1'; pre = 2;
}
else {
a += '1'; pre = 2;
}
}
}
cout << a << "\n";
}
return 0;
}
B. Different Divisors
문제
양의 정수 d가 주어졌을 때, 조건을 만족하는 양의 정수 a를 찾는 문제이다.
a는 최소 4개의 약수를 가질 것.
모든 약수들의 간격은 최소 d 이상은 되어야 함.
풀이 1
상당히 헤매었던.. 문제입니다.
우선 1을 제외한 모든 수는 약수를 최소 2개는 갖습니다. (1과 자기 자신)
나머지 두 개만 찾으면 되겠네요!
처음에 간단히 생각해볼 수 있는 방법은
1, 1 + d, 1+ 2d, (1 + d) * (1 + 2d)
이렇게 있으면 a = (1 + d) * (1 + 2d) 라면 위 조건을 모두 만족시킬 수 있다는 점입니다.
맞는 말입니다.
으앙! 쳐맞는 말이었군요 ㅠㅠ
무슨 일인고.. 하니 그 a값은 약수로 1, 1 + d, 1+ 2d, a 딱 4가지만 가진다는 보장이 없습니다 ㅠ
1과 1+d 사이 또는 1+d ~ 1+2d / 1+2d ~ a 사이에 또 a의 약수가 있다면 차이가 d이하가 되므로 틀리게 됩니다.
그리고 1+d, 1+2d 도 약수가 있으면 큰일이겠네요 ㅠ
따라서 1을 제외한 나머지 2가지 수는 소수이고, 마지막 수가 2가지 소수를 곱한 값이면 모든 조건을 만족시킬 수 있고, 이때 a값이 최소임은 자명합니다.
문제에서 d값은 최대 1만이므로 한 20만까지 에라토스테네스의 체를 이용해 소수를 모두 구하고
2부터 시작해서 차이가 +d가 나도록 소수 2개를 골라주면 됩니다.
소스 코드 1
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool check[1000010];
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
int t; cin >> t;
check[1] = true;
for (int i = 2; i * i <= 200000; i++) {
if (!check[i]) {
for (int j = i + i; j <= 200000; j += i) {
check[j] = true;
}
}
}
vector<int>pr;
for (int i = 1; i <= 200000; i++) if (!check[i]) pr.push_back(i);
while (t--)
{
int d; cin >> d;
int pre = 1;
int cnt = 0;
int ans = 1;
for (int i = 0; i < pr.size(); i++) {
if (pr[i] - pre >= d) {
ans *= pr[i];
pre = pr[i];
cnt++;
if (cnt == 2) break;
}
}
cout << ans << "\n";
}
return 0;
}
C. Array Destruction
문제
쓸모없는 2n 개의 양의 정수가 담긴 배열이 주어진다.
다음과 같은 작업을 통해 배열에 있는 원소를 다 비워버리자.
1. 우선 아무 양의 정수 x를 고른다. (배열에 없어도 된다.)
2. 합이 x가 되는 두 원소를 고르고, x를 두 원소 중 큰 수로 바꾼 후, 두 원소를 삭제한다. 이 과정을 n번 반복한다.
만약 합이 x가 되는 두 원소가 없다면 이 작업은 중단되며 그때 "NO"를 출력한다.
그렇지 않다면 그 과정을 모두 출력하면 된다.
풀이 1
우선, 합이 x가 되는 두 원소를 a, b라 하면 (x = a + b) a, b가 x보다 작음은 자명하다. (모든 원소는 양의 정수)
그렇다면 맨 처음 x를 정할 때, 그 x는 배열에 있는 수들 중 가장 큰 수보다 반드시 커야 한다.
왜 그런가 하면..
배열 a를 오름차순으로 정렬했을 때 a1, a2,..., a(2n-1), a(2n)로 원소가 정렬되었다고 해보자.
맨 처음 x가 a(2n) 보다 작다면 처음에 두 수 a,b를 고를 때 a(2n)을 선택할 수 없게 되고
a(2n)을 선택하지 못한다면 영영 x는 a(2n)보다 작으므로 결국 고르지 못하게 되기 때문이다.
이는 a(2n)을 고른 이후에도 마찬가지로, 배열에 있는 수들 중 가장 큰 수를 계속 골라야만
그다음 큰 수를 고를 수 있게 된다.
따라서 x는 큰 수부터 시작해서 점점 작아지는 느낌으로 가야 한다.
여기까지 이해했다면 이다음은 브루트 포스의 영역이다.
맨 처음 x는 우리가 아무거나 선택할 수 있기 때문에
가장 큰 수를 제외하고 하나씩 선택해서 시뮬레이션을 돌려보면 된다. (x = (가장 큰 수) + (아무거나 수))
이렇게 수를 골랐다면 이제 다음 수는 (가장 큰 수) = (그다음 큰 수) + (가장 큰 수와 다음 큰 수의 차이)...로 계속 이루어지므로 두 번째 수가 있으면 계속하고, 없으면 멈추면 된다.
단, 수를 찾는데 시간을 줄이기 위해 map을 사용하자.
n이 최대 1000밖에 안되므로 시뮬레이션해도 500번이고 모든 경우를 다 따져보아도
1000 x 500으로 50만 번 계산하고 끝나게 된다.
소스 코드 1
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
int t; cin >> t;
while (t--)
{
int n; cin >> n;
map<int, int>mp;
vector<int>v(2 * n);
for (int i = 0; i < 2 * n; i++) {
cin >> v[i];
mp[v[i]]++;
}
map<int, int> tmp = mp;
sort(v.begin(), v.end());
vector<pair<int, int> > ans;
int pre = v[2 * n - 1];
bool flag = false;
for (int k = 2 * n - 2; k >= 0; k--) {
mp = tmp;
pre = v[2 * n - 1];
vector<pair<int, int> >tans;
tans.push_back({ v[k], pre });
mp[v[k]]--; mp[pre]--;
int ptr = 2 * n - 2;
for (int i = 0; i < n - 1; i++) {
while (mp[v[ptr]] == 0) ptr--;
mp[v[ptr]]--;
if (mp[pre - v[ptr]] == 0) {
break;
}
else {
tans.push_back({ v[ptr], pre - v[ptr] });
mp[pre - v[ptr]]--;
pre = v[ptr];
ptr--;
if (i == n-2) {
flag = true;
ans = tans;
}
}
}
if (flag) break;
}
if (n == 1) {
cout << "YES\n";
cout << v[0] + v[1] << "\n";
cout << v[0] << " " << v[1] << "\n";
}
else if (ans.size() == n) {
cout << "YES\n";
cout << ans[0].first + ans[0].second << "\n";
for (int i = 0; i < ans.size(); i++) {
cout << ans[i].first << " " << ans[i].second << "\n";
}
}
else {
cout << "NO\n";
}
}
return 0;
}
D. Cleaning
문제
n개의 돌무더기를 제거하려고 한다.
제거 방식은 다음 작업을 따르는데
두 개의 돌이 있는 이웃 돌 무더기를 고른 후 각각 -1씩 하는 작업이다.
이것만 하면 너무 쉬우니 한 가지 능력이 있는데
바로 제거하기 전, 이웃되는 두 돌무더기를 바꿀 수 있다는 점이다. 이 능력은 너무 사기라 최대 1번만 사용 가능하다.
모든 돌무더기를 제거할 수 있겠는가?
풀이
머리에 털나고 처음 풀어보는 무려 2200점 레이팅의 문제이다.. ㄷ
원래 웬만하면 쳐다보지도 않는 문제인데.. 요즘 어려운걸 많이 풀어봐야 한다는 생각과.. 이 문제는 좀 할 만한 것 같아서 풀이에 올려놓는다.
우선 에디토리얼에 나온 문제 설명은 이렇다.
능력을 사용하지 않고, 돌 무더기를 모두 치울 수 있는 조건이 어떻게 되는가?
1. 우선 첫 번째 돌무더기는 두 번째 돌 무더기 밖에 같이 치울 친구가 없다.
따라서 a[1] > a[2] 가 되버리면 a[2]를 다 쓰더라도 첫 번째 돌 무더기에 있는 돌들을 모두 제거할 수 없다.
2. 만약 첫 번째를 모두 제거하였더라면, 두 번째는 a[2] - a[1]이 된다. 따라서 세 번째 돌무더기만 이용해 두 번째를 치워야 한다. 원리는 1번과 동일하다.
3. 이렇게 1 ~ n 번째 인덱스를 순회하다가 a[i] > a[i+1] 가 되어버리면, 이는 능력없이 절대 치울 수 없고
a[i] <= a[i+1] 라면, a[i+1] = a[i+1] - a[i] 로 초기화해야 한다.
그럼 이 작업을 모든 i에 대해서 다 해야 하는가? 그렇지 않다.
만약 i와 i+1 번째 돌무더기를 바꾸었더라도, 1, 2,... i-2 번째 돌무더기는 그 어떤 영향을 받지 않는다.
또한 i+2,..., n 도 마찬가지이다.
따라서 미리 prefix, suffix 전처리를 해준다면 (1,... i-1을 청소했을 때 i번째 돌무더기 돌 개수)
i, i+1을 바꾸고, prefix(i-1), suffix(i + 2)를 바로 알 수 있으므로 총 O(n) 시간 복잡도로 계산이 가능하다.
소스 코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t, n;
bool check(vector<ll> v)
{
for (int i = 0; i < v.size() - 1; i++)
{
if (v[i] > v[i + 1]) return false;
else {
v[i + 1] -= v[i];
}
}
if (v.back() != 0) return false;
else return true;
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> t;
while (t--)
{
cin >> n;
vector<ll>a(n);
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
if (check(a)) {
cout << "YES\n";
continue;
}
if (n == 1)
{
cout << "NO\n";
continue;
}
vector<ll>p(n), s(n);
vector<ll>b = a;
p[0] = b[0];
for (int i = 1; i < n; i++)
{
if (p[i - 1] == -1 || b[i - 1] > b[i]) {
p[i] = -1;
}
else {
b[i] -= b[i - 1];
b[i - 1] = 0;
p[i] = b[i];
}
}
b = a;
s[n - 1] = b[n - 1];
for (int i = n - 2; i >= 0; i--)
{
if (s[i + 1] == -1 || b[i + 1] > b[i]) {
s[i] = -1;
}
else {
b[i] -= b[i + 1];
b[i + 1] = 0;
s[i] = b[i];
}
}
bool flag = false;
for (int i = 0; i < n - 1; i++)
{
if (i == 0 || i == n-2) {
swap(a[i], a[i + 1]);
if (check(a)) {
cout << "YES\n";
flag = true;
break;
}
swap(a[i], a[i + 1]);
continue;
}
vector<ll> c = { p[i - 1], a[i], a[i + 1], s[i + 2] };
if (p[i - 1] == -1 || s[i + 2] == -1) continue;
swap(c[1], c[2]);
if (check(c))
{
cout << "YES\n";
flag = true;
break;
}
}
if (flag) continue;
cout << "NO\n";
}
return 0;
}