Codeforces #819

A. Mainak and Array

길이 $n$의 배열 $a$가 주어진다.

배열의 $[l,r]$ 구간을 선택, 원하는만큼 cyclically rotate하는 연산을 한 번 수행하여 얻을 수 있는 $a_n-a_1$의 최댓값을 구하는 문제이다.

 

다음과 같이 경우를 나눌 수 있다.

1) $a_1,a_n$ 미포함: $ans=a_n-a_1$

2) $a_1$만 미포함: $ans=max(a_2,a_3,...,a_n)-a_1$

3) $a_n$만 미포함: $ans=a_n-min(a_1,a_2,...,a_{n-1})$

4) $a_1,a_n$을 모두 포함: $ans=ma{x}_{1\le i\le n}(a_{i-1}-a_i)$ (단, $a_0=a_n$)

 

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tp;
 
int main(void) {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
 
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        vector<int> a(n+1);
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        a[0] = a[n];
 
        int ans = a[n] - a[1];
        for (int i = 2; i <= n; i++) {
            ans = max(ans, a[i] - a[1]);
        }
        for (int i = 1; i <= n-1; i++) {
            ans = max(ans, a[n] - a[i]);
        }
        for (int i = 1; i <= n; i++) {
            ans = max(ans, a[i-1] - a[i]);
        }
        cout << ans << '\n';
    }
    return 0;
}

 

B. Mainak and Interesting Sequence

$a$와 $p$는 길이가 $n$인 배열이다.

 

배열 $p$의 원소 $p_i$의 값은 다음과 같이 정의된다.

$p_i=\text{the bitwise XOR of all elements in}$ $a$ $\text{which are strictly less than }{a}_i$

 

배열 $p$의 모든 원소가 0일 때 배열 $a$를 interesting하다고 한다.

$a_1+a_2+...+a_n=m$을 만족하는 interesting한 배열 $a$를 찾는 문제이다. 단, $a_i>0$이다.

 

배열 $a$에서 가장 작은 원소를 $x$, 그 다음 작은 원소를 $y$, 그 다음 작은 원소를 $z$, ...라고 하자.

$x$는 배열 $a$ 안에 반드시 짝수개 존재해야 한다.

만약 홀수개 존재한다면 $y$ 입장에서 봤을 때 $p$의 원소가 0이 아니게 된다.

$y$도 반드시 짝수개 존재해야 한다.

$x$를 모두 XOR한 값이 0이므로 $y$가 홀수개 존재하면 $z$ 입장에서 $p$의 원소가 0이 아니게 된다.

같은 이유로 $z$, ...도 각각 짝수개 존재해야 한다.

단, 가장 큰 원소는 홀짝 개수 제한이 없다.

 

다음과 같이 경우를 나눌 수 있다.

1) $n>m$: NO

2) $n$이 홀수: 1, 1, ..., 1, 1, $m-n+1$

3) $n$이 짝수:

  3-1) $m$이 짝수: 1, 1, ..., 1, $\frac{m-n+2}{2}$, $\frac{m-n+2}{2}$

  3-2) $m$이 홀수: NO

 

3-2 증명

$n$이 짝수, $m$이 홀수이면서 조건을 만족하는 배열 $a$가 존재한다고 가정하자.

$m$이 홀수이므로, 배열 $a$에는 어떤 홀수 $x$가 홀수개 존재해야 한다.

그런데 $n$이 짝수이므로 배열 $a$에 어떤 수 $y$가 홀수개 존재한다. ($y\ne x$)

(위에서 증명한 정리에 의해) 이러한 배열은 존재할 수 없으므로 가정에 모순된다.

 

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tp;
 
int main(void) {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
 
    int t; cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        
        if (n > m) {
            cout << "No\n";
        }
        else {
            if (n % 2) {
                cout << "Yes\n";
                for (int i = 0; i < n-1; i++) {
                    cout << 1 << ' ';
                }
                cout << m - n + 1 << '\n';
            }
            else {
                if (m % 2) {
                    cout << "No\n";
                }
                else {
                    cout << "Yes\n";
                    for (int i = 0; i < n-2; i++) {
                        cout << 1 << ' ';
                    }
                    cout << (m - n + 2) / 2 << ' ';
                    cout << (m - n + 2) / 2 << '\n';
                }
            }
        }
    }
    return 0;
}

 

C. Jatayu's Balanced Bracket Sequence

길이가 $2n$인 balanced bracket sequence $s$가 주어진다.

$1\le i<j\le 2n$인 모든 $i,j$에 대해, $s[i...j]$가 balanced bracket sequence이면 $i$와 $j$를 잇는 간선을 그래프에 추가한다.

간선은 양방향이며 가중치가 붙지 않는다.

위 과정을 거쳐 만들어진 그래프의 component 개수를 구하는 문제이다.

 

$i,j$가 같은 component에 속하려면 다음 두 가지 조건을 만족해야 한다.

1) $s[i],s[j]$의 괄호 깊이가 같다.

2) $i$와 $j$ 사이에 깊이가 더 낮은 괄호가 존재하지 않는다.

 

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tp;
 
int main(void) {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
 
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        string s; cin >> s;
        stack<int> st;
        vector<int> a;
        for (char ch: s) {
            if (ch == '(') {
                st.push(1);
                a.push_back(st.size());
            }
            else {
                st.pop();
            }
        }
        int ans = 1;
        for (int i = 1; i < (int)a.size(); i++) {
            if (a[i] > a[i-1]) ans++;
        }
        cout << ans << '\n';
    }
    return 0;
}

 

D. Edge Split

$n$개의 정점과 $m$개의 간선으로 구성된 무방향, 가중치 없는 연결 그래프가 주어진다.

각 간선을 빨간색 또는 파란색 중 하나로 칠한다.

빨간 간선만 고려했을 때 component의 개수를 $c_1$, 파란 간선만 고려했을 때 component의 개수를 $c_2$라고 하자.

$c_1+c_2$의 최솟값을 구하는 문제이다.

 

$m\le n+2$ 조건이 눈에 띈다. 스패닝 트리 느낌이 난다.

빨간 간선으로만 이뤄진 그래프를 $R$, 파란 간선으로만 이뤄진 그래프를 $B$라고 하자.

WLOG, $R$이 스패닝 트리일 때 정답이 되지 않을까? 정말 그런지 증명해보자.

 

증명

1. $R$에 cycle이 존재하는 경우

cycle에 포함된 어떤 간선 $e$를 $R$에서 $B$로 옮긴다.

이때 $c_1$은 변하지 않고 $c_2$는 최대 1만큼 감소한다.

 

2. $R$이 두 개 이상의 component로 구성된 경우

$R$의 서로 다른 component에 속해 있는 두 정점 $u,v$를 잇는 간선을 $B$에서 $R$로 옮긴다.

이때 $c_1$은 1만큼 감소하고 $c_2$는 최대 1만큼 증가한다.

 

$\therefore$ 두 행동 모두 최적해를 악화시키지 않는다는 것을 알 수 있다.

 

$R$을 스패닝 트리로 만들었으므로 $c_1=1$이다.

이제 $c_2$를 최소화해야 하는데, 남은 간선의 개수는 최소 0개에서 최대 3개이다.

$B$에 cycle이 생기는 경우만 조심하면 된다.

 

$B$에 포함된 간선이 $u-v,v-w,w-u$라고 하자.

DFS spanning tree에 포함된 간선은 tree edge와 back edge로 나뉜다.

따라서, WLOG, $u,v$가 $w$의 조상이다.

$w$의 부모를 $p$라고 하자.

$B$의 $v-w$와 $R$의 $w-p$를 교환함으로써 문제를 해결할 수 있다.

 

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tp;
 
int n, m;
vector<int> par;
vector<int> depth;
vector<vector<pii> > adj;
vector<int> ans;
 
void dfs(int u, int p, int d) {
    par[u] = p;
    depth[u] = d;
    for (auto [v, idx]: adj[u]) {
        if (v != p && depth[v] == -1) {
            dfs(v, u, d+1);
            ans[idx] = 1;
        }
    }
}
 
int main(void) {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
 
    int t; cin >> t;
    while (t--) {
        cin >> n >> m;
        par.clear(); par.resize(n+1);
        depth.clear(); depth.resize(n+1, -1);
        adj.clear(); adj.resize(n+1);
        ans.clear(); ans.resize(m);
 
        for (int i = 0; i < m; i++) {
            int u, v;
            cin >> u >> v;
            adj[u].push_back({v, i});
            adj[v].push_back({u, i});
        }
 
        dfs(1, 0, 0);
 
        if (m == n + 2) {
            vector<int> vertex;
            for (int i = 1; i <= n; i++) {
                for (auto [j, idx]: adj[i]) {
                    if (ans[idx] == 0) {
                        vertex.push_back(i);
                        vertex.push_back(j);
                    }
                }
            }
            sort(all(vertex));
            vertex.erase(unique(all(vertex)), vertex.end());
 
            if (vertex.size() == 3) {
                int w = vertex[0];
                int v = vertex[1];
                if (depth[w] < depth[v]) swap(w, v);
 
                int idx1, idx2;
                for (auto [i, idx]: adj[w]) {
                    if (i == v) idx1 = idx;
                    if (i == par[w]) idx2 = idx;
                }
                swap(ans[idx1], ans[idx2]);
            }
        }
 
        for (int i: ans) {
            cout << i;
        }
        cout << '\n';
    }
    return 0;
}