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

찐렌지

A - Common Subsequence

Problem - A - Codeforces

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

두 수열의 길이가 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; }
 
int n, m;
int a[1001], b[1001];
 
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 = 0; i < n; i++) cin >> a[i];
        for (int i = 0; i < m; i++) cin >> b[i];
 
        int ans = -1;
        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++)
        {
            if (a[i] == b[j]) ans = a[i];
        }
 
        if (ans != -1) cout << "YES\n1 " << ans << '\n';
        else cout << "NO\n";
    }
}

---

B - Sequential Nim

Problem - B - Codeforces

\(n\)개의 돌 무더기가 있고, 각 무더기에는 \(a_i\)개의 돌이 있다.

님 게임을 하려고 하는데, 각 차례의 플레이어는 돌이 존재하는 가장 첫 무더기에서만 돌을 가져갈 수 있다.

 

두 사람이 이상적으로 플레이했을 때, 선공과 후공 중 이기는 사람이 누군지 알아내야 한다.

 

모든 무더기에 돌이 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 main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        int n; cin >> n;
 
        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            int x; cin >> x;
            if (!ans && x > 1) ans = i % 2 + 1;
        }
 
        if (ans == 0) ans = (n + 1) % 2 + 1;
 
        if (ans == 1) cout << "First\n";
        else cout << "Second\n";
    }
}

---

A - Prefix Flip (Hard Version)

Problem - A2 - Codeforces

\(n\)길이의 이진문자열 \(a,b\)가 있다.

이 문자열의 접두사를 골라 비트를 모두 반전시키고, 위치를 뒤집는 연산을 할 수 있다.

 

\(a\)에 이 연산을 \(2n\)번 이하로 사용해서 \(b\)로 만들어야 한다.

 

\(a\)를 맨 뒤에서부터 차례로 \(b\)와 같게 만들어주자.

 

현재 \(a_i\)와 \(b_i\)가 같다면, 아무것도 하지 않는다.

그렇지 않다면, 연산을 통해 같게 만들어 준다.

현재 \(a_1\)과 \(a_i\)가 다르다면, \(a_1\)을 뒤집어 같게 만들어 준 다음,

\(i\)길이의 접두사를 뒤집으면 \(a_i\)와 \(b_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; }
 
int n;
string a, b;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n;
        cin >> a >> b;
 
        int st = 0, ed = n - 1;
        bool inv = false;
 
        vector <int> ans;
        for (int i = n - 1; i >= 0; i--)
        {
            if (!inv && a[ed] == b[i] || inv && a[ed] != b[i])
            {
                if (inv) ed++;
                else ed--;
                continue;
            }
 
            if (a[st] != a[ed])
            {
                ans.push_back(1);
                a[st] = a[ed];
            }
 
            ans.push_back(i + 1);
            inv = !inv;
            swap(st, ed);
 
            if (inv) ed++;
            else ed--;
        }
 
        cout << ans.size();
        for (int it : ans) cout << ' ' << it;
        cout << '\n';
    }
}

---

B - Unmerge

Problem - B - Codeforces

\(n\)길이의 배열 \(a,b\)가 있고, 이 배열 둘을 merge연산을 이용해 합쳐 만든 \(2n\)길이의 배열 \(p\)가 있다.

순열인 배열 \(p\)가 주어졌을 때, 위를 만족하는 배열 \(a,b\)가 존재하는지 알아내야 한다.

 

먼저 \(p\)를 앞에서부터 차례대로 봤을 때,

\(p_i\)와 현재 보고 있는 \(p_i\)보다 작으면서 뒤로 연속된 모든 원소들은 하나의 배열에 연속되도록 존재해야 함을 알 수 있다.

 

그러면 다음과 같은 DP를 정의할 수 있다.

\(DP(i, j)\) : 현재 \(p_i\)를 보고 있고, 지금까지 \(a\)에 \(j\)개의 원소를 넣었을 때, 위의 조건을 만족하는 두 배열 \(a,b\)을 만들 수 있는지 여부 (bool)

 

각각의 덩어리를 \(a\)에 넣을지 \(b\)에 넣을지만 정하면 되므로 각 상태마다 2개의 부분 문제만을 보면 되기 때문에,

\(O(n^2)\) DP로 해결할 수 있다.

 

#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 p[4001];
 
int dp[4001][4001];
int solve(int idx, int a)
{
    int& ret = dp[idx][a];
    if (ret != -1) return ret;
 
    if (idx == n)
    {
        if (a == n / 2) return ret = 1;
        else return ret = 0;
    }
 
    ret = 0;
 
    int ed = idx + 1;
    for (; ed < n; ed++)
    {
        if (p[idx] < p[ed]) break;
    }
 
    int sz = ed - idx;
 
    if (solve(ed, a + sz)) ret = 1;
    if (solve(ed, a)) ret = 1;
 
    return ret;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n; n *= 2;
        for (int i = 0; i < n; i++) cin >> p[i];
 
        for (int i = 0; i <= n; i++) for (int j = 0; j <= n; j++) dp[i][j] = -1;
 
        int res = solve(0, 0);
 
        if (res) cout << "YES\n";
        else cout << "NO\n";
    }
}

---

C - Mastermind

Problem - C - Codeforces

\(n\)길이의 배열 \(b\)가 주어진다. (\(1 \le b_i \le n+1\))

\(b\)와의 교집합의 크기가 \(y\)이고, 그 중 같은 인덱스에 있는 원소의 개수가 \(x\)인 \(n\)길이의 배열 \(a\)가 존재하는지 여부를 알아내고, 존재한다면 실해를 출력해야 한다.

 

먼저, \(a\)의 \(y-x\)개의 원소는 \(b\)에 존재하지만 서로 다른 인덱스에 존재해야 하는데, 이런 원소들은 종류가 다양할수록, 개수가 균일할수록 많은 원소의 위치를 서로 바꿀 수 있음을 알 수 있다.

 

따라서 남는 원소가 최대한 다양하고 균일하도록 \(x\)개의 원소를 정한다음, 남는 원소 중 \(y-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; }
 
const int N = 100010;
 
int n, x, y;
int b[N];
vector <int> cnt[N];
 
bool cmp(int a, int b)
{
    return cnt[a].size() > cnt[b].size();
}
 
struct ASDF
{
    int x, idx;
    bool operator <(ASDF t) const
    {
        if (cnt[x].size() != cnt[t.x].size())
            return cnt[x].size() > cnt[t.x].size();
        return x < t.x;
    }
};
 
int ans[N];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n >> x >> y;
        for (int i = 1; i <= n + 1; i++) cnt[i].clear();
        for (int i = 0; i < n; i++) ans[i] = -1;
 
        for (int i = 0; i < n; i++)
        {
            cin >> b[i];
            cnt[b[i]].push_back(i);
        }
 
        int notUsed = -1;
        vector <int> tmp;
        for (int i = 1; i <= n + 1; i++)
        {
            if (cnt[i].size() == 0) notUsed = i;
            tmp.push_back(i);
        }
 
        sort(tmp.begin(), tmp.end(), cmp);
 
        int rm = x;
 
        for (int i = 0; i < tmp.size() - 1 && rm > 0; i++)
        {
            while (cnt[tmp[i]].size() != cnt[tmp[i + 1]].size() && rm > 0)
            {
                for (int j = 0; j <= i && rm > 0; j++)
                {
                    int num = tmp[j];
                    int idx = cnt[num].back();
 
                    ans[idx] = num;
                    rm--;
 
                    cnt[num].pop_back();
                }
            }
        }
 
        vector <ASDF> vec;
 
        for (int i = 1; i <= n + 1; i++)
        {
            for (int idx : cnt[i])
            {
                vec.push_back({ i, idx });
            }
        }
 
        sort(vec.begin(), vec.end());
        multiset <ASDF> st(vec.begin(), vec.end());
 
        rm = y - x;
        for (auto it : vec)
        {
            int num = it.x;
            int idx = it.idx;
 
            if (st.empty()) break;
 
            auto nxt = st.upper_bound(it);
            if (nxt == st.end())
            {
                nxt = st.begin();
                if (num == nxt->x) continue;
            }
 
            int n2 = nxt->x;
            int i2 = nxt->idx;
 
            if (rm == 0) break;
            rm--;
 
            ans[idx] = n2;
            if (ans[i2] == -1) ans[i2] = notUsed;
 
            st.erase(nxt);
        }
 
        if (rm > 0)
        {
            cout << "NO\n";
            continue;
        }
 
        for (int i = 0; i < n; i++) if (ans[i] == -1) ans[i] = notUsed;
 
        cout << "YES\n";
        for (int i = 0; i < n; i++) cout << ans[i] << ' ';
        cout << '\n';
    }
}

---

D - The Majestic Brown Tree Snake

Problem - D - Codeforces

추가 예정

---

E - Origami

Problem - E - Codeforces

추가 예정