Codeforces Round #696 (Div. 2)

A - Puzzle From the Future

Problem - A - Codeforces

\(n\)길이의 이진 문자열 \(b\)가 주어진다.

 

여기에 새로운 \(n\)길이의 이진 문자열 \(a\)를 만들어서, 두 이진 문자열을 더하려고 한다.

두 이진 문자열은 자리올림 없이 더해진다. (결과에 2가 포함되어 있을 수 있다)

더해진 다음, 연속된 같은 숫자들은 1개로 압축된다.

 

두 이진 문자열을 더했을 때 합이 최대가 되는 \(a\)를 알아내야 한다.

 

 

자릿수가 클 수록 큰 수가 되므로, 더한 후에 연속된 같은 숫자들이 없는것이 무조건 이득이다.

이를 만족하도록 앞에서부터 더한 결과가 최대한 큰 수가 되도록 \(a\)를 만들어 주면 된다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int n;
string b;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n;
        cin >> b;
 
        int last = -1;
        for (int i = 0; i < n; i++)
        {
            if (b[i] == '0')
            {
                if (last == 1) cout << 0, last = 0;
                else cout << 1, last = 1;
            }
            else
            {
                if (last == 2) cout << 0, last = 1;
                else cout << 1, last = 2;
            }
        }
 
        cout << '\n';
    }
}

---

B - Different Divisors

Problem - B - Codeforces

다음을 만족하는 가장 작은 양의 정수 \(a\)를 출력해야 한다.

 

1. \(a\)는 4개 이상의 약수를 가져야 한다.

2. \(a\)의 서로 다른 두 약수를 골랐을 때, 두 약수의 차는 항상 \(d\) 이상이어야 한다.

 

 

\(1+d\)이상의 소수 중 가장 작은 것을 \(x\)라고 하고, \(x+d\)이상의 소수 중 가장 작은 것을 \(y\)라고 하자.

답은 \(xy\)이다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
vector <ll> p;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    p.push_back(2);
    for (ll i = 3; i <= 100000; i++)
    {
        bool flag = true;
        for (int j = 0; j < p.size() && p[j] * p[j] <= i; j++)
        {
            if (i % p[j] == 0)
            {
                flag = false;
                break;
            }
        }
 
        if (flag) p.push_back(i);
    }
 
    int t; cin >> t;
    while (t--)
    {
        ll d; cin >> d;
 
        ll a = *lower_bound(p.begin(), p.end(), 1 + d);
        ll b = *lower_bound(p.begin(), p.end(), a + d);
 
        cout << a * b << '\n';
    }
}

---

C - Array Destruction

Problem - C - Codeforces

\(2n\)개의 양의 정수로 이루어진 배열 \(a\)가 주어진다.

 

이 배열의 원소를 없애기 위해 다음과 같은 연산을 할 수 있다.

 

1. 임의의 양수 \(x\)를 정한다.

2. 배열에서 합이 \(x\)이 두 원소 \(a,b\)를 고르고, 배열에서 제거한 다음 \(x\)를 \(\max(a,b)\)로 대체한다. 이를 \(n\)번 반복한다.

 

배열의 원소를 모두 없앨 수 있는지 여부를 알아내고, 가능하다면 그 과정을 출력해야 한다.

 

 

먼저, \(x\)는 항상 \(a\)에 현재 남아 있는 원소 중 가장 큰 수와 다른 원소 하나의 합이어야 한다는 사실을 알 수 있다.

따라서 초기 \(x\)가 될 수 있는 수는 \(2n-1\)가지이고, 각각의 경우에 대해 직접 set등으로 시뮬레이션 해보면 된다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int n;
int a[2001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n;
        for (int i = 0; i < n * 2; i++) cin >> a[i];
 
        bool hasAns = false;
        int fv = -1;
        vector <pii> ans;
 
        sort(a, a + n * 2);
        for (int i = 0; i < n * 2 - 1; i++)
        {
            fv = a[n * 2 - 1] + a[n * 2 - 2 - i];
 
            bool isAns = true;
            
            ans.clear();
            multiset<int> st(a, a + 2 * n);
 
            int cv = fv;
            for (int i = 0; i < n; i++)
            {
                int b = *prev(st.end());
                st.erase(prev(st.end()));
 
                auto it = st.find(cv - b);
                if (it == st.end())
                {
                    isAns = false;
                    break;
                }
 
                int a = *it;
                st.erase(it);
 
                ans.push_back({ a,b });
                cv = b;
            }
 
            if (isAns)
            {
                hasAns = true;
                break;
            }
        }
 
        if (hasAns)
        {
            cout << "YES\n";
            cout << fv << '\n';
            for (auto it : ans)
                cout << it.first << ' ' << it.second << '\n';
        }
        else cout << "NO\n";
    }
}

---

D - Cleaning

Problem - D - Codeforces

\(n\)크기의 배열 \(a\)가 주어진다.

 

이 배열의 연속된 두 원소가 모두 0보다 크다면, 둘 다 1을 빼는 연산을 할 수 있다.

초기에 연속된 두 원소를 단 한 번 바꿀 수 있고, 그 후 위의 연산은 원하는 만큼 사용할 수 있다.

 

이 때 \(a\)의 모든 원소를 0으로 만들 수 있는지 여부를 알아내야 한다.

 

두 원소를 초기에 바꿀 수 없다면 가능 여부를 알아내는 것은

$$\sum_{i=1}^k (-1)^{k-i} \cdot a_i \ge 0$$

위의 식이 \(1 \le k \le n\)에 대해서 모두 만족하는지 확인함으로써 알 수 있다.

(\(k=n\)일 때는 \(\ge 0\)이 아니라 \(= 0\)이다.)

 

따라서 위 식의 값의 부분 최소값을 저장해 두면, 임의의 연속된 두 원소를 바꾸게 되었을 때 변화량을 이용해 모든 \(k\)에 대해 위 식을 만족하는지 \(O(1)\)로 알 수 있게 된다.

 

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
const ll INF = 1e18;
 
int n;
ll a[200001];
ll psum[200001];
 
ll min0[200001];
ll min1[200001];
 
ll pmin[200001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n;
 
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
            psum[i] = -psum[i - 1] + a[i];
 
            pmin[i] = min(pmin[i - 1], psum[i]);
        }
 
        bool ans = true;
        for (int i = 1; i <= n; i++)
        {
            if (psum[i] < 0) ans = false;
        }
 
        if (psum[n] != 0) ans = false;
 
        if (ans)
        {
            cout << "YES\n";
            continue;
        }
 
        ll cmin0 = INF, cmin1 = INF;
 
        for (int i = n; i >= 1; i--)
        {
            if (i % 2)
                cmin1 = min(cmin1, psum[i]);
            else
                cmin0 = min(cmin0, psum[i]);
 
            min0[i] = cmin0;
            min1[i] = cmin1;
        }
 
        for (int i = 1; i < n; i++)
        {
            // swap(a[i], a[i+1])
            if (pmin[i - 1] < 0) continue;
 
            ll d = 2 * a[i + 1] + -2 * a[i];
            if (i % 2 == 0) d = -d;
 
            if (min1[i + 1] + d >= 0 && min0[i + 1] - d >= 0 && psum[i] - a[i] + a[i + 1] >= 0)
            {
                if (n % 2 == 1 && psum[n] + d == 0
                    || n % 2 == 0 && psum[n] - d == 0)
                {
                    ans = true;
                    break;
                }
            }
        }
 
        if (ans) cout << "YES\n";
        else cout << "NO\n";
    }
}

---

E - What Is It?

Problem - E - Codeforces

\(n\)길이의 임의의 순열 \(p\)를 만들자.

 

이 순열에서 \(p_j = i\)를 만족하는 서로 다른 두 인덱스 \(i, j\)를 골라서, \(p_i\)와 \(p_j\)를 바꾸는 연산을 할 수 있다.

이 때 \((j-i)^2\)의 시간이 소요된다.

 

순열에 더 이상 위의 연산을 할 수 없을 때까지 이를 반복한다고 할 때,

소요되는 시간이 최대가 되는 초기 순열과 연산 순서를 출력해야 한다.

 

 

해설은 생략한다.

코드를 실행해서 출력을 보는게 훨씬 이해가 빠를것 같다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
ll n;
vector <pii> ans;
ll a[100001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n;
        ans.clear();
 
        ll sum = 0;
        for (int i = 1; i <= n; i++) a[i] = i;
 
        sum += (n - 1) * (n - 1);
        ans.push_back({ 1, n });
        swap(a[1], a[n]);
 
        if (n % 2 == 1)
        {
            sum += (n / 2) * (n / 2);
            ans.push_back({ n / 2 + 1, 1 });
            swap(a[1], a[n / 2 + 1]);
        }
 
        for (int i = 0; i < n / 2 - 1; i++)
        {
            ll l, r;
 
            l = 1, r = n - 1 - i;
            sum += (r - l) * (r - l);
            ans.push_back({ r, l });
            swap(a[l], a[r]);
 
            l = 2 + i, r = n;
            sum += (r - l) * (r - l);
            ans.push_back({ l, r });
            swap(a[l], a[r]);
        }
 
        reverse(ans.begin(), ans.end());
 
        cout << sum << '\n';
        for (int i = 1; i <= n; i++) cout << a[i] << ' ';
        cout << '\n';
        cout << ans.size() << '\n';
        for (auto it : ans)
            cout << it.first << ' ' << it.second << '\n';
    }
}

---

F - 1 2 3 4 ...

Problem - F - Codeforces

추가 예정