Codeforces Round #712 (Div1, Div. 2)

A - Déjà Vu

Problem - A - Codeforces

문자열 \(s\)가 주어진다.

\(s\)의 임의의 위치에 문자 'a'를 추가하여, \(s\)가 팰린드롬이 아니도록 만들어야 한다.

 

\(s\)가 'a'로만 이루어져 있다면 불가능하다.

그렇지 않다면, \(s\)의 맨 앞이나 맨 뒤에 'a'를 추가하면 둘 중 하나는 답이다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
string s;
bool isPal(string s)
{
    for (int i = 0; i < s.size(); i++)
        if (s[i] != s[s.size() - 1 - i]) return false;
 
    return true;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> s;
        string s1 = "a" + s;
        string s2 = s + "a";
 
        if (!isPal(s1))
        {
            cout << "YES\n";
            cout << s1 << '\n';
        }
        else if (!isPal(s2))
        {
            cout << "YES\n";
            cout << s2 << '\n';
        }
        else cout << "NO\n";
    }
}

---

B - Flip the Bits

Problem - B - Codeforces

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

이 \(a\)의 접두사가 같은 갯수의 0과 1을 가지고 있다면, 이 접두사를 반전시킬 수 있다.

\(a\)를 적절히 반전시켜 \(b\)로 만들 수 있는지 여부를 알아내야 한다.

 

\(a\)와 \(b\)를 뒤에서 부터 살펴보자.

탐색 도중 \(a_i \ne b_i\)인 \(i\)가 있다면, 지금 반전시켜주어야 한다.

실제로 반전시켜줄 필요는 없고, 반전시켰다는 표시만 해준다음 0과 1을 반대로 생각하면 된다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
int n;
string a, b;
int sum[300001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n;
        cin >> a >> b;
        for (int i = 0; i < n; i++)
            sum[i + 1] = sum[i] + a[i] - '0';
 
        bool ans = true;
        if (n % 2 && a.back() != b.back()) ans = false;
 
        bool isFliped = false;
 
        for (int i = n / 2 * 2; i > 0; i -= 2)
        {
            if ((a[i - 2] == b[i - 2]) != (a[i - 1] == b[i - 1])) ans = false;
            if (isFliped ^ (a[i - 2] == b[i - 2])) continue;
 
            if (sum[i] != i / 2) ans = false;
 
            isFliped = !isFliped;
        }
 
        if (ans) cout << "YES\n";
        else cout << "NO\n";
    }
}

---

A - Balance the Bits

Problem - A - Codeforces

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

이 이진 문자열을 이용해 \(n\)길이의 괄호 문자열 2개를 만들려고 한다.

 

\(s_i = 1\)이면, \(a_i = b_i\)여야 하고,

\(s_i = 0\)이면, \(a_i \ne b_i\)여야 한다.

 

위를 만족하면서 \(a, b\)가 모두 올바른 괄호 문자열이 되도록 만들 수 있는지 여부를 알아내야 한다.

가능하다면, 실해를 출력한다.

 

 

먼저, \(s\)에서 0의 개수는 짝수여야 한다.

\(a, b\) 각각에서 \(s_i = 0\)인 인덱스에서 절반은 '(', 절반은 ')' 로 이루어져야 하기 때문이다.

'('와 ')'가 연속으로 나오지 않는 것이 유리함을 알 수 있다. 둘을 번갈아가며 채우자.

 

그리고 \(s_i = 1\)인 인덱스들에 대해 생각해보면, 앞 절반은 '(', 뒤 절반은 ')'로 채우는 것이 최적임을 알 수 있다.

 

이렇게 2개의 문자열을 만든다음, 두 문자열이 올바른 괄호 문자열인지 확인하면 된다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
int n;
string s;
int ans[2][200001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n >> s;
 
        bool hasAns = true;
 
        vector <int> idx[2];
        for (int i = 0; i < n; i++)
        {
            idx[s[i] - '0'].push_back(i);
        }
 
        if (idx[0].size() % 2) hasAns = false;
 
        for (int i = 0; i < idx[1].size(); i++)
        {
            if (i < idx[1].size() / 2)
                ans[0][idx[1][i]] = ans[1][idx[1][i]] = 0;
            else
                ans[0][idx[1][i]] = ans[1][idx[1][i]] = 1;
        }
 
        for (int i = 0; i < idx[0].size(); i++)
        {
            ans[0][idx[0][i]] = i % 2;
            ans[1][idx[0][i]] = (i + 1) % 2;
        }
        
        for (int k = 0; k < 2; k++)
        {
            int sum = 0;
            for (int i = 0; i < n; i++)
            {
                if (ans[k][i] == 0) sum++;
                else sum--;
 
                if (sum < 0) hasAns = false;
            }
 
            if (sum) hasAns = false;
        }
 
        if (!hasAns) cout << "NO\n";
        else
        {
            cout << "YES\n";
            for (int i = 0; i < n; i++)
                cout << (ans[0][i] == 0 ? '(' : ')');
            cout << '\n';
            for (int i = 0; i < n; i++)
                cout << (ans[1][i] == 0 ? '(' : ')');
            cout << '\n';
        }
    }
}

---

B - 3-Coloring

Problem - B - Codeforces

\(n \times n\)크기의 격자가 있다.

이 격자에 3가지의 색으로 색칠을 하려고 한다.

 

격자를 이용해 두 사람이 게임을 하려고 한다.

선공은 3가지의 색 중 사용할 수 없는 색 1가지를 골라 말해준다.

후공은 그 색을 제외한 2가지의 색 중 하나를 골라 격자의 색칠되지 않은 칸 중 하나를 골라 칠한다.

 

만약 격자에서 인접한 두 칸이 같은 색으로 색칠되어 있게 되면, 선공이 승리한다.

그러지 않고 격자를 모두 채웠다면, 후공이 승리한다.

 

후공으로 이 게임을 승리해야 한다.

 

격자의 모든 칸을, 체스판으로 따졌을 때 흰색칸과 검은색칸 2가지로 나누자.

흰색칸은 모두 1로, 검은색칸은 모두 2로 채운다고 생각하고 게임을 진행한다.

두 종류의 칸 중 한 종류의 칸이 모두 채워졌다면, 남은 칸은 2가지의 색으로 칠할 수 있게 된다.

ex) 흰색칸이 1로 모두 채워졌다면 검은색칸은 2 or 3, 검은색 칸이 2로 모두 채워졌다면 흰색 칸은 1 or 3으로 채울 수 있다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
int n;
int a[101][101];
vector <pii> v[2];
 
int query()
{
    int res; cin >> res;
    return res;
}
 
void setColor(int c, int x, int y)
{
    a[x][y] = c;
    cout << c << ' ' << x << ' ' << y << endl;
}
 
void printBoard()
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++) cout << a[i][j] << ' ';
        cout << endl;
    }
}
 
int main()
{
    ios::sync_with_stdio(0);
    //cin.tie(0), cout.tie(0);
 
    cin >> n;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++)
    {
        v[(i + j) % 2].push_back({ i,j });
    }
 
    int curColor = 0, nxtColor = 0;
    int res = query();
    if (res == 1) curColor = 2, nxtColor = 1;
    else curColor = 1, nxtColor = 2;
 
    setColor(curColor, 1, 1);
 
    int p1 = 1, p2 = 0;
    for (int i = 1; i < n * n; i++)
    {
        int res = query();
 
        if (p1 == v[0].size() || p2 == v[1].size())
        {
            if (p1 == v[0].size())
            {
                auto it = v[1][p2++];
                int x = it.first, y = it.second;
 
                if (res == nxtColor)
                    setColor(3, x, y);
                else
                    setColor(nxtColor, x, y);
            }
            else
            {
                auto it = v[0][p1++];
                int x = it.first, y = it.second;
 
                if (res == curColor)
                    setColor(3, x, y);
                else
                    setColor(curColor, x, y);
            }
 
            continue;
        }
 
        if (res == curColor)
        {
            auto it = v[1][p2++];
            int x = it.first, y = it.second;
 
            setColor(nxtColor, x, y);
        }
        else
        {
            auto it = v[0][p1++];
            int x = it.first, y = it.second;
 
            setColor(curColor, x, y);
        }
    }
 
    //printBoard();
}

---

C - Travelling Salesman Problem

Problem - C - Codeforces

\(n\)개의 도시가 있다.

각 도시는 아름다운 수치 \(a_i\)와, 비용 \(c_i\)로 이루어져 있다.

 

1번 도시에서 시작해, 모든 도시를 한 번 씩 방문한 다음 다시 1번 도시로 돌아오려고 한다.

\(i\)번 도시에서 \(j\)번 도시로 이동할 때 \(max(c_i, a_j-a_i)\)의 비용이 든다고 할 때, 필요한 비용의 최소값을 구해야 한다.

 

 

먼저 \(\sum c_i\)의 비용은 고정적으로 든다는 사실을 알 수 있다.

이 비용을 고정시켜둔 상태에서, \(a_i\)에 대한 비용을 최소화 시켜 보자.

 

\(a_i\)가 큰 도시에서 작은 도시로 가는 데에는 추가 비용이 발생하지 않는다.

하지만 우리는 시작했던 도시로 돌아와야 하므로, 작은 도시에서 큰 도시로 이동하는데 필요한 비용을 최소화 해야 한다.

 

도시들을 \(a_i\)가 작은 순으로 정렬하자.

\(i\)번째 도시에서 \(c_i\)의 비용이 드므로, \(a_j \le a_i + c_i\)에 해당하는 \(j\)번 도시는 추가 비용 없이 이동할 수 있다.

또, 추가로 \(a_k > a_i + c_i\)에 해당하는 가장 작은 인덱스의 \(k\)번 도시까지의 비용은 \(a_k - a_i - c_i\)의 비용으로 이동할 수 있다.

 

\(DP_i : \) (정렬한 후에) \(i\)번째 도시까지 이동할 때 필요한 최소 추가 비용

으로 DP를 정의하면, 세그먼트 트리를 이용해 최적화 하여 문제를 해결할 수 있게 된다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int N = 100001;
const ll INF = 1e18;
 
ll n;
pll v[100001];
ll segTree[N * 4];
ll lazy[N * 4];
 
void setLazy(int ptr, int l, int r)
{
    ll val = lazy[ptr]; lazy[ptr] = INF;
 
    segTree[ptr] = min(segTree[ptr], val);
    if (l != r)
    {
        lazy[ptr * 2] = min(lazy[ptr * 2], val);
        lazy[ptr * 2 + 1] = min(lazy[ptr * 2 + 1], val);
    }
}
 
void update(int ptr, int l, int r, int i, int j, ll val)
{
    if (lazy[ptr] != INF) setLazy(ptr, l, r);
 
    if (j < l || r < i) return;
    if (i <= l && r <= j)
    {
        segTree[ptr] = min(segTree[ptr], val);
        if (l != r)
        {
            lazy[ptr * 2] = min(lazy[ptr * 2], val);
            lazy[ptr * 2 + 1] = min(lazy[ptr * 2 + 1], val);
        }
 
        return;
    }
 
    update(ptr * 2, l, (l + r) / 2, i, j, val);
    update(ptr * 2 + 1, (l + r) / 2 + 1, r, i, j, val);
 
    segTree[ptr] = min(segTree[ptr * 2], segTree[ptr * 2 + 1]);
}
 
ll getVal(int ptr, int l, int r, int i, int j)
{
    if (lazy[ptr] != INF) setLazy(ptr, l, r);
 
    if (j < l || r < i) return INF;
    if (i <= l && r <= j) return segTree[ptr];
 
    return min(
        getVal(ptr * 2, l, (l + r) / 2, i, j),
        getVal(ptr * 2 + 1, (l + r) / 2 + 1, r, i, j)
    );
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    fill(segTree, segTree + N * 4, INF);
    fill(lazy, lazy + N * 4, INF);
 
    cin >> n;
 
    ll ans = 0;
 
    for (int i = 0; i < n; i++)
    {
        ll a, c; cin >> a >> c;
        v[i] = { a,c };
        ans += c;
    }
 
    sort(v, v + n);
 
    update(1, 0, n - 1, 0, 0, 0);
    for (int i = 0; i < n - 1; i++)
    {
        ll res = getVal(1, 0, n - 1, i, i);
        int j = upper_bound(v, v + n, pll(v[i].first + v[i].second, INF)) - v;
 
        update(1, 0, n - 1, i + 1, j - 1, res);
        if (j < n) update(1, 0, n - 1, j, j, res + v[j].first - v[i].first - v[i].second);
    }
 
    ll res = getVal(1, 0, n - 1, n - 1, n - 1);
    ans += res;
 
    cout << ans;
}

---

D - Flip the Cards

Problem - D - Codeforces

---

E - 2-Coloring

Problem - E - Codeforces

추가 예정

---

F - Balance the Cards

Problem - F - Codeforces

추가 예정