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

A - Permutation Forgery

Problem - A - Codeforces

어떤 순열 \(p\)에 대해 \(F(p)\)를 모든 인접한 원소의 합을 정렬한 배열이라고 정의하자.

\(n\)길이의 순열 \(p\)가 주어지면, \(F(p) = F(q)\)이면서 \(p \ne q\)인 \(n\)길이의 순열 \(q\)를 알아내야 한다.

 

\(p\)를 뒤집으면 된다.

 

#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[101];
 
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; i++) cin >> a[i];
        reverse(a, a + n);
        for (int i = 0; i < n; i++) cout << a[i] << ' ';
        cout << '\n';
    }
}

---

B - Array Cancellation

Problem - B - Codeforces

\(n\)길이의 배열 \(a\)가 주어진다. \(a\)의 모든 원소의 합은 0이다.

서로 다른 두 인덱스 \(i, j\)를 골라 \(a_i\)를 1 감소시키고, \(a_j\)를 1 증가시키는 연산을 할 수 있다.

\(i < j\)라면 비용이 들지 않지만, 그렇지 않다면 1의 비용이 든다.

 

배열의 모든 원소를 0으로 만들기 위한 최소 비용을 알아내야 한다.

 

맨 앞에 있는 원소부터 차례대로 0으로 만들자.

\(a_i\)가 0보다 크다면, 비용 없이 0으로 만듦과 동시에,

뒤에 0보다 작은 원소들에 1 증가시키는 연산을 \(a_i\)번 연산 할 수 있다. 이 횟수를 \(rm\)이라고 하자.

\(a_i\)가 0보다 작다면, 일단 최대 \(rm\)번 증가시키자. 그래도 0이 되지 않았다면, 비용을 내고 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;
ll a[100001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int T; cin >> T;
    while (T--)
    {
        cin >> n;
        ll rm = 0;
        ll ans = 0;
 
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
            if (a[i] < 0)
            {
                ll tmp = min(rm, -a[i]);
                rm -= tmp;
                a[i] += tmp;
                
                ans += -a[i];
            }
            else
            {
                rm += a[i];
            }
        }
        
        cout << ans << '\n';
    }
}

---

A - Balanced Bitstring

Problem - A - Codeforces

어떤 이진 문자열이 \(k\)의 길이를 가지고, 0이 \(\frac k2\)개, 1이 \(\frac k2\)개로 이루어져 있다면

이 문자열을 \(k\)-balanced하다고 하자.

 

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

이 문자열은 0,1,?으로 이루어져 있는데, ?에는 0,1 중 어떤 것이라도 들어갈 수 있다.

?에 적절히 문자를 채워넣음으로써 \(s\)를 \(k\)-balanced하게 만들 수 있는지 알아내야 한다.

 

관찰을 통해, \(s\)는 \(k\)의 주기를 가져야 함을 알 수 있다.

\(s\)를 주기가 \(k\)가 되도록 만들 수 있는지, 또 0, 1의 개수가 각각 \(\frac k2\)개가 되도록 만들 수 있는지 확인하면 된다.

 

#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;
string s;
 
int res[300001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int T; cin >> T;
    while (T--)
    {
        cin >> n >> k;
        cin >> s;
        for (int i = 0; i < n; i++) res[i] = -1;
 
        bool ans = true;
 
        for (int i = 0; i < n; i++)
        {
            if (res[i % k] == -1)
            {
                if (s[i] == '0') res[i % k] = 0;
                if (s[i] == '1') res[i % k] = 1;
            }
            else
            {
                if (s[i] == '0' && res[i % k] == 1
                    || s[i] == '1' && res[i % k] == 0)
                {
                    ans = false;
                    break;
                }
            }
        }
 
        int cnt[2] = { 0,0 };
        for (int i = 0; i < k; i++)
        {
            if (res[i] != -1) cnt[res[i]]++;
        }
 
        if (cnt[0] > k / 2 || cnt[1] > k / 2) ans = false;
 
        if (ans) cout << "YES\n";
        else cout << "NO\n";
    }
}

---

B - Tree Tag

Problem - B - Codeforces

\(n\)개의 정점으로 이루어진 트리가 주어진다.

두 사람이 이 트리에서 게임을 한다.

Alice는 \(a\)번 정점에서, Bob은 \(b\)번 정점에서 시작한다.

Alice는 현재 정점에서 거리가 \(da\)이하인 모든 정점까지 이동할 수 있고,

Bob은 현재 정점에서 거리가 \(db\)이하인 모든 정점까지 이동할 수 있다.

 

Alice가 먼저 시작하고, 차례로 트리에서 움직이게 된다.

움직이는 도중, 두 사람이 같은 위치에 있을 수 있다면 Alice가 승리하고, 영원히 만날 수 없다면 Bob이 승리한다.

 

이상적으로 플레이했을 때 승자를 알아내야 한다.

 

먼저, 트리의 지름을 \(d\)라고 했을 때, \(da\)와 \(db\)는 \(d\)보다 커질 수 없다.

관찰을 통해, \(2da \ge db\)면 Alice가 무조건 Bob을 잡을 수 있고, 그렇지 않다면 잡을 수 없다는 사실을 알 수 있다.

 

시작하자마자 Alice가 Bob을 잡는 예외만 잘 처리하면 된다.

 

#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, a, b, da, db;
vector <int> graph[100001];
 
int DFS(int v, int p, int d)
{
    if (v == b) return d;
    for (int nv : graph[v])
    {
        if (nv == p) continue;
        int res = DFS(nv, v, d + 1);
        if (res != -1) return res;
    }
 
    return -1;
}
 
void LEN(int v, int p, int d, int& rv, int& rd)
{
    if (d > rd)
    {
        rd = d;
        rv = v;
    }
 
    for (int nv : graph[v])
    {
        if (nv == p) continue;
        LEN(nv, v, d + 1, rv, rd);
    }
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int T; cin >> T;
    while (T--)
    {
        cin >> n >> a >> b >> da >> db;
        for (int i = 1; i <= n; i++) graph[i].clear();
        for (int i = 0; i < n - 1; i++)
        {
            int u, v; cin >> u >> v;
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
 
        int res = DFS(a, 0, 0);
        if (res <= da)
        {
            cout << "Alice\n";
            continue;
        }
 
        int rv = 1;
        int rd = 1;
        LEN(1, 0, 1, rv, rd);
 
        rd = 1;
        LEN(rv, 0, 1, rv, rd);
 
        da = min(da, rd - 1);
        db = min(db, rd - 1);
 
        if (da * 2 < db) cout << "Bob\n";
        else cout << "Alice\n";
    }
}

---

C - Fixed Point Removal

Problem - C - Codeforces

\(n\)길이의 배열 \(a\)가 주어진다.

이 배열의 인덱스 \(i\)에 대해, \(a_i = i\)라면 \(a_i\)를 배열에서 제거할 수 있다.

배열의 weight는 배열에서 제거할 수 있는 원소의 최대 개수를 뜻한다.

 

\(q\)개의 쿼리 \(x, y\)가 주어진다.

각 쿼리에 대해, \(a\)의 앞에서 \(x\)개, 뒤에서 \(y\)개를 제거한 부분 배열의 weight를 출력해야 한다.

 

 

먼저, 각 원소를 없앨 수 있는 최대 \(x\)를 저장하자. 이를 \(lmx\)라고 하자.

\(a_i\)를 삭제하기 위해서는 \(a_i\)보다 왼쪽에 있는 원소 중 최소 \(i - a_i\)개가 삭제 되어야 한다.

이를 구하는 방법에는 여러가지가 있는데, 본인은 레이지 세그트리를 이용했다.

 

그 다음 쿼리를 \(x\)의 비내림차순으로 정렬하여 오프라인으로 처리하자.

정렬한 쿼리를 차례대로 처리하면서, \(lmx\)가 \(x\)보다 작은 인덱스의 원소들은 삭제할 수 없도록 처리하면 된다.

오른쪽에서부터 삭제된 값들은 여기에 영향을 받지 않으므로 인덱스가 \(n-y\)보다 작은 원소에 대해서 삭제할 수 있는 최대 원소 개수를 구하면 된다.

 

#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 = 300001;
const int INF = 987654321;
 
int n, q;
int a[N];
 
vector <int> lmx[N];
 
int lazy[N * 4];
pii segTree[N * 4];
 
void build(int ptr, int l, int r)
{
    if (l == r)
    {
        segTree[ptr] = { 0, l };
        return;
    }
 
    build(ptr * 2, l, (l + r) / 2);
    build(ptr * 2 + 1, (l + r) / 2 + 1, r);
 
    segTree[ptr] = min(segTree[ptr * 2], segTree[ptr * 2 + 1]);
}
 
void setLazy(int ptr, int l, int r)
{
    int val = lazy[ptr]; lazy[ptr] = 0;
    segTree[ptr].first += val;
 
    if (l != r)
    {
        lazy[ptr * 2] += val;
        lazy[ptr * 2 + 1] += val;
    }
}
 
void update(int ptr, int l, int r, int i, int j, int val)
{
    if (lazy[ptr]) setLazy(ptr, l, r);
 
    if (j < l || r < i) return;
    if (i <= l && r <= j)
    {
        segTree[ptr].first += val;
 
        if (l != r)
        {
            lazy[ptr * 2] += val;
            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]);
}
 
pii getVal(int ptr, int l, int r, int i, int j)
{
    if (lazy[ptr]) setLazy(ptr, l, r);
 
    if (j < l || r < i) return { INF, 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 fwTree[N];
void fw_update(int i, int v)
{
    while (i <= n)
    {
        fwTree[i] += v;
        i += i & -i;
    }
}
 
int fw_getVal(int i)
{
    int res = 0;
    while (i)
    {
        res += fwTree[i];
        i -= i & -i;
    }
    return res;
}
 
vector <pair<pii, int> > query;
int ans[N];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
 
    build(1, 1, n);
 
    int removed = 0;
    for (int i = n; i >= 1; i--)
    {
        if (a[i] > i)
        {
            update(1, 1, n, i, i, INF);
            continue;
        }
 
        int rm = i - a[i];
        update(1, 1, n, i, i, rm);
 
        while (true)
        {
            pii res = getVal(1, 1, n, i, n);
 
            if (res.first > 0) break;
 
            int v = res.second;
            fw_update(v, 1);
            lmx[i - 1].push_back(v);
 
            update(1, 1, n, v, v, INF);
            update(1, 1, n, v + 1, n, -1);
        }
    }
 
    for (int i = 0; i < q; i++)
    {
        int x, y; cin >> x >> y;
        query.push_back({ {x,y},i });
    }
 
    sort(query.begin(), query.end());
 
    int cur = 0;
    for (auto qu : query)
    {
        int x = qu.first.first, y = qu.first.second;
        int idx = qu.second;
 
        while (cur < x)
        {
            for (int v : lmx[cur])
            {
                fw_update(v, -1);
            }
            cur++;
        }
 
        int res = fw_getVal(n - y);
        ans[idx] = res;
    }
 
    for (int i = 0; i < q; i++) cout << ans[i] << '\n';
}

---

D - Game of Pairs

Problem - D - Codeforces

추가 예정

---

E - Bricks

Problem - E - Codeforces

추가 예정