2020 icpc 인터넷예선 후기

생애 첫 icpc 였다. 

아무래도 ps계에서 제일 큰 대회중 하나이기에 전 날부터 잠도 오지 않았다.

우리 팀은 다 신입생이고, 뛰어나게 잘하는 사람이 없었기에 본선 진출은... 사실상 다음기회에 해야했고

목표는 남들이 다 푸는 기본문제 쉬운거 4개 + 어려운 문제 1개를 푸는 걸로 목표로 잡고 갔다.

 

 

푼 순서대로 solution을 나열해보면...

 

I. Project Teams (4min)

 

이 문제딱 풀었을 때 우리팀은 2등이였다(!) 퍼솔은 0분에 퍼솔이던데 ...그게 가능할까... 

어쨌든 코포에서 a번으로 많이 봤을법한 문제다. 사실 아마 I번으로 등록을 많은 사람들이 찾았을 텐데 없는 걸 보고 실망했으나, 그래도 쉬운 문제가 I 번으로 출제 되었다.

 

sol)

그냥 정렬하고 젤 작은거 젤 큰거 더해가면서 큐에서 빼고 min으로 찾아주면 된다.

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int n, a;
vector<int> v;
int main() {
	cin >> n;
	n *= 2;
	for (int i = 0; i < n; i++) {
		cin >> a;
		v.push_back(a);
	}
	sort(v.begin(), v.end());
	a = 1234567891;
	for (int i = 0; i < n; i++) {
		a = min(a, v[i] + v[n - 1 - i]);
	}
	cout << a;
}

 

E. Cycle Game(22min)

 

팀원 한테 문제 설명 듣자마자 유니온-파인드 인거 알고 바로 풀이가 떠올랐는데, 여기서 아쉬운점이 있다...

1. 내가 문제를 이거부터 바로 봤더라면

2. 입력이 들어오는 건 상관없이 들어오는거다. 입력들어오는 중간에 return 해주면 안되는 줄 알았다.

3. 내 풀이를 팀원들에게 설명하느라 시간을 썼다.

 

사실 1번은 그럴 수 있다고 쳐도 2,3번은 개선할 여지가 있었다. 최소 10분쯤은 빨리 풀 수 있었을 것 같다.

짜는데 5분도 안걸렸기에...

 

sol)

무방향인게 엄청 중요하다. 결국 같은 집합에 속하면 항상 문제에서 정의하는 사이클대로 돌아올 수 있기 때문이다.

따라서 들어오는 순서대로 merge 해주다가, 같은 집합에 속할때 출력해주면 된다.

 

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int par[500000 + 100], n, m, a, b, ans;
int find(int x) {
	if (par[x] < 0)return x;
	return par[x]=find(par[x]);
}
void merge(int x, int y) {
	x = find(x), y = find(y);
	if (x == y)return;
	par[x] = y;
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	memset(par, -1, sizeof(par));
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		cin >> a >> b;
		if (find(a) == find(b)) {
			cout << i;
			return 0;
		}
		merge(a, b);
	}
	cout << '0';
}

 

F. Escaping(68min)

기령형이 짰다.

대충 아이디어는 같이 구현하고, 거리 기준으로 '잘' 나눠보면 어떻게든 되나 보다.

 

여기까지 짜고 위에 갓갓들의 스코어보드를 봤는데 k,l 위주로 풀려있었다.

그리고 k번은 단순 다익스트라인것 같아서 우선 l 풀고있던 건이에게 컴퓨터 넘겨주고 다른 문제를  봤는데,

그러지 말았어야 했다...  l 번에서 수많은 반례와 함께 계속 몇 번씩 더 틀리고,

그냥 내가 k 잡고 풀었다.

 

K.Road Reconstruction (129min) + 1try

 

좌표 (x,y)에 대해 (x+1,y), (x-1,y), (x,y+1), (x,y-1) 에 대해 각각 가중치가 배열값인 간선을 그어주고 다익스트라 돌리면 된다. -1인 경우엔 inf를 넣어준다.

정말 아쉬웠던 점은... 내가 다익스트라를 완벽히 이해하고 있었다면 디버깅 하느라 20분 정도 버리지는 않았을 것이다. 

priority_queue 까먹고 그냥 queue에 넣어서 한번 TLE난것도 아쉽다.

 

소스코드는 다시 구현하기 귀찮아서 나중에 이 문제 다시 풀때 넣어 놓겠다.(넣었다)

#include<iostream>
#include<algorithm>
#include<queue>
#include<functional>

using namespace std;
using ll = long long;
using P = pair<pair<ll, ll>, ll>;
ll M[1010][1010], n, m, a, b, c, d, x, y, z, k, t;
ll dist[1010][1010], inf = 1234567891234;
vector<P>edge[1010][1010];
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			ll aa;
			cin >> aa;
			if (aa < 0)aa = inf;
			M[i][j] = aa;
			dist[i][j] = inf;
		}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			if (i <= n)
				if (M[i + 1][j])edge[i][j].push_back({ {i + 1,j},M[i+1][j] });
				else edge[i][j].push_back({ {i + 1,j},0 });
			if (i >= 2)
				if (M[i - 1][j])edge[i][j].push_back({ {i - 1,j},M[i-1][j] });
				else edge[i][j].push_back({ {i - 1,j},0 });
			if (j <= m)
				if (M[i][j + 1])edge[i][j].push_back({ {i,j + 1},M[i][j+1] });
				else edge[i][j].push_back({ {i,j + 1},0 });
			if (j >= 2)
				if (M[i][j - 1])edge[i][j].push_back({ {i,j - 1},M[i][j-1] });
				else edge[i][j].push_back({ {i,j - 1},0 });
		}
	priority_queue<P, vector<P>, greater<>> pq;
	dist[1][1] = M[1][1];
	pq.push({ {1,1},dist[1][1] });

	while (pq.size()) {
		auto cur = pq.top();
		pq.pop();
		if (dist[cur.first.first][cur.first.second] < cur.second)continue;
		for (auto nxt : edge[cur.first.first][cur.first.second]) {
			if (cur.second + nxt.second >= dist[nxt.first.first][nxt.first.second])continue;
			dist[nxt.first.first][nxt.first.second] = cur.second + nxt.second;
			pq.push({ {nxt.first.first,nxt.first.second},dist[nxt.first.first][nxt.first.second] });
		}
	}
	if (dist[n][m] == inf)cout << "-1";
	else cout << dist[n][m];
}

 

 

 

 

F번 푼시점부터 거의 건이와 기령형은 l번에 몰빵하고 있었고, 난 k풀고 뭐할지 보다가 h 음수 사이클 문제 해볼만 해 보여서 생각하고 있었다. 그러다 거의 막판에는 우리 팀원 전부 l번 붙잡고 있었는데... 결국 못 풀었다.

 

결국 4솔했고, 목표보다는 약간 못 미치는게 아쉬웠다.

1학년인데 이정도면 됐지... 라는 안일한 마음은 가지지 말아야겠다.

내 실력과 노력이 부족했다.

당장 내 자리 대신에 tourist가 왔다면 혼자 6~7문제 풀지 않았을까...

수고한 내 팀원들에게 미안한 마음이 앞선다.

내년에 이팀과 또 할지는 모르겠지만

내년엔 꼭 예선 통과하고

졸업 전엔 꼭 월파간다...