Codeforces Round #646 (Div. 2)

A - Odd Selection

Problem - A - Codeforces

길이 \(n\)인 배열 \(a\)가 있다.

여기에서 원소 \(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; }
 
int n, x;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n >> x;
 
        int odd = 0, even = 0;
        for (int i = 0; i < n; i++)
        {
            int a; cin >> a;
            if (a % 2) odd++;
            else even++;
        }
 
        if (x % 2 == 0)
        {
            if (even == 0)
            {
                cout << "No\n";
                continue;
            }
 
            even--;
            x--;
        }
 
        if (odd == 0)
        {
            cout << "No\n";
            continue;
        }
 
        int cnt = (odd - 1) / 2 + even / 2;
        if (cnt * 2 >= x - 1) cout << "Yes\n";
        else cout << "No\n";
    }
}

---

B - Subsequence Hate

Problem - B - Codeforces

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

이 문자열의 문자 하나를 뒤집는 연산을 할 수 있을 때, 문자열이 "010" 또는 "101"을 부분 부분 수열로 갖지 않도록 하는 최소 연산 횟수를 구해야 한다.

 

조건을 만족하기 위해서는 문자열이 0....1.... 또는 1....0.... 형태로 이루어져야 한다는 사실을 알 수 있다.

1의 개수의 부분합을 계산해 두면 모든 경우에 대해 뒤집어야 하는 문자의 수를 \(O(1)\)로 계산할 수 있으므로, \(O(n)\)에 문제를 해결할 수 있다.

 

시간제한이 넉넉하기 때문에 나이브한 \(O(n^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 main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        string s; cin >> s;
        int n = s.size();
 
        int ans = 987654321;
 
        int psum[1001];
        psum[0] = 0;
        for (int i = 0; i < n; i++)
        {
            psum[i + 1] = psum[i] + s[i] - '0';
        }
 
        for (int i = 0; i <= n; i++)
        {
            int r1 = psum[i];
            int r2 = psum[n] - psum[i];
 
            ans = min(ans, r1 + (n - i) - r2);
            ans = min(ans, i - r1 + r2);
        }
 
        cout << ans << '\n';
    }
}

---

C - Game On Leaves

Problem - C - Codeforces

\(n\)개의 노드로 이루어진 트리가 주어진다.

두 플레이어가 게임을 하는데, 각 차례에 플레이어는 아무 리프 노드를 선택해 삭제할 수 있다.

 

\(x\)번 노드를 삭제하는 사람이 승리한다고 할 때, 두 플레이어가 모두 이상적으로 플레이했을 때 승자를 알아내야 한다.

 

먼저, \(x\)번 노드가 이미 리프노드라면, 처음 시작하는 사람이 승리한다.

 

그렇지 않다면, \(x\)에 2개의 간선이 연결된 3개의 노드로 이루어진 트리를 먼저 만드는 사람이 승리함을 알 수 있다.

이 형태가 되기 전까지는 어떻게 진행하든 결과에 변함이 없다.

 

따라서 노드의 수가 짝수면 처음 시작하는 사람이, 그렇지 않다면 뒤에 시작하는 사람이 승리한다.

 

#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, x; cin >> n >> x;
        int cnt = 0;
        for (int i = 0; i < n - 1; i++)
        {
            int u, v; cin >> u >> v;
            if (u == x || v == x) cnt++;
        }
 
        if (cnt <= 1)
        {
            cout << "Ayush\n";
            continue;
        }
 
        if (n % 2) cout << "Ashish\n";
        else cout << "Ayush\n";
    }
}

---

D - Guess The Maximums

Problem - D - Codeforces

\(k\)개의 원소로 이루어진 비밀번호를 알아내야 한다.

 

비밀번호는 \(n\) 길이의 숨겨진 배열 \(A\)와 서로 서로소인 \(k\)개의 집합의 배열 \(S\)로 만들어 내는데,

각 비밀번호의 자리 \(k_i\)는 구간 \([1,n]\)내에서 \(S_i\)에 속하지 않는 모든 \(j\)에 대해, \(A_j\)의 최대값으로 정해진다.

 

\(A\)를 알아내기 위해, 임의의 인덱스들을 입력으로 주면 그 인덱스에 저장된 값 중 최대값을 출력하는 쿼리를 최대 12번 사용할 수 있을 때, 원래 비밀번호를 복원해 내야 한다.

 

배열 \(A\) 전체의 최대값을 \(mx\)라고 하고, 그 인덱스를 \(i\)라고 하자.

\(S\)에 속한 집합 중 \(i\)를 포함하지 않는 집합 \(S_j\)에 대해, \(j\)번째 비밀번호는 무조건 \(mx\)임을 알 수 있다.

 

한 번의 쿼리로 \(mx\)를 알아내고, 이분 탐색을 이용해 \(i\)를 알아낸 다음, (최대 10쿼리)

\(i\)를 포함하는 \(S_k\) (없을 수도 있다)에 속하지 않는 모든 \(j\)에 대해 \(A_j\)의 최대값을 한 번의 쿼리로 알아내면 된다.

 

#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, k;
vector <vector <int> > s;
 
int main()
{
    int t; cin >> t;
    while (t--)
    {
        cin >> n >> k;
        s.clear();
        s.resize(k);
 
        for (int i = 0; i < k; i++)
        {
            int sz; cin >> sz;
            s[i].resize(sz);
            for (int j = 0; j < sz; j++) cin >> s[i][j];
        }
 
        cout << "? " << n;
        for (int i = 1; i <= n; i++) cout << " " << i;
        cout << endl;
 
        int mx; cin >> mx;
        
        int l = 0, r = k - 1;
 
        while (l < r)
        {
            int m = (l + r) / 2;
 
            vector <int> tmp;
            for (int i = l; i <= m; i++)
            {
                for (auto x : s[i]) tmp.push_back(x);
            }
 
            cout << "? " << tmp.size();
            for (auto x : tmp) cout << " " << x;
            cout << endl;
 
            int res; cin >> res;
 
            if (res == mx) r = m;
            else l = m + 1;
        }
 
        bool isExist[1001] = { 0, };
        for (auto x : s[l]) isExist[x] = 1;
 
        cout << "? " << n - s[l].size();
        for (int i = 1; i <= n; i++) if (!isExist[i]) cout << " " << i;
        cout << endl;
 
        int res; cin >> res;
 
        cout << "!";
        for (int i = 0; i < k; i++)
        {
            cout << " ";
            if (i == l) cout << res;
            else cout << mx;
        }
        cout << endl;
 
        string isOk; cin >> isOk;
 
        if (isOk != "Correct") return 0;
    }
}

---

E - Tree Shuffling

Problem - E - Codeforces

루트가 1이고 \(n\)개의 노드로 이루어진 트리가 있다.

\(i\)번째 노드는 \(a_i\)의 비용을 가지며, \(b_i\) (0 or 1)가 쓰여져 있다. 이를 \(c_i\)가 쓰여져 있도록 바꾸려고 한다.

 

모든 노드에 대해 \(c_i\)가 쓰여져 있도록 바꾸기 위해, 다음과 같은 연산을 할 수 있다.

어떤 노드 \(u\)의 서브트리에 포함되는 노드 중 \(k\)개를 골라 원하는 대로 수를 바꾼다. 이 때, \(k \cdots a_u\)의 비용이 든다.

 

조건을 만족하도록 연산을 했을 때 최소 비용을 알아내야 한다.

 

우선 관찰을 통해 \(a_i\)가 작은 순으로 처리하는 것이 무조건 유리하다는 사실을 알 수 있다.

현재 처리하고 있는 노드가 \(u\)일 때, \(u\)의 서브트리에서 0을 1로 바꿔야 하는 노드의 수를 \(n_0\), 1을 0으로 바꿔야 하는 노드의 수를 \(n_1\)이라고 하자.

 

최대한 많은 노드를 \(c_i\)로 바꿔 주는 것이 이득이기 때문에, \(2a_u\times min(n_0, n_1)\)의 비용을 사용해 \(2 \times min(n_0, n_1)\)개의 노드를 처리해 주면 된다.

 

그 후에 아직 \(c_i\)가 쓰여져 있지 않은 노드들이 있을 수 있는데, 이는 \(u\)의 서브트리에 있는 노드로는 해결할 수 없기 때문에 \(u\)의 부모 노드를 처리할 때까지 무시하면 된다.

 

불가능할 때의 예외처리를 잊지 말자.

 

#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 = 200001;
const int INF = 987654321;
 
int n;
ll a[N];
int b[N];
int c[N];
 
vector <int> graph[N];
int child[N][2];
 
int DFS_cnt = 0;
int DFS_num[N];
void DFS(int v, int p)
{
    DFS_num[v] = ++DFS_cnt;
    child[v][0] = DFS_cnt;
 
    for (int nv : graph[v])
    {
        if (nv == p) continue;
        DFS(nv, v);
    }
 
    child[v][1] = DFS_cnt;
}
 
int cnt0[N];
int cnt1[N];
int valid[N];
 
void fw_update(int* segTree, int i, int x)
{
    while (i <= n)
    {
        segTree[i] += x;
        i += i & -i;
    }
}
 
int fw_getVal(int* segTree, int i)
{
    int res = 0;
    while (i)
    {
        res += segTree[i];
        i -= i & -i;
    }
 
    return res;
}
 
int fw_getVal(int* segTree, int i, int j)
{
    return fw_getVal(segTree, j) - fw_getVal(segTree, i - 1);
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n;
 
    int sumb = 0, sumc = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i] >> b[i] >> c[i];
        sumb += b[i], sumc += c[i];
    }
 
    for (int i = 0; i < n - 1; i++)
    {
        int u, v; cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
 
    if (sumb != sumc)
    {
        cout << -1;
        return 0;
    }
 
    DFS(1, 0);
 
    priority_queue <pll> pq;
    for (int i = 1; i <= n; i++)
    {
        pq.push({ -a[i], i });
 
        if (b[i] != c[i])
        {
            if (b[i] == 0)
                fw_update(cnt0, DFS_num[i], 1);
            else
                fw_update(cnt1, DFS_num[i], 1);
        }
    }
 
    ll ans = 0;
    while (!pq.empty())
    {
        ll cost = -pq.top().first;
        int v = pq.top().second;
        pq.pop();
 
        if (fw_getVal(valid, DFS_num[v])) continue;
 
        int res0 = fw_getVal(cnt0, child[v][0], child[v][1]);
        int res1 = fw_getVal(cnt1, child[v][0], child[v][1]);
 
        int res = min(res0, res1);
 
        ans += cost * res * 2;
        fw_update(cnt0, DFS_num[v], -res);
        fw_update(cnt1, DFS_num[v], -res);
 
        fw_update(valid, child[v][0], 1);
        fw_update(valid, child[v][1] + 1, -1);
    }
 
    cout << ans;
}

---

F - Rotating Substrings

Problem - F - Codeforces

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

 

\(s\)에 \(s\)의 부분 문자열 \(s[l, r]\)을 선택해 시계방향으로 회전하는 연산을 해서 \(t\)로 만드려고 한다.

 

이 때 최소 연산 횟수를 구해야 한다.

 

우선 \(s\)와 \(t\)의 알파벳 개수가 서로 다르다면 불가능하고, 그렇지 않다면 무조건 가능함을 알 수 있다.

 

다음과 같은 DP식을 정의하자.

\(DP(i,j)\) : s의 부분 문자열 \(s[1,i]\)을 t의 부분 문자열 \(t[1,j]\)로 만드는데 필요한 최소 연산의 수

 

각 상황에 대해, \(s[i]\)를 \(t[j]\)로 만드는 것을 목표라고 생각해 보자.

그러면 다음과 같은 경우로 나눌 수 있다.

 

1. \(s[i]\)를 현재 사용하지 않고, 다음에 회전 연산을 통해 앞으로 끌어오도록 한다 : \(DP(i-1,j) + 1\)

2. \(s[i] = t[j]\)라면 : \(DP(i-1,j-1)\)

3. \(s[i,n]\)에 다음에 앞으로 끌어오도록 처리한 문자 \(t[j]\)가 존재한다면, 지금 끌어온다 : \(DP(i, j-1)\)

 

이 중 최소값이 답이 된다.

각 상황을 계산하는데 최대 3번의 연산만 필요하므로, \(O(n^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; }
 
const int INF = 987654321;
 
int n;
string s, t;
 
int ps1[26][2001];
int ps2[26][2001];
 
int dp[2001][2001];
int solve(int i, int j)
{
    if (i == 0) return 0;
    int& ret = dp[i][j];
    if (ret != -1) return ret;
 
    ret = solve(i - 1, j) + 1;
 
    if (s[i - 1] == t[j - 1])
        ret = min(ret, solve(i - 1, j - 1));
 
    int idx = t[j - 1] - 'a';
    int s1 = ps1[idx][n] - ps1[idx][i];
    int s2 = ps2[idx][n] - ps2[idx][j];
 
    if (s1 > s2)
        ret = min(ret, solve(i, j - 1));
 
    return ret;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int T; cin >> T;
    while (T--)
    {
        cin >> n;
        cin >> s >> t;
 
        int cnt[2][26] = { 0, };
        for (int i = 0; i < n; i++)
        {
            cnt[0][s[i] - 'a']++;
            cnt[1][t[i] - 'a']++;
        }
 
        bool flag = false;
        for (int i = 0; i < 26; i++)
        {
            if (cnt[0][i] != cnt[1][i])
            {
                flag = true;
                break;
            }
        }
 
        if (flag)
        {
            cout << "-1\n";
            continue;
        }
        
        for (int i = 0; i <= n; i++) for (int j = 0; j <= n; j++)
            dp[i][j] = -1;
 
        int s1[26] = { 0, };
        int s2[26] = { 0, };
 
        for (int i = 0; i < n; i++)
        {
            s1[s[i] - 'a']++;
            s2[t[i] - 'a']++;
 
            for (int j = 0; j < 26; j++)
            {
                ps1[j][i + 1] = s1[j];
                ps2[j][i + 1] = s2[j];
            }
        }
 
        cout << solve(n, n) << '\n';
    }
}