제 7회(2021) SCPC 라운드1운 7월 16일 오후 9시에서 부터 17일 오후 9시까지 24시간 동안 온라인에서 진행되었다.
결과
16일 오후 6시에 퇴근하고 피곤해서 대회에 바로 참여하기 어려웠다. 때문에 다음날 4~5시간 정도를 투자하여 대회에 참여했다.
PS를 안한지 꽤 오래되었지만, 올솔을 할 수 있었다. 이번 1차 예선은 뭔가 이전보다 난이도가 낮은 느낌이다.
문제1.
왼쪽부터 순서대로 1부터 $N$번의 번호를 가진 $N$명의 사람들이 좌우로 서있다. 이들은 다음과 같은 규칙에 의해 친구 관계를 가진다.
- 번호 $i$인 사람은 자연수 $D_i$를 가지고 있다. ($0<D_i\leq N$)
- 번호 $i$인 사람은 번호 $i+D_i$인 사람과 친구 관계이다. 친구 관계는 대칭적이다. 즉, 한쪽만 상대방이 친구라고 생각하는 경우는 없다. 만약 번호 $i+D_i$인 사람이 존재하지 않는다면, 이 $D_i$는 무시된다.
- 사람 $A$와 $B$가 친구 관계이고 $B$와 $C$가 친구 관계이면, $A$와 $C$도 친구 관계이다.
이때, 극대 그룹이란, 그룹에 속한 사람 간에 친구 관계를 유지하면서 더 이상 사람을 추가할 수 없는 상태의 그룹을 뜻한다.
이 상황에서 각 사람들이 들고 있는 $D_i$들을 입력받아 친구 관계인 극대그룹의 개수를 출력하는 프로그램을 작성하라.
제한
- $N\leq 100,000$
풀이
각 사람을 정점으로 하고 친구관계를 간선으로 하는 그래프에서 연결요소의 개수를 구하는 문제와 같다. 연결요소의 개수를 구하는 방법으로 DFS/BFS 등을 사용할 수 있지만, 간단하게 DSU을 사용하여 구현했다.
#include <iostream>
#include <set>
#define MAXN 100000
using namespace std;
int T, N, D[MAXN], ans;
int djset[MAXN], djset_cnt[MAXN];
int djset_find(int d){
if(djset[d] == d) return d;
int r = djset_find(djset[d]);
djset[d] = r;
return r;
}
void djset_union(int d1, int d2){
int r1 = djset_find(d1);
int r2 = djset_find(d2);
if(r1 == r2) return;
if(djset_cnt[r1] < djset_cnt[r2]){
djset[r1] = r2;
djset_cnt[r2] += djset_cnt[r1];
}else{
djset[r2] = r1;
djset_cnt[r1] += djset_cnt[r2];
}
}
void init_djset(){
for(int j = 0; j < MAXN; ++j){
djset[j] = j;
djset_cnt[j] = 1;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> T;
for(int tt = 1; tt <= T; ++tt){
cout << "Case #" << tt << "\n";
init_djset();
cin >> N;
for(int j = 0; j < N; ++j)
cin >> D[j];
for(int j = 0; j < N; ++j){
int f = j + D[j];
if(f < N)
djset_union(j, f);
}
ans = 0;
set<int> exi;
for(int j = 0; j < N; ++j){
exi.insert(djset_find(j));
}
ans = exi.size();
cout << ans << "\n";
}
return 0;
}
문제2.
$n$비트로 구성된 이진수 $A=a_1a_2\dots a_n$ ($a_i$는 0 또는 1)와 자연수 $t$가 주어질 때, $A$로 부터 다음의 연산을 통해 새로운 이진수 $B$를 얻는다.
- 초기에 $b_i$ ($1\leq i\leq n$)는 모두 0으로 리셋한다.
- 만약 $i>t$ 이고 $a_{i-t}=1$ 이면 $b_i$는 1로 둔다.
- 만약 $i\leq n-t$ 이고 $a_{i+t}=1$ 이면 $b_i$는 1로 둔다.
이때, 변환된 이진수 $B$와 자연수 $t$에 대한 정보가 주어졌을 때, 역으로 $A$를 유추하는 프로그램을 작성하고자 한다.
유추 가능한 $A$가 둘 이상인 경우, 가장 작은 값을 출력하는 프로그램을 작성하라. 단, 유추가 불가능한 경우는 주어지지 않는다.
제한
- $2\leq n\leq 50,000$
- $1\leq t<n$
풀이
우선 $B$를 구하는 과정 2를 생각해보자. 해당 과정에서 사용되는 $a_i$는 각 $b_j$에 대해 유일하다. 이 경우, $b_i$에 대해 유일한 $a_{i\pm t}$는 $b_i$의 값과 동일하다는 것을 관찰할 수 있다. 이후 각 $b_i$에 대해 $b_i=0$인 경우, $a_{i-t}$와 $a_{i+t}$ 또한 0임을 이용하여 해당 경우를 처리한다. 이제 남은 경우는 $b_i=1$인 경우 중 고려해야하는 $a_j$가 2개인 경우인데, 해당 경우는 최소 $A$값을 찾아야 한다는 점을 고려하여, 두 $a_j$ 중에 1이 하나가 되도록 하도록 처리한다.
#include <iostream>
#include <string>
#define MAXN 50000
using namespace std;
int TT, N, T, ans[MAXN];
string numB;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> TT;
for(int tt = 1; tt <= TT; ++tt){
cout << "Case #" << tt << "\n";
cin >> N >> T >> numB;
for(int j = 0; j < N; ++j)
ans[j] = 2;
for(int j = 0; j < T && j + T < N; ++j)
ans[j + T] = numB[j] - '0';
for(int j = N - 1; j >= N - T && j - T >= 0; --j)
ans[j - T] = numB[j] - '0';
for(int j = 0; j + 2 * T < N; ++j){
if(numB[j + T] - '0') continue;
ans[j] = 0;
ans[j + 2 * T] = 0;
}
for(int j = 0; j + 2 * T < N; ++j){
if(numB[j + T] - '0' == 0) continue;
if(ans[j] == 1 || ans[j + 2 * T] == 1){
if(ans[j] == 2) ans[j] = 0;
if(ans[j + 2 * T] == 2) ans[j + 2 * T] = 0;
}else{
if(ans[j + 2 * T] == 2){
ans[j + 2 * T] = 1;
if(ans[j] == 2) ans[j] = 0;
}else{
ans[j] = 1;
if(ans[j + 2 * T] == 2) ans[j + 2 * T] = 0;
}
}
}
for(int j = 0; j < N; ++j)
cout << (ans[j] == 2 ? 0 : ans[j]);
cout << "\n";
}
return 0;
}
문제3.
정점이 $N$개이고 간선이 $M+K$개인 유향그래프가 주어진다. 이때, 간선들 중 일부인 $K$개의 간선들은 방향성이 정해져있지 않은 상태로 주어진다.
방향성이 정해진 간선들만 고려하면 해당 그래프에는 사이클이 존재하지 않는다.
방향성이 정해지지 않은 간선들의 방향을 그래프에서 사이클이 존재하지 않도록 모두 정하는 프로그램을 작성하라.
제한
- $3\leq N\leq 500$
- $0\leq M\leq 2,000$
- $1\leq K\leq 2,000$
- 하나의 정점을 간선이 연결하는 경우는 없다.
- 동일한 쌍의 정점들에 대해 여러개의 간선이 존재할 수 있다.
- 답이 여러개인 경우, 출력 내용이 사전순으로 가장 빠른 것을 출력한다.
풀이
간선과 정점의 개수가 그리 많지 않다는 점을 이용하여 단순 그래프 탐색을 이용해 해결한다. 사전순으로 가장 작은 값을 출력해야 하므로, 0임을 가정하고 탐색하여 사이클이 발견되면 1로 처리한다.
#include <iostream>
#include <vector>
#define MAXN 500
using namespace std;
struct edge{
int s, e;
};
int T, N, M, K, visit[MAXN], vcount;
vector<int> G[MAXN];
vector<edge> E;
vector<bool> ans;
void init_G(){
E.clear();
ans.clear();
for(int j = 0; j < MAXN; ++j)
G[j].clear();
}
bool find_by_travel(int v, int tv){
visit[v] = vcount;
for(int j = 0; j < G[v].size(); ++j){
int u = G[v][j];
if(u == tv) return true;
if(visit[u] == vcount) continue;
if(find_by_travel(u, tv)) return true;
}
return false;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> T;
for(int tt = 1; tt <= T; ++tt){
cout << "Case #" << tt << "\n";
init_G();
cin >> N >> M >> K;
for(int j = 0; j < M; ++j){
int s, e; cin >> s >> e;
G[s - 1].push_back(e - 1);
}
for(int j = 0; j < K; ++j){
int s, e; cin >> s >> e;
E.push_back({s - 1, e - 1});
ans.push_back(false);
}
for(int j = 0; j < K; ++j){
int s = E[j].s, e = E[j].e;
++vcount;
if(find_by_travel(e, s)){
ans[j] = true;
G[e].push_back(s);
}else{
G[s].push_back(e);
}
}
for(int j = 0; j < K; ++j)
cout << ans[j];
cout << "\n";
}
return 0;
}
문제4.
복도를 사이에 두고 2행 $m$열로 구성된 총 $2m$개의 방이 존재하는 호텔이 있다.
예약자들의 총 수는 $2m$명이고, 예약자들의 전체집합 $S$에 대해서, $S$는 집합 $S_1, S_2, S_3, \dots, S_n$으로 나뉜다.
또한 임의의 두 집합 $S_h$, $S_k$에 대해서 $S_h\cap S_k=\emptyset$ 이고, $\left\vert S_i \right\vert \leq 5, \forall i$ 이다.
예약 시스템은 방 하나에 한 사람씩 배정한다. 즉, 임의의 배정 $A$는 예약자들의 집합에서 방들의 집합으로 일대일 대응이다.
이때, 한 집합에 속한 예약자들은 모두 한 덩어리의 방들을 배정받아야 한다. 한 덩어리의 방들이란, 덩어리에 속한 어떤 방 두개에 대해서도, 덩어리에 속하고 인접한 방들을 통해서 이동이 가능하다는 의미이다. 여기서 인접한 방이란, 행이 같거나 열이 같으면서 이웃한 방이다.
서로 다른 집합에 속하는 예약자 $a$와 $b$가 인접하게 배정되면, $a$와 $b$사이에는 충돌 $c$가 발생하고, 이때의 페널티는 $p(c)=w_a+w_b$로 주어진다.
그렇다면 배정 $A$의 페널티 $p(A)$는 $A$에서 발생하는 모든 충돌의 페널티 합으로 정의한다.
최소 페널티를 구하는 프로그램을 작성하라.
제한
- $2\leq n\leq 20,000$
- $5\leq m\leq 50,000$
- $5\leq \left\vert S_i \right\vert \leq 100,000$
- $1\leq w_{ij}\leq 10,000,000$
- $\left\vert S \right\vert = 2m$
풀이
고려해야 할 예외 상황이 있어서 제출 수가 많았던 문제다.
충돌되는 예약자의 수를 최소화 해야 하므로, 각 그룹의 배치를 같은 그룹에 속한 사람끼리 최대한 같은 열에 배치하도록 해야한다. 이후 양쪽 끝에 위치하게 되는 두 그룹에 대한 페널티를 고려해주면 된다.
홀수 그룹과 짝수 그룹이 섞여있는 상황에서 예외 케이스가 존재하는데, 이는 홀수 그룹이 양 끝에 위치하는 경우이다. 해당 경우에서 홀수 그룹이 4개 이상인 경우와 2개인 경우를 추가적으로 고려해줘야 한다.
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#define MAXN 20000
using namespace std;
typedef long long int lli;
int T, N, M, I[MAXN];
vector<vector<int>> Weven, Wodd;
lli ans;
void init(){
ans = 0;
Weven.clear();
Wodd.clear();
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> T;
for(int tt = 1; tt <= T; ++tt){
cout << "Case #" << tt << "\n";
init();
cin >> N >> M;
for(int j = 0; j < N; ++j){
cin >> I[j];
if(I[j] % 2){
Wodd.push_back(vector<int>());
for(int i = 0; i < I[j]; ++i){
int tmp; cin >> tmp;
Wodd.back().push_back(tmp);
}
sort(Wodd.back().begin(), Wodd.back().end());
}else{
Weven.push_back(vector<int>());
for(int i = 0; i < I[j]; ++i){
int tmp; cin >> tmp;
Weven.back().push_back(tmp);
}
sort(Weven.back().begin(), Weven.back().end());
}
}
priority_queue<lli, vector<lli>, greater<lli>> pq;
lli cornerans = -1;
if(Wodd.size() == 2 && N > 2){
cornerans = (lli)Wodd[0][0] * 2LL + Wodd[0][1];
cornerans += (lli)Wodd[1][0] * 2LL + Wodd[1][1];
for(int j = 0; j < Weven.size(); ++j){
cornerans += (lli)Weven[j][0] * 2LL + Weven[j][1] * 2LL + Weven[j][2] + Weven[j][3];
}
}
for(int j = 0; j < Wodd.size(); j += 2){
vector<int> arr;
for(int i = 2; i < Wodd[j].size(); ++i) arr.push_back(Wodd[j][i]);
for(int i = 2; i < Wodd[j + 1].size(); ++i) arr.push_back(Wodd[j + 1][i]);
ans += (lli)Wodd[j][0] * 2LL + Wodd[j][1];
ans += (lli)Wodd[j + 1][0] * 2LL + Wodd[j + 1][1];
if(!(Weven.size() == 0 && Wodd.size() == 2)){
ans += (lli)Wodd[j][2] + Wodd[j][3];
ans += (lli)Wodd[j + 1][2] + Wodd[j + 1][3];
}
if(Wodd.size() == 2){
pq.push(max((lli)Wodd[j][2] + Wodd[j][3], (lli)Wodd[j + 1][2] + Wodd[j + 1][3]));
}else{
pq.push((lli)Wodd[j][2] + Wodd[j][3]);
pq.push((lli)Wodd[j + 1][2] + Wodd[j + 1][3]);
}
while(pq.size() > 2) pq.pop();
}
if(Weven.size() == 0 && Wodd.size() == 2){
cout << ans << "\n";
continue;
}
for(int j = 0; j < Weven.size(); ++j){
lli most2 = (lli)Weven[j][2] + Weven[j][3];
pq.push(most2);
while(pq.size() > 2) pq.pop();
ans += most2 + Weven[j][0] + Weven[j][1];
}
while(!pq.empty()){
ans -= pq.top();
pq.pop();
}
if(cornerans != -1)
ans = min(ans, cornerans);
cout << ans << "\n";
}
return 0;
}
문제5.
$N$개의 변수 $X_1, X_2, \dots, X_N$이 존재한다. 처음에는 $X_i$들의 값에 대한 어떤 정보도 가지고 있지 않다. 이후 $K$개의 명령이 주어진다. 명령은 두 가지 종류로 구성된다.
첫번째 종류의 명령은 두 변수의 차이를 알려주는 것이다. 즉, $X_i-X_j=d$라는 정보를 준다. 여기서 $X_j-X_i=-d$라는 정보도 준 것으로 간주한다.
두번째 종류의 명령은 두 변수의 차이를 붇는 것이다. 해당 명령이 주어지면 다음 중 하나의 답을 해야한다.
- 그 시점까지 주어진 모든 정보에 따라 두 변수의 차이가 유일하게 정해지면 그 값을 출력해야 한다.
- 그 시점까지 주어진 모든 정보에 따라 두 변수의 차이를 유추할 방법이 전혀 없다면 NC를 출력한다. (Not Connected)
- 그 시점까지 주어진 모든 정보에 따라 두 변수의 차이를 유추할 수 있지만 하나로 정하는 것이 불가능 하다면 CF를 출력한다. (Conflict)
명령들은 하나하나 순서대로 주어지는 것으로 생각한다.
제한
- $1\leq N\leq 100,000$
- $1\leq K\leq 200,000$
- $\left\vert d \right\vert \leq 10,000$
풀이
각 변수를 하나의 정점으로 하고, 두 변수의 차이를 간선의 가중치로 가지는 그래프를 주어진 연산에 대해 효율적으로 처리하는 문제다. 이는 가중치가 추가된 DSU를 구현하여 해결할 수 있다.
#include <iostream>
#define MAXN 100000
using namespace std;
struct edge{
int v, offset;
};
int T, N, K;
edge djset[MAXN];
bool spoiled[MAXN];
void init_djset(){
for(int j = 0; j < MAXN; ++j){
spoiled[j] = false;
djset[j] = {j, 0};
}
}
edge djset_find(int v){
if(djset[v].v == v) return djset[v];
edge r = djset_find(djset[v].v);
r.offset += djset[v].offset;
djset[v] = r;
return r;
}
void djset_union(int v1, int v2, int offset){
edge r1 = djset_find(v1);
edge r2 = djset_find(v2);
if(r1.v == r2.v) return;
djset[r2.v] = {r1.v, offset + r1.offset - r2.offset};
spoiled[r1.v] |= spoiled[r2.v];
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> T;
for(int tt = 1; tt <= T; ++tt){
cout << "Case #" << tt << "\n";
init_djset();
cin >> N >> K;
for(int j = 0; j < K; ++j){
int t; cin >> t;
if(t == 1){
int x, y, d; cin >> x >> y >> d;
--x; --y;
edge r1 = djset_find(x);
edge r2 = djset_find(y);
if(r1.v != r2.v){
djset_union(x, y, d);
}else{
if(r2.offset - r1.offset != d){
spoiled[r1.v] = true;
}
}
}else{
int x, y; cin >> x >> y;
--x; --y;
edge r1 = djset_find(x);
edge r2 = djset_find(y);
if(r1.v != r2.v){
cout << "NC\n";
}else{
if(spoiled[r1.v])
cout << "CF\n";
else
cout << r2.offset - r1.offset << "\n";
}
}
}
}
return 0;
}