AtCoder Beginner Contest 304 후기 (ABC 304 4솔)

여러모로 아쉬웠음. C가 더러워 보여서 미루고 D로 넘어갔는데, D를 풀 아이디어가 생각나지 않아서 시간만 날렸다.

E는 예상 외로 쉬웠다

 

그리고 이번 앳코더에는 체점 큐가 밀리는 사고가 있어서... 답이 틀려도 그게 틀렸는지 알고 싶으면 2~30분을 기다려야 했다. 주최측에서도 문제라고 생각했는지 시험 종료 1분전에 시험 시간을 20분 연장시켜 줬지만 추가된 시간 동안 다른 문제를 풀지는 못했음.

악!! 체점 큐가 밀리는 이슈 때문에 대회가 Unrated 처리되었다!! 이번에 30점가량 올릴 수 있었는데!!악!! 체점 큐가 밀리는 이슈 때문에 대회가 Unrated 처리되었다!! 이번에 30점가량 올릴 수 있었는데!!악!! 체점 큐가 밀리는 이슈 때문에 대회가 Unrated 처리되었다!! 이번에 30점가량 올릴 수 있었는데!!악!! 체점 큐가 밀리는 이슈 때문에 대회가 Unrated 처리되었다!! 이번에 30점가량 올릴 수 있었는데!!

 

A - 최솟값, 반복문, 배열

A번치고는 까다롭게 나왔다.

나이의 최솟값의 인덱스를 찾아서, 그 인덱스부터 끝까지. 다시 처음 인덱스부터 최솟값 인덱스까지 순서대로 출력

A번을 제출하는데 이번엔 앳코더 서버가 터져서 한참 동안 제출이 안 됐다. 그래서 또 시간 날림

최근 들어 앳코더에 DDOS 공격이 잦은 것 같다

 

B - 영어독해

그냥 하라는 대로만 하면 된다. 참가자들의 타자 속도와 영어독해 속도를 테스트하는 문제 같다

 

C - Disjoint set, union-find, 두 점 사이의 거리

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define ll long long
using namespace std;

double dist(double a,double b,double c,double d){
	return sqrt((a-c)*(a-c)+(b-d)*(b-d));
}
int parent[2001];
int findp(int n){
	if(parent[n]==n)return n;
	return parent[n]=findp(parent[n]);
}

int main(void) {
	fastio;
	int N,D;cin>>N>>D;
	for (int i = 0; i <= N; i++)
	{
		parent[i]=i;
	}
	vector<pair<int,int>> v(N+1);
	for (int i = 1; i <= N; i++)
	{
		int a,b;
		cin>>a>>b;
		v[i]={a,b};
	}
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			if(i==j)continue;
			int pa = findp(i);
			int pb = findp(j);
			if(pa!=pb&&dist(v[i].first,v[i].second,v[j].first,v[j].second)<=D){
				if(pa<pb)parent[pb]=pa;
				else parent[pa]=pb;
			}
		}
	}
	for (int i = 1; i <= N; i++)
	{
		findp(i);
		if(parent[i]==1)cout<<"Yes\n";
		else cout<<"No\n";
	}
	
	return 0;
}

풀면서

C번 문제에 유니온파인드가 나올 리가 없는데 내가 잘못 풀고 있는 건가?? 라는 생각이 들었다, 그래서인가 구현에 시간이 더 걸렸다

N이 2000으로 작고, 시간제한이 넉넉하므로 반복문을 충분히 돌리기만 해도 풀릴 것 같긴 한데,

유니온파인드를 쓰는 게 더 구현도 쉽고 확실한 결과를 낼 것 같아서 이렇게 했음

 

정해가 뭔지 궁금해진다 에디토리얼을 봐야겠다

 

정해 : DFS, BFS, Disjoint set union 무엇을 사용하든 풀린다. 

 

N*N시간복잡도로, 2차원 벡터로 그래프를 표현하고 나서 진행하면 편하다. 두 점 사이의 거리가 D보다 작은 경우에만 간선이 존재한다고 하면 된다.

 

D - 모르겠음. 좌표압축, 2차원 누적합??

W,H가 10억으로 주어지므로 전체 공간을 2차원 배열로 표현하는 것은 불가능하다.

문제를 더 읽어 보면, 케이크 위의 딸기와 칼질의 좌표가 겹치는 일은 없다고 한다.

그러므로 정렬과 map을 활용해 좌표를 압축하고, 압축한 인덱스를 이용해 2차원 배열을 만들고, 그 2차원 배열을 딸기 개수의 2차원 누적합 배열로 사용하면 된다고 생각했음

 

그런데 생각해 보면, 케이크 위의 딸기가 최대 20만개, 칼질이 X방향으로 20만, Y방향으로 20만번 가능하므로

만들어야 하는 2차원 누적합 배열의 크기가 arr[400002][400002]여야 한다. 공간복잡도가 초과된다.

 

그러므로 다른 방법을 생각해내야 하는데,,, 모르겠다

 

업솔빙>>>

 

에디토리얼>>>

공간복잡도/시간복잡도 를 줄이기 위해, 딸기가 1개 이상인 케이크 조각만 map을 이용해 표현한다.

 

2차원 배열로 x방향의 칼질 B번과 y방향의 칼질 A번을 거치면, (A+1)*(B+1)개의 직사각형 케이크 조각이 생성될 것이고, 이것들의 한 꼭짓점 값을 key로 쓸 수 있다.

lower_bound를 이용해 케이크 조각이 어느 꼭짓점(어느 케이크 조각)에 존재하는지 판단할 수 있고, 그때마다 그 key값에 해당하는 value값을 1씩 증가시키면 map에는 딸기가 1개 이상인 케이크 조각만 들어있게 된다

 

이후에는 map의 모든 원소를 순회하면서 딸기의 최대 / 최소 개수를 판단하면 되고, map의 사이즈를 이용해 최소 딸기 개수가 0개인지 아니면 1개인지 판단이 가능하다.

 

 

 

E - Disjoint set, Union-find

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define ll long long
using namespace std;

int parent[200001];
int fparent(int n){
	if(parent[n]==n)return n;
	return parent[n] = fparent(parent[n]);
}

int main(void) {
	fastio;
	int N,M;cin>>N>>M;
	for (int i = 0; i < 200001; i++)
	{
		parent[i]=i;
	}
	
	for (int i = 0; i < M; i++)
	{
		int a,b;cin>>a>>b;
		int pa = fparent(a);
		int pb = fparent(b);
		parent[pb] = pa;
	}

	set<pair<int,int>> dont;//붙으면 안되는 parent의 집합

	int K;cin>>K;//K개 조건을 모두 만족해야 good graph 20만 조건
	for (int i = 0; i < K; i++)
	{
		int a,b;cin>>a>>b;
		int pa = fparent(a);
		int pb = fparent(b);
		dont.insert({min(pa,pb),max(pa,pb)});
	}
	int Q;cin>>Q;//간선 하나를 연결할 경우 -> 여전히 좋은 그래프인가? 20만 쿼리
	for (int i = 0; i < Q; i++)
	{
		int a,b;cin>>a>>b;
		int pa = fparent(a);
		int pb = fparent(b);
		if(dont.count({min(pa,pb),max(pa,pb)}))cout<<"No\n";
		else cout<<"Yes\n";
	}
	// for (auto i:dont)
	// {
	// 	cout<<i.first<<" "<<i.second<<"\n";
	// }
	
	return 0;
}

사실 이게 D번 난이도가 아닐까?? 엄청 무난하게 풀렸다

처음에 M개 간선의 입력을 받아서, union하고, 모든 정점의 parent가 무엇인지 배열에 저장해 놓는다

이후 good graph가 되기 위한 K개의 조건을 판단해야 하는데, 매 쿼리마다 K개 조건을 판단할 경우 시간 복잡도가 20만 * 20만 = 400억 = 400초 가 되어버리므로 안된다.

그러므로, K개 조건의 판단을 간소화하기 위해, 엮이면 안 되는 parent들의 조합을 set에 저장해 놓는다.

이후 Q개 쿼리를 처리한다. 두 정점의 parent를 find한 뒤, 그 parent 들의 조합이 set에 존재하는지 안하는지 판단하고, set에 존재한다면 No, 존재하지 않는다면 Yes를 출력하면 된다.

 

 

F, G,  EX는 D에 시선이 팔려서 쳐다보지도 않았음