SCPC 2021 1차 예선 풀이

대충 1시간 30분 정도 쓴 것 같다.

 

1번. 친구들

친구 관계가 일부 주어졌고, 친구의 친구 역시 친구로 간주할 때 "친구 관계인 maximal 그룹"의 개수를 구하는 문제다.

이는 사람을 정점으로, 친구 관계를 간선으로 볼 때 연결 컴포넌트의 개수를 구하는 문제와 같다. disjoint set 자료구조로 쉽게 해결할 수 있다.

 

#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ldb;
const ll mod = 1e9 + 7;
 
int n;
int d[111111];
int par[111111];
 
int find(int x)
{
    if(par[x] == x) return x;
    return par[x] = find(par[x]);
}
 
void unite(int u, int v)
{
    u = find(u);
    v = find(v);
    if(u == v) return;
    par[u] = v;
}
 
void solve(void)
{
    int i, ans = 0; cin >> n;
    for(i=1 ; i<=n ; i++) cin >> d[i];
    for(i=1 ; i<=n ; i++) par[i] = i;
    for(i=1 ; i<=n ; i++)
        if(i+d[i]<=n) unite(i, i+d[i]);
    for(i=1 ; i<=n ; i++) if(i == find(i)) ans++;
    cout << ans;
}
 
int main(void)
{
    fio; int tc; cin >> tc;
    for(int i=1 ; i<=tc ; i++) 
    {
        cout << "Case #" << i << endl;
        solve(); cout << endl;
    }
    return 0;
}

 

2번. 이진수

$b_i = a_{i-t} | a_{i+t}$로 정의된 bit string $b$가 주어졌을 때, 사전순으로 가장 앞선 $a$를 구하는 문제다.

단, index가 가능한 범위 밖인 경우 값은 $0$이라고 생각하도록 한다. 또한, 조건을 만족하는 $a$가 존재함은 보장된다. 

 

먼저 $b_i = 0$이면 $a_{i-t} = a_{i+t} = 0$임이 강제되며, 이렇게 둘 경우 $b_i = 0$ 역시 만족함을 알 수 있다. 

이에 해당되는 $a$의 bit에 0을 넣는 것을 확정하고 나면, 이제 $b_i = 1$ 형태의 조건들만 남았다. 

이들은 결국 $a$의 두 bit 중 적어도 하나가 1이라는 의미고, 이는 직관적으로 봤을 때 1을 더 넣으면 넣을수록 만족하기 쉬운 조건이다.

그러니, 앞서 0으로 확정된 bit가 아닌 임의의 bit에 대해서는 그냥 1로 두면 조건을 만족하는 $a$가 될 것이다.

 

이제 문제는 사전순으로 가장 앞선 $a$를 구하는 건데, 이런 문제가 그렇듯 앞부터 보면서 0을 넣을 수 있는지 판별하면 된다.

$a_i = 0$이 가능한지 고려해보자. 먼저 $a_i = 0$이 앞서 확정되었다면 굳이 고려를 할 필요도 없다.

만약 $i-t$가 범위에 있고 $b_{i-t} = 1$이라면, $a_{i-2t}$ 또는 $a_i$가 $1$이 되어야 한다. $a_{i-2t}=0$이라면, 여기서 $a_i = 1$이 강제된다. 

만약 $i+t$가 범위에 있고 $b_{i+t}=1$이라면, $a_i$ 또는 $a_{i+2t}$가 $1$이 되어야 한다. $a_{i+2t}$가 이미 $0$으로 확정되었다면, 여기서 $a_i = 1$이 강제된다.

이를 제외한 경우에서는, $a_i = 0$을 해도 문제가 되지 않는다. $a_i$가 영향을 주는 $b$의 값은 $b_{i-t}$, $b_{i+t}$이며, 이들의 값을 $a_i = 0$으로 두면서도 정확하게 맞춰줄 수 있기 때문이다. 특히, 마음에 걸릴 수 있는 유일한 부분이 $a_i = 0$으로 두면서 후에 $a_{i+2t}$를 $1$로 둔 것인데, 애초에

• $a_i = 1$로 두면 무조건 $a_i = 0$으로 두는 것보다 사전순으로 뒤고, 그러니 $a_i = 0$인게 이득이고
• $a_{i+2t}$는 확정되지 않은 bit이므로 $a_{i+2t} = 1$으로 두었다고 해서 조건을 만족하는 게 "어려워지지 않는다"

애초에 이 경우에는 $a_i = 0$으로 두고 확정된 bit를 제외한 뒤의 모든 bit를 1로 두면 조건을 만족하게 되어있다.

어쨌든 이런 식으로 bit를 계산하면 $\mathcal{O}(n)$에 모든 계산을 할 수 있다. 2번 문제인 것 치고는 약간 까다로웠다. 

 

#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ldb;
const ll mod = 1e9 + 7;
 
// b[i] = a[i-t] | a[i+t]
 
int n, t, a[55555], b[55555];
string s;
 
void solve(void)
{
    int i; cin >> n >> t >> s;
    for(i=1 ; i<=n ; i++) b[i] = s[i-1] - '0';
    for(i=1 ; i<=n ; i++) a[i] = -1;
    for(i=1 ; i<=n ; i++)
    {
        if(b[i] == 0)
        {
            if(i+t<=n) a[i+t] = 0;
            if(i-t>=1) a[i-t] = 0;
        }
    }
    for(i=1 ; i<=n ; i++)
    {
        if(a[i] != -1) continue;
        if(i-t>=1 && (i<=2*t || a[i-2*t] == 0)) a[i] = 1;
        else if(i+t<=n && (i+2*t>n || a[i+2*t]==0)) a[i] = 1;
        else a[i] = 0;
    }
    for(i=1 ; i<=n ; i++) cout << a[i];
}
 
int main(void)
{
    fio; int tc; cin >> tc;
    for(int i=1 ; i<=tc ; i++) 
    {
        cout << "Case #" << i << endl;
        solve(); cout << endl;
    }
    return 0;
}

 

3번. No Cycle

사이클이 생기지 않도록 간선의 방향을 결정하는데, 사전순 조건이 있다. 즉, 앞쪽에서 입력받은 간선들은 최대한 입력받은 순서를 유지하도록 해야한다. 

이 문제 역시 사전순 문제에서 항상 등장하는 방법인, 앞부터 보면서 답을 맞춰나가는 방법을 사용한다. 결국 우리가 풀어야하는 문제는 

• 방향 그래프 $G$와 지금 당장 방향을 정해야 하는 간선 $e$, 그리고 뒤에 추가할 무방향 간선의 배열 $E$가 주어져있다.
• $e$를 입력받은 순서로 방향을 줄 때, $E$의 간선들의 방향을 잘 설정하여 $e, E$를 전부 추가한 뒤에도 그래프에 사이클이 없도록 할 수 있는가? 

이 문제를 해결할 수 있다면, 본 문제 역시 위 문제를 각 간선에 대하여 해결하는 것을 반복하여 해결할 수 있다.

즉, 입력으로 방향 그래프 $G$와 무방향 간선 $e_1, e_2, \cdots, e_k$가 들어온다면,

• $G, e_1, [e_2, \cdots, e_k]$에 대해 문제를 해결. 그 후 결정된 방향에 맞게 $G_1 \gets G + \vec{e_1}$.
• $G_1, e_2, [e_3, \cdots , e_k]$에 대해 문제를 해결. 그 후 결정된 방향에 맞게 $G_2 \gets G + \vec{e_2}$.
• 반복하면서 최종적으로 $G_{k-1}, e_k, []$에 대하여 문제를 해결하는 것으로 마무리.

물론, 위 과정에서 각 간선은 그리디하게 가능하면 입력 순서대로 방향을 잡아야 한다. 

 

Claim : $G$가 DAG고, $E$가 추가할 무방향 간선들이라고 하자. $E$의 간선들의 방향을 잘 정하여 $E$를 추가한 뒤에도 $G$가 DAG이도록 할 수 있다.

Proof of Claim : $G$를 위상정렬하고, 위상정렬 순서로 방향을 주면 된다. 증명 끝.

 

결국 위에서 논의한 $G, e, E$에 대한 문제는 사실 $G + e$가 DAG인지, 즉 사이클이 없는지 판별하는 문제와 같다.

$G$ 역시 DAG이므로, $G + e$에 사이클이 있는지 판별하는 문제는 $G$에 특정 경로가 존재하는지 판별하는 문제와 같다.

즉, $e$가 $u$에서 $v$로 가는 간선이라면, $G + e$의 사이클 존재 유무는 $G$에서 $v$에서 $u$로 가는 경로의 존재 여부와 같다.

 

결론적으로, 간선 $u \rightarrow v$가 주어졌다면 현재 그래프에서 $v \rightarrow u$ 경로가 존재하는지 보고,

• 존재한다면 순서를 뒤집어서 $v \rightarrow u$로 두고 이 간선을 그래프에 추가
• 그렇지 않다면 순서를 그대로 두고 간선을 그래프에 추가

하는 것을 반복하면 된다. 대충 $\mathcal{O}(K(N+M+K))$ 정도에 돌 것이다. 아마 자료구조 빡세게 쓰면 subquadratic 될듯? 아니면 말고

 

#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ldb;
const ll mod = 1e9 + 7;
 
vector<int> edge[511];
pair<int, int> E[4333];
queue<int> Q;
int vis[555];
int n, m, k;
 
int work(int u, int v)
{
    int i; for(i=1 ; i<=n ; i++) vis[i] = 0;
    vis[v] = 1; Q.push(v); 
    while(!Q.empty())
    {
        int c = Q.front(); Q.pop();
        for(i=0 ; i<edge[c].size() ; i++)
        {
            if(vis[edge[c][i]] == 0)
            {
                vis[edge[c][i]] = 1;
                Q.push(edge[c][i]);
            }
        }
    }
    if(vis[u]) return 1;
    return 0;
}
 
void solve(void)
{
    int i, u, v;
    cin >> n >> m >> k;
    for(i=1 ; i<=n ; i++) edge[i].clear();
    for(i=1 ; i<=m ; i++)
    {
        cin >> u >> v;
        edge[u].push_back(v);
    }
    for(i=1 ; i<=k ; i++)
    {
        cin >> u >> v;
        E[i] = make_pair(u, v);
    }
    for(i=1 ; i<=k ; i++)
    {
        u = E[i].first;
        v = E[i].second;
        int res = work(u, v);
        cout << res;
        if(res == 0) edge[u].push_back(v);
        else edge[v].push_back(u);
    }
}
 
 
int main(void)
{
    fio; int tc; cin >> tc;
    for(int i=1 ; i<=tc ; i++) 
    {
        cout << "Case #" << i << endl;
        solve(); cout << endl;
    }
    return 0;
}

 

4번. 예약 시스템

$2 \times m$ 직사각형에 사람들을 배치한다. 사람들은 총 $n$개의 그룹으로 나뉘어 있으며, 각 그룹에는 5명 이상이 있다. 

각 사람들은 스트레스 지수 $w$를 갖는데, 자신의 이웃에 자신과 다른 그룹에 속하는 사람이 있다면 그런 사람의 수와 $w$의 곱만큼 스트레스가 오른다.

우리의 목표는 스트레스 지수의 총합을 최소화하는 것이다. 제한은 전체적으로 큰 편이다. 

 

동적계획법을 쓰기 어렵게 생긴 제한인만큼, 한방에 문제를 푸는 방법이 필요해보인다. 

 

그룹 $S$ 하나를 고정해보자. $S$의 사람들이 스트레스를 느낄 때는, $S$와 $S^C$가 한 변을 공유할 때다.

그러니까 $S$의 둘레의 (단, 직사각형의 둘레는 제외한다) 길이가 길면 길수록 $S$ 전체의 스트레스가 커진다.

이는 $S$의 사람들이 뭉쳐있어야 스트레스가 적을 것 같다는 직관과도 거의 같은 결과다. 

 

"$S$의 둘레"를 생각해보면, 전체 직사각형의 길이 2의 세로변을 잠깐 무시하고 생각해보면

• $S$의 크기가 짝수인 경우, 직사각형 형태를 이루도록 하면 둘레가 4가 된다.
• 특히, 이 경우 $S$에서 서로 다른 4명의 사람들이 정확히 $S^C$의 한 사람과 만나게 된다. 이 사람들은 스트레스 지수가 작을수록 좋다.
• $S$의 크기가 홀수인 경우, 직사각형에 하나 튀어나온 형태를 만들면 둘레가 5가 된다.
• 특히, 이 경우 $S$에서 서로 다른 4명의 사람들이 $S^C$의 사람과 만나게 된다. 4명 중 정확히 한 명은 $S^C$를 두 명 만나고, 나머지는 한 명 만난다.
• 물론, 두 명 만나는 사람의 스트레스 지수가 가장 작아야하며, 나머지의 스트레스 지수 역시 작을수록 좋다.

그리고 조금 열심히 생각해보면 이게 진짜 최적임을 납득할 수 있다. 또한, 홀수 크기의 그룹이 짝수개 존재하므로, 홀수 크기의 그룹끼리 서로 맞닿아 직사각형을 이루도록 하면 배치 역시 어렵지 않다. 이제 문제는 길이 2의 세로변을 처리하는 것이다. 길이 2의 세로변에 걸쳐서 $S$를 배치한다면, $S$에서 스트레스를 받는 4명 중 2명은 (이들은 4명 중에서 스트레스가 많은 두 명일 것이다) 전체 직사각형의 세로변의 도움을 받아 스트레스를 받지 않아도 된다. 

 

단순하게 생각하면, 여기서도 "가장 이득을 보는 그룹"을 양쪽 끝에 배치하여 세로변의 도움을 받을 수 있도록 하면 된다.

그런데 이게 이렇게 단순하지는 않은 게, 배치를 양쪽 끝에 하면 앞서 언급한 최적의 배치를 만드는 것이 어려울 수 있기 때문이다.

홀수 크기의 그룹이 정확히 2개 있고, 짝수 크기의 그룹이 여러 개 있다고 하자. 만약 홀수 크기의 그룹 2개가 양쪽 끝에 놓인다면, 짝수 크기 그룹을 직사각형 형태로 사용할 수 없고, 직사각형에서 양쪽에 한 개씩 튀어나온 형태로 사용해야 한다. 이때 짝수 크기 그룹에서 희생을 더 해야한다. 나머지 경우에서는 어떤 크기의 그룹을 양쪽에 배치해도, 우리가 생각하는 "최적의 배치"가 (직사각형 최대한 사용, 홀수 크기 2개 직사각형으로 만들기) 가능하다. 이제 열심히 케이스 분류.

 

#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ldb;
const ll mod = 1e9 + 7;
 
 
ll n, m;
vector<ll> even_save;
vector<ll> odd_save;
 
void solve(void)
{
    int i, j; 
    ll sz, val, ans=0, subt=0, odd=0, even=0, saved, ex = 0; 
    cin >> n >> m;
    vector<ll> cc;
    for(i=1 ; i<=n ; i++)
    {  
        cin >> sz; cc.clear(); cc.resize(sz);
        for(j=0 ; j<sz ; j++) cin >> cc[j];
        sort(cc.begin(), cc.end());
        if(!(sz & 1))
        {
            val = cc[0] + cc[1] + cc[2] + cc[3];
            saved = cc[2] + cc[3];
            ex += cc[0] + cc[1];
            ans += val; even++;
            even_save.push_back(saved);
        }
        else
        {
             val = 2 * cc[0] + cc[1] + cc[2] + cc[3];
            saved = cc[2] + cc[3]; 
            ans += val; odd++; 
            odd_save.push_back(saved);   
        }
    }
    sort(even_save.begin(), even_save.end());
    reverse(even_save.begin(), even_save.end());
    sort(odd_save.begin(), odd_save.end());
    reverse(odd_save.begin(), odd_save.end());
    if(even >= 2) subt = max(subt, even_save[0] + even_save[1]);
    if(even >= 1 && odd >= 1) subt = max(subt, even_save[0] + odd_save[0]);
    if(odd >= 2 && (odd >= 4 || n == 2)) subt = max(subt, odd_save[0] + odd_save[1]);
    if(odd == 2 && n >= 3)
        subt = max(subt, odd_save[0] + odd_save[1] - ex);
    even_save.clear(); odd_save.clear();
    cout << ans - subt;
}
 
int main(void)
{
    fio; int tc; cin >> tc;
    for(int i=1 ; i<=tc ; i++) 
    {
        cout << "Case #" << i << endl;
        solve(); cout << endl;
    }
    return 0;
}

 

5번. 차이

주어진 조건을 두 변수 사이의 간선이라고 보면, 연결 컴포넌트에 안에서는 모든 차이 계산이 가능하다. 

문제가 되는 것은 사이클, 특히 한바퀴 돌았는데 합이 0이 되지 않는 사이클이다. 이 경우, 사이클에 도달할 수 있는 모든 정점들은 모순된 상태가 된다.

 

그러니, disjoint set 자료구조를 가져왔을 때 대강

• 두 정점이 같은 disjoint set에 속하지 않으면 Not Connected
• 두 정점이 같은 disjoint set에 속하는데 여기에 모순된 cycle이 있으면 Conflict
• 두 정점이 같은 disjoint set에 속하고 모순도 없으면 계산이 가능

함을 알 수 있다. 연결관계 자체만 봤을 때 disjoint set은 자명하고, 모순을 찾거나 계산을 하는 것이 문제다.

 

계산을 하기 위해서, 각 disjoint set의 대표 노드를 하나 두고 각 원소가 그 대표 노드의 값보다 얼마나 큰지 저장한다. 

원소들 사이의 차이는 알지만 원소 자체의 값은 모르니, 대표 노드의 값을 하나의 변수로 보고 차이만 저장하자는 의미다. 

 

이제 간선, 즉 하나의 등식이 추가되었다고 가정하자. 

• 만약 두 정점이 같은 disjoint set에 있다면, 모순이 있는지 바로 확인할 수 있다. 저장된 값의 차이가 입력된 값과 다르면 모순이다.
• 두 정점이 다른 disjoint set에 있다면, 이번에 추가된 등식은 두 disjoint set의 대표 노드 값 사이의 차이를 제공하는 정보가 된다. 이 경우, 두 disjoint set 중 하나의 대표를 전체의 새로운 대표로 정한다. 그 후, 흡수되는 집합의 각 원소들에 대해서 새로운 대표의 값과의 차이를 계산해야 한다. 이는 새로 얻어진 등식을 활용하여 할 수 있을 것이다. 물론, 두 disjoint set 중 이미 모순된 집합이 있다면 새로운 집합 역시 모순이 있다. 

두 disjoint set을 합치는 과정에서 걸리는 시간이 흡수되는 집합의 크기에 비례함을 알 수 있다. 그러므로, 작은 집합을 큰 집합에 흡수시키는 small-to-large 알고리즘을 사용하면 빠른 시간에 문제를 해결할 수 있다. 또한, 각 집합을 std::set 자료구조로 저장해야 집합의 순회가 쉽다. 

 

#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ldb;
const ll mod = 1e9 + 7;
 
ll ans[111111];
int par[111111];
int sz[111111];
int doom[111111];
set<int> idx[111111];
set<int>::iterator it;
ll n, k;
 
int find(int x)
{
    if(par[x] == x) return x;
    return par[x] = find(par[x]);
}
 
void unite(int uu, int vv, int u, int v, ll val)
{
    if(sz[uu] < sz[vv])
    {
        swap(uu, vv);
        swap(u, v);
        val = -val;
    }
    sz[uu] += sz[vv];
    doom[uu] |= doom[vv];
    ll dif = -val - ans[v] + ans[u];
    for(it = idx[vv].begin() ; it != idx[vv].end() ; it++)
    {
        int loc = (*it);
        ans[loc] += dif;
        par[loc] = uu;
        idx[uu].insert(loc);
    }
    idx[vv].clear();
}
 
void solve(void)
{
    int i, whi, u, v, uu, vv; ll val;
    cin >> n >> k;
    for(i=1 ; i<=n ; i++) idx[i].clear();
    for(i=1 ; i<=n ; i++) ans[i] = 0, par[i] = i, sz[i] = 1, doom[i] = 0;
    for(i=1 ; i<=n ; i++) idx[i].insert(i);
    for(i=1 ; i<=k ; i++)
    {
        cin >> whi >> u >> v;
        if(whi == 1)
        {
            cin >> val;
            uu = find(u);
            vv = find(v);
            if(uu == vv && ans[u] - ans[v] != val) doom[uu] = 1;
            if(uu != vv) unite(uu, vv, u, v, val);
        }
        else if(whi == 2)
        {
            uu = find(u);
            vv = find(v);
            if(uu != vv) cout << "NC\n";
            if(uu == vv && doom[uu] == 1) cout << "CF\n";
            if(uu == vv && doom[uu] == 0) cout << ans[u] - ans[v] << "\n";
        }
    }
}
 
int main(void)
{
    fio; int tc; cin >> tc;
    for(int i=1 ; i<=tc ; i++) 
    {
        cout << "Case #" << i << endl;
        solve(); cout << endl;
    }
    return 0;
}