SCPC 2021 1차 예선 후기

7/16 15:00 ~ 7/17 15:00에 진행되었던 SCPC 2021 1차 예선에 참여해보았습니다.

혹여라도 풀이 글이 문제가 될 경우 바로 비공개 처리 하도록 하겠습니다.

 

 

후반 문제 난이도는 대강 골드 상위? 플레 중하위권? 쯤 될 것 같네요.

작년에는 codeground에서 진행되고 있는지도 모르고 내내 자버려서 참여를 못했기에

예년과의 난이도 비교는 할 수 없네요 ㅠㅠ

올해에는 여러 문제에서 삽질을 심하게 하는 바람에 많이 틀렸고 많이 제출하였습니다.

 

2차 예선 잘 되어 본선까지 나갈 수 있으면 좋을 것 같네요

 

문제는 아마 추후에 codeground에서 보실 수 있을 것 같습니다.

 

1. 친구들

문제 요약

n명의 사람이 있고 각각 1~n의 번호가 붙어있다.

이 사람들은 Di (0<Di<=n)의 값을 지니는데 이는 i+Di번째 사람과 친구라는 소리다.

i+Di>n이면 그냥 뒤에는 친구가 없다는 말

1<=T<=50 (테스트 케이스 수)

n<=100000

 

풀이

사람들은 모두 친구를 가지고 있다 i+Di이내에 친구가 있으면 그 사람이 이 친구체인의 마지막 사람일 것이다.

즉 i+Di가 n을 넘어서면 그 뒤에 친구가 없고 해당 i번째 사람이 마지막 친구다. <- 이런 사람 수를 세어준다

 

소스코드

#include <bits/stdc++.h>
using namespace std;

int main(){
	int T, n, N;
	scanf("%d",&T);
	for(int N=0; N<T; ){
		int a, c=0;
		scanf("%d",&n);
		for(int i=0; i<n; ++i){
			scanf("%d",&a);
			if(i+a>=n) ++c;
		}
		printf("Case #%d\n%d\n",++N,c);
	}
}

 

2. 이진수

문제 요약

n개 비트로 구성된 A=a1a2,,,an에 대해 자연수 t가 주어질 때 아래의 연산을 통해 n개 비트로 구성된 이진수 B를 구한다.

1. 처음에 B는 0

2. if i-t>0 && a(i-t) ==1 : b(i)=1

3. if i+t<=n && a(i+t)==1 : b(i)=1

만들어진 B와 t가 주어질 때 가능한 A중 이진수로 보았을 때 가장 작은 값을 구해라

1<=T<=64 (테스트 케이스)

2<=n<=50000, 1<=t<n

 

풀이

이진수로 보았을때 가장 작은 값이 오른쪽이 최소화되어야한다고 생각해서 삽질을 심하게 하다가

마지막에 그 반대인걸 알게되어 바로 맞았다. (내 3시간...)

 

범위가 허용하는 한, bi기준 -t, +t좌표중 하나라도 a가 0이면 bi는 1이다.

또 bi가 0이라는 말은 -t, +t좌표의 a가 모두 0이어야 한다.

사전식 가장 작은 수를 구하는거로 보면 되므로 일단 그리디라 할 수 있다.

왼쪽이 최대한 0이 될 수 있도록 해주면 된다.

우선 전처리를 bi가 0인 경우 a(i-t) = a(i+t) = 0으로 고정한다.

두번째로, for i=1~n : if b(i-t)==1 : a(i)=1, b(i-t) = b(i+t) = 0.

 bi-t가 1인게 발견되면 바로 ai=1로 둔다. 현재까지 A에서 1로 두기위해 가능한 부분 중 가장 작은 수가 되기 때문.

 ai가 1이 되었다는 말은 b(i+t)가 1인걸 체크했다는 소리다. 즉, a(i+2t)에서 b(i+t)에 대해 신경쓸필요가 없어야 한다.

 그래서 b(i+t)와 b(i-t) 둘다 0으로 그냥 바꿔준다.

세번째로, 두번째에서 처리를 다 하고도 남은애들이 있다. 앞에서 처리 못해줬거나 1~t번째에서 뒤쪽 B에 1이 있는 경우

 for i=1~n : if b(i+t)==1 : a(i)=1, b(i-t) = b(i+t) = 0.

위와같이 처리해주면 정답 :)

 

소스코드

#include <bits/stdc++.h>
using namespace std;

int A[100001], n, t;
char B[100001];

int main(){
	int T, N;
	scanf("%d",&T);
	for(int N=0; N<T; ){
		scanf("%d%d",&n,&t);
		scanf("\n%s",B);
		printf("Case #%d\n",++N);
		for(int i=0; i<n; ++i) A[i]=-1;
		for(int i=0; i<n; ++i) {
			if(B[i]=='0'){
				if(i-t>=0) A[i-t]=0;
				if(i+t<n) A[i+t]=0;
			}
		}
		for(int i=0; i<n; ++i){
			if(A[i]==-1) if(i-t>=0 && B[i-t]=='1') A[i]=1;
			if(A[i]==1){
				if(i-t>=0) B[i-t]='0';
				if(i+t<n) B[i+t]='0';
			}
		}
		for(int i=0; i<n; ++i){
			if(A[i]==-1){
				if(i+t<n && B[i+t]=='1') A[i]=1, B[i+t]='0';
				else if(i-t>=0 && B[i-t]=='1') A[i]=1, B[i-t]='0';
				else A[i]=0;
			}
		}
		for(int i=0; i<n; ++i) printf("%d",A[i]); puts("");
	}
}

 

3. No Cycle

문제 요약

사이클이 없는 방향 그래프가 주어진 후 k개의 무방향 간선이 주어진다.

k개의 무방향 간선 입력은 a, b로 주어지는데 사이클이 없도록 방향을 정해줬을 때 

a->b로 연결되면 0, b->a로 연결되면 1로 나타낸다.

입력받은 무방향간선들을 0 또는 1로 표시했을 때 사전순 가장 작은 경우를 구해라

1<=T<=70 (테스트 케이스)

3<=n<=500

0<=m<=2000

1<=k<=2000

 

풀이

이것도 그리디다.

일단 방향 간선을 모두 입력받은 후 그래프를 그려준다.

그다음 무방향 간선 쿼리에 대해 다음과 같이 생각한다.

1. if a->b로 가는 경로가 이미 존재한다 : 0출력

2. if b->a로 가는 경로가 이미 존재한다 : 1출력

3. else a->b 간선을 새로 이어주고 0출력

이게 TLE가 나기 쉽도록 되어있어서 처음에 n작다고 플루이드 와샬 썼다가 고생했는데,

그냥 bfs든 dfs든 잘 써서 a, b간의 관계를 구하면 되는 것 같더라

대충 O(k(n+m)) ?

 

소스코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<ll> v[501], w[501];

bool bfs1(int a,int b){
	ll e[501]={0}, s=0;
	vector<ll> t;
	t.push_back(a); e[a]=1;
	for(ll f=t[s]; s<t.size(); ++s){
		
		for(int j=0; j<v[f].size(); ++j){
			if(!e[v[f][j]]){
				if(v[f][j]==b) return true;
				e[v[f][j]]=1;
				t.push_back(v[f][j]);
			}
		}
	}
	return false;
}

bool bfs2(int b, int a){
	ll e[501]={0}, s=0;
	vector<ll> t;
	t.push_back(a); e[a]=1;
	for(ll f=t[s]; s<t.size(); ++s){
		for(int j=0; j<w[f].size(); ++j){
			if(!e[w[f][j]]){
				if(w[f][j]==b) return true;
				e[w[f][j]]=1;
				t.push_back(w[f][j]);
			}
		}
	}
	return false;
}

int main(){
	ll T, N;
	scanf("%lld",&T);
	for(ll N=0; N<T; ){
		printf("Case #%lld\n",++N);
		ll n, m, q;
		scanf("%lld%lld%lld",&n,&m,&q);
		for(int i=1; i<=n; ++i) v[i].clear(), w[i].clear();
		for(int i=0; i<m; ++i){
			ll a, b;
			scanf("%lld%lld",&a,&b);
			v[a].push_back(b);
			w[b].push_back(a);
		}
		for(int i=0; i<q; ++i){
			ll a, b;
			scanf("%lld%lld",&a,&b);
			bool A=bfs1(a,b), B=bfs2(b,a);
			if(A) printf("0");
			else if(B) printf("1");
			else {
				printf("0");
				v[a].push_back(b);
				w[b].push_back(a);
			}
		}
		puts("");
	}
}

 

4. 예약 시스템

문제 요약

2행 m열의 호텔이 있다.

한 호실에 대해 맞은편 및 좌우 호실은 인접한 호실이라 한다.

단체 손님들이 들어오는데 각 단체는 4명 이상이다.

각 손님마다 값 w를 지니는데 인접한 호실의 손님이 다른 단체면 충돌을 일으킨다. 두 손님이 a, b일 때 그 값은 wa+wb

충돌을 최소화 할 수 있도록 손님들을 배치하자

1<=T<=67 (테스트 케이스)

2<=n<=20000

5<=m<=50000

 

풀이

이거도 그리디라 봐야할까? 싶다.

같은 그룹끼리 묶어두면 다른 그룹과 마주치는 손님은 4명으로 한정된다. 이 값을 가장 작은 값으로 둬야한다.

손님 수가 총 2m이므로 홀수그룹은 홀수개일 수 없다. 즉 짝지어 있다.

이 경우 홀수그룹 2개의 가장 작은 손님은 충돌을 한번씩 더 하게 된다.

 

경우의 수를 조금 나눠볼 수 있다.

i) 짝수 그룹만 있음

모든 4개 손님에 대해 더한 후 양 가 호실에 거주하는 그룹의 가장 큰 2값씩 총 4개를 빼준다.

즉, res = (1a+2a+3a+4a) + (1b+2b+3b+4b) - (3a+4a + 3b+4b) (단, 1a<=2a<=3a<=4a 및 b도 동일)

 

ii) 홀수 그룹만 있음

짝수그룹과 같은 계산을 한 후 튀어나와있는 1a, 1b에 대해서 서로 충돌하므로 한번씩 더 더해준다.

즉, res = (1a+2a+3a+4a + 1a) + (1b+2b+3b+4b + 1b) - (3a+4a + 3b+4b)

 

iii) 섞여있는 그룹

경우의 수를 조금 나눌 수 있다.

 a) 홀수그룹이 2개일 때 특수케이스 / 홀짝홀

이 경우 짝수들의 가장 작은 2값들을 모두 한번씩 더 더해줘야한다.

해당하는 예제는 홀수 그룹 2개의 큰값 2개들이 매우 큰 경우이다.

 

 b) 홀 짝 (or 짝 홀)

 c) 짝 홀 짝

 d) 홀짝홀(홀수그룹 >=4)

a), b), c), ( d) ) 중 가장 큰 값을 출력해주면 된다.

 

소스코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll MX(ll a, ll b){return a>b?a:b;}
vector<ll> v1, v2; // v1 odd, v2 even

int main(){
	ll T, N;
	scanf("%lld",&T);
	for(ll N=0; N<T; ){
		v1.clear(), v2.clear();
		printf("Case #%lld\n",++N);
		ll n, m, res=0, even=0;
		scanf("%lld%lld",&n,&m);
		for(ll i=0; i<n; ++i){
			ll l, a[5];
			scanf("%lld",&l);
			for(ll j=0; j<4; ++j) scanf("%lld",&a[j]);
			for(ll j=4; j<l; ++j) scanf("%lld",&a[4]), sort(a,a+5);
			res+=a[0]+a[1]+a[2]+a[3];
			if(l&0x01) v1.push_back(a[2]+a[3]), res+=a[0];
			else v2.push_back(a[2]+a[3]), even+=a[0]+a[1];
		}
		sort(v1.begin(),v1.end());
		sort(v2.begin(),v2.end());
		if(n==1) res=0;
		else if(!v1.size()) res-=(v2[v2.size()-1]+v2[v2.size()-2]);
		else if(!v2.size()) res-=(v1[v1.size()-1]+v1[v1.size()-2]);
		else { // v1>=2 & v2>=1
			ll mx = MX( v1[v1.size()-1]+v1[v1.size()-2]-even, v1[v1.size()-1]+v2[v2.size()-1] ); // ?€ 吏??€ / ?€ 吏?
			if(v1.size()>3) mx=MX(mx,v1[v1.size()-1]+v1[v1.size()-2]);
			if(v2.size()>1) mx=MX(mx,v2[v2.size()-1]+v2[v2.size()-2]); // 吏??€ 吏?
			res-=mx;
		}
		printf("%lld\n",res);
	}
}

 

5. 차이

문제 요약

n개의 변수가 있다. Xi로 나타낼 때, k개의 명령이 주어진다.

각 명령에 대해 첫 입력은 종류를 나타낸다.

1인 경우 a, b, c를 입력받고 X(a) - X(b) = c임을 나타낸다.

2인 경우 a, b를 입력받고 X(a) - X(b)가 얼마인지 유추한다.

유추 가능한 경우가 여러가지인 경우 "CF"

유추 가능한 경우가 하나인 경우 그 값 출력

유추 불가능한 경우 "NC" 출력

1<=n<=100000

1<=k<=200000

 

풀이

그래프라 생각했을 때 하나의 그래프 집합 내에서 임의의 두 노드사이에 가중치가 다른 경로가 여러가지가 있다면 그 집합의 노드간 연결은 모두 CF이다.

또한 서로 다른 집합의 노드 간 연결은 NC이다.

그 이외의 경우 출력해주면 된다.

 

unionfind를 사용한다.

R : 각 노드에서 자신의 부모를 저장해두고

D : 각 노드에서 루트까지 거리(X(root) - X(i)의 값)를 저장하고

V : 해당 집합 내에 CF가 될만한게 있는지 체크한다

1번 쿼리가 들어왔을 때,

i) a, b의 루트가 다른 경우

경로를 이어준다.

ii) a, b의 루트가 같은 경우

기존에 있던 D(a)-D(b)값이 c와 다르다면 V(root) 체크 및 업데이트(는 나중에 알아서 합니다)

2번 쿼리가 들어왔을 때,

i) a, b의 루트가 같은 경우

루트의 V가 체크되어있다면 "CF" 그렇지 않다면 D(a)-D(b)를 출력

ii) a, b의 루트가 다른 경우

"NC" 출력

 

소스코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll r[110000], d[110000], v[110000];

ll uf(ll x){
	if(x==r[x]) return x;
	ll t=uf(r[x]);
	d[x]+=d[r[x]];
	v[r[x]]=v[x]=(v[r[x]]|v[x]);
	return r[x]=t;
}

int main(){
	ll T, N;
	scanf("%lld",&T);
	for(ll N=0; N<T; ){
		printf("Case #%lld\n",++N);
		ll n, k;
		scanf("%lld%lld",&n,&k);
		for(ll i=0; i<=n; ++i) r[i]=i, d[i]=v[i]=0;
		while(k--){
			ll o, a, b;
			scanf("%lld%lld%lld",&o,&a,&b);
			ll x=uf(a), y=uf(b);
			if(o==1){
				ll c;
				scanf("%lld",&c);
				//if(x>y){ll t=x; x=y; y=t;c=-c;}
				if(x!=y){
					r[x]=y;
					v[x]=v[y]=(v[x]|v[y]);
					d[x]=d[b]-d[a]+c;
				}
				else if(d[a]-d[b]!=c) v[x]=1; // CF
			}
			else{
				if(x!=y) printf("NC\n");
				else {
					if(v[x]) printf("CF\n");
					else printf("%lld\n",d[a]-d[b]);
				}
			}
		}
	}
}