Codeforces Round #692 (Div.1, Div.2)

A - In-game Chat

Problem - A - Codeforces

생략

 

#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 main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        int n; string s;
        cin >> n >> s;
        int cnt = 0;
        for (int i = s.size() - 1; i >= 0; i--)
        {
            if (s[i] == ')') cnt++;
            else break;
        }
 
        if (cnt > n - cnt) cout << "Yes\n";
        else cout << "No\n";
    }
}

---

B - Fair Numbers

Problem - B - Codeforces

어떤 양의 정수가 0을 제외한 모든 자릿수로 나누어 떨어지면 이 수를 fair하다고 한다.

\(n\)이 주어지면, \(n\)보다 크거나 같은 가장 작은 fair한 수를 출력해야 한다.

 

 

어떤 수가 1~9까지 모든 수를 자릿수로 가지고 있다고 생각해보자.

이 수는 2520으로 나누어 떨어져야 한다는 사실을 알 수 있다.

 

다시 말하면, 답은 \(n\)이상 \(n+2520\)미만의 수 중 하나이므로, 완전탐색으로 충분히 답을 찾을 수 있다.

 

#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 main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        ll n; cin >> n;
        while (true)
        {
            bool flag = true;
 
            ll x = n;
            while (x)
            {
                if (x % 10 && n % (x % 10)) flag = false;
                x /= 10;
            }
 
            if (flag)
            {
                cout << n << '\n';
                break;
            }
 
            n++;
        }
    }
}

---

A - Peaceful Rooks

Problem - A - Codeforces

\(n \times n\) 크기의 체스보드가 있다.

이 체스보드에 \(m\)개의 룩이 서로를 공격하지 않는 위치에 놓여 있다.

이 룩들을 모든 시점에 서로 공격받지 않도록 하면서, 모두 정대각선 (\((x, x)\))위치에 놓이게 하기 위해 룩을 이동해야 하는 최소 횟수를 알아내야 한다.

 

 

어떤 룩이 \((x,y)\)에 있다고 가정하자.

이 룩을 이동하기 위해서는 \((y, a)\)와, \((b, x)\)에 있는 룩 중 하나를 먼저 이동해야 한다는 사실을 알 수 있다.

만약 \((y,a)\)에 룩이 없다면 현재 룩을 \((y,y)\)로, \((b,x)\)에 룩이 없다면 현재 룩을 \((x,x)\)로 바로 이동시키는 것이 이득임을 알 수 있다.

 

그러면 각각의 룩을 정점으로, 현재 룩을 이동하기 위해 먼저 움직여야 하는 룩을 간선으로 하는 그래프를 만들 수 있다.

이 그래프는 1개 이상의 컴포넌트로 이루어져 있을 것이다.

정점이 1개인 컴포넌트는 정대각선에 있는 룩이므로 무시하면 되고,

그렇지 않은 컴포넌트는 컴포넌트의 크기를 답에 더해주면 된다.

 

하지만 만약 어떤 컴포넌트가 사이클을 이룬다면, 이 컴포넌트는 모든 룩이 제자리를 찾기 위해서 임의의 한 룩을 다른 위치로 이동 시켜주어야 한다. 따라서 답에 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; }
 
int n, m;
int x[100001], y[100001];
int xr[100001], yr[100001];
int cache[100001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
        {
            xr[i] = 0, yr[i] = 0;
            cache[i] = 0;
        }
 
        for (int i = 1; i <= m; i++)
        {
            cin >> x[i] >> y[i];
            xr[x[i]] = i;
            yr[y[i]] = i;
        }
 
        int ans = 0;
        for (int i = 1; i <= m; i++)
        {
            if (cache[i]) continue;
            cache[i] = 1;
 
            int ci = i;
            int cx = x[i], cy = y[i];
            
            if (cx == cy) continue;
 
            int res = 1;
            bool isLoop = false;
 
            while (xr[y[ci]])
            {
                ci = xr[y[ci]];
 
                if (cache[ci])
                {
                    isLoop = true;
                    break;
                }
 
                res++;
 
                cache[ci] = 1;
                cx = x[ci], cy = y[ci];
            }
 
            ci = i;
 
            if (!cache[yr[x[ci]]])
            {
                while (yr[x[ci]])
                {
                    ci = yr[x[ci]];
 
                    res++;
 
                    cache[ci] = 1;
                    cx = x[ci], cy = y[ci];
                }
            }
 
            if (isLoop) ans += res + 1;
            else ans += res;
        }
 
        cout << ans << '\n';
    }
}

---

B - Grime Zoo

Problem - B - Codeforces

0과 1과 ?로 이루어진 문자열이 주어진다.

?에는 0또는 1을 임의로 넣을 수 있다.

 

이 문자열의 모든 길이가 2인 부분수열에 대해,

부분수열이 "01"이라면 점수에 \(x\)를 더하고, 부분수열이 "10"이라면 점수에 \(y\)를 더한다.

받을 수 있는 최소 점수를 구해야 한다.

 

문자열의 모든 ?를 앞과 뒤 두 부분으로 나누자. (각 부분의 크기는 0일 수 있다)

\(x < y\)라면 앞 부분을 전부 0으로, 뒷 부분을 전부 1로 하는 것이,

그렇지 않다면 앞 부분을 전부 1로, 뒷 부분을 전부 0으로 하는 것이 무조건 이득임을 관찰을 통해 알 수 있다.

 

부분합이나 세그트리 등을 이용해 모든 경우에 대해 답을 구한다음, 그 중 최소값이 답이다.

 

 

#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 = numeric_limits<ll>::max();
 
const int N = 100001;
 
string s;
ll x, y;
 
ll segTree[2][N];
 
void update(ll *segTree, int idx, ll v)
{
    while (idx <= s.size())
    {
        segTree[idx] += v;
        idx += idx & -idx;
    }
}
 
ll getVal(ll* segTree, int idx)
{
    ll res = 0;
    while (idx)
    {
        res += segTree[idx];
        idx -= idx & -idx;
    }
 
    return res;
}
 
ll getVal(ll* segTree, int i, int j)
{
    return getVal(segTree, j) - getVal(segTree, i - 1);
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> s;
    cin >> x >> y;
 
    ll ans = 0;
 
    for (int i = 0; i < s.size(); i++)
    {
        int idx = i + 1;
        if (s[i] != '1')
        {
            ans += getVal(segTree[1], 1, idx - 1) * y;
            update(segTree[0], idx, 1);
        }
        else
        {
            ans += getVal(segTree[0], 1, idx - 1) * x;
            update(segTree[1], idx, 1);
        }
    }
 
    ll res = ans;
    for (int i = 0; i < s.size(); i++)
    {
        int idx = i + 1;
        if (s[i] != '?') continue;
 
        res -= getVal(segTree[1], 1, idx - 1) * y;
        res -= getVal(segTree[1], idx + 1, s.size()) * x;
 
        update(segTree[0], idx, -1);
 
        res += getVal(segTree[0], 1, idx - 1) * x;
        res += getVal(segTree[0], idx + 1, s.size()) * y;
 
        update(segTree[1], idx, 1);
 
        ans = min(ans, res);
    }
 
    for (int i = 0; i < s.size(); i++)
    {
        int idx = i + 1;
        if (s[i] != '?') continue;
 
        res -= getVal(segTree[0], 1, idx - 1) * x;
        res -= getVal(segTree[0], idx + 1, s.size()) * y;
 
        update(segTree[1], idx, -1);
 
        res += getVal(segTree[1], 1, idx - 1) * y;
        res += getVal(segTree[1], idx + 1, s.size()) * x;
 
        update(segTree[0], idx, 1);
 
        ans = min(ans, res);
    }
 
    cout << ans;
}

---

C - Poman Numbers

Problem - C - Codeforces

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

이 문자열의 값 \(f(S)\)를 다음과 같이 결정할 수 있다.

 

1. \(|S| > 1\)이라면, 임의의 \(1 \le m \le |S|\)을 고른다. \(f(S) = -f(S[1,m]) + f(S[m+1,|S|])\) 이다.

2. 그렇지 않다면, \(f(S) = 2^c\)이다.

 

어떤 수 \(T\)가 주어졌을 때, \(f(S) = T\)가 될 수 있는지 여부를 알아내야 한다.

 

 

함수가 복잡하게 쓰여 있지만, 관찰을 통해 다음과 같은 사실을 알 수 있다.

1. 가장 뒤에 있는 문자의 부호는 무조건 +이다.

2. 2번째로 뒤에 있는 문자의 부호는 무조건 -이다.

3. 그 외의 문자의 부호는 +, - 두 경우 모두 가능하다.

 

따라서 문제를 2의 제곱꼴인 양의 정수 \(n-2\)개가 주어졌을 때, 이 정수들을 더하거나 빼서 \(X\)를 만들 수 있는지 여부를 묻는 문제로 바꿔 생각할 수 있다. (\(X\)는 \(T\)에서 뒤에 있는 2개의 문자를 더하고 뺀 값이다.)

 

그리디하게 큰 수 부터 \(X\)를 만들어 가면 된다.

 

#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, T;
string s;
 
ll cnt[26];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n >> T;
    cin >> s;
 
    for (int i = 0; i + 2 < n; i++)
    {
        cnt[s[i] - 'a']++;
    }
 
    T += (1ll << (s[n - 2] - 'a'));
    T -= (1ll << (s[n - 1] - 'a'));
 
    for (int i = 25; i >= 0; i--)
    {
        for (int j = 0; j < cnt[i]; j++)
        {
            if (T > 0) T -= (1ll << i);
            else T += (1ll << i);
        }
    }
 
    bool ans = (T == 0);
 
    if (ans) cout << "Yes";
    else cout << "No";
}

---

D - The Thorny Path

Problem - D - Codeforces

---

E - No Game No Life

Problem - E - Codeforces

추가 예정

---

F - My Beautiful Madness

Problem - F - Codeforces

추가 예정