Good Bye BOJ 2019 후기::::Gratus' Blog

Good Bye BOJ 2019 후기

알고리즘 문제풀이/대회 후기, 문제풀이 2020. 1. 2. 21:31

Good Bye BOJ 2019 대회에 참여해서 15등 했다. 솔직히 딱 풀 수 있는거 다 푼 거고, 그냥저냥 딱 실력만큼 성적 나온 대회인거 같다.

B번에서 놀라운 뇌절을 해서 (처음엔 뇌절이라고 생각도 못 함) 그렇지...

A. 겨울왕국 티켓 예매

단순히 "L열 4번" 이라는 좌석이 존재할 수 있는지만 확인한 다음, 존재 여부에 따라 좌석번호 (L열 4번의 좌석번호) 를 뱉어주면 되는 문제. 1틀한 이유는 "L열" 이 있는지만 확인하고 "4번" 이 있는지 확인 안해서 생긴 일인데, 일일히 확인하진 않았지만 이 똑같은 실수를 한 사람이 꽤 있는거 같다. :(

#include <bits/stdc++.h>
using namespace std;
#define all(x) ((x).begin()),((x).end())

int solve()
{
	int m, n;
	cin >> m >> n;
	int x = 'l'-'a';
	if (m+'a'-1 < 'l' || n < 4)
		return -1;
	else return (x*n+4);
}
int32_t main()
{
	int t;
	cin >> t;
	while(t--)
		cout << solve() << '\n';
}

B. 제야의 종

사람들이 종소리를 들으려고 모인 상황에서, 종소리를 듣는 사람의 위치와 들을 수 있는지 여부가 monotonic, 즉 $A$ 보다 $B$가 종에 가깝다면 $B$ 가 들을 수 있는 종은 $A$의 부분집합이다. 이때 가청여부를 나타낸 행렬을 보고 가능한 배치인지 확인하는 문제.

그냥 모든 $i$, $j$ 페어에 대해서만 확인하면 되는 문제라고 하는데, 그런건지 모르고 뇌절하기 시작했다. $A$ 가 들을 수 있는데 $B$ 가 들을 수 없다면 $A \rightarrow B$ 간선이 있다고 놓고, 그렇게 얻어지는 direct graph 를 위상정렬시도하는 풀이를 시도했다.

구현하면서 무고한 세터를 욕하고 이 대회를 뛰기로 한 스스로를 욕하는 등 많이 빡셌는데, 특히 SNUPC때 위상정렬후 사이클체크 수준의 상황에서 10틀을 해본경험이 있어서 더 그런거 같다. 아무튼 3틀 후 AC

#include <bits/stdc++.h>
using namespace std;
using pii = pair <int, int>;

int able[1010][103];
int n, m;
int graph[1010][1010];
bool visited[1010];
vector <int> sorted;

void dfs(int root)
{
	visited[root] = 1;
	for (int i = 0; i<n; i++)
		if (!visited[i] && graph[root][i])
			dfs(i);
	sorted.push_back(root);
}

int32_t main()
{
	cin >> n >> m;
	for (int i = 0; i<n; i++)
		for (int j = 0; j<m; j++)
			cin >> able[i][j];
	for (int i = 0; i<m; i++)
	{
		for (int j = 0; j<n; j++)
		{
			for (int k = 0; k<n; k++)
			{
				if (able[j][i] && !able[k][i])
					graph[j][k] = true;
				else if (!able[j][i] && able[k][i])
					graph[k][j] = true;
			}
		}
	}
	for (int i = 0; i<n; i++)
		if (!visited[i])
			dfs(i);
	reverse(sorted.begin(),sorted.end());
	for (int i = 0; i<n; i++)
	{
		for (int j = i+1; j<n; j++)
		{
			if (graph[sorted[j]][sorted[i]])
			{
				cout << "NO\n";
				return 0;
			}
		}
	}
	cout << "YES\n";
}

재밌는 것중 하나는, 이 풀이의 시간 복잡도는 무려 $O(mn^2)$ 으로 1억이기 때문에 ~~무고한 세터를 두번 욕하며~~ 믿음을 가지고 코딩했었다.

C. 욱제가 풀어야 하는 문제

이미 대회가 망했다고 생각하고 (이때까지도 내 생각에 이 대회는 B번에 위상정렬 + 그래프로 모델링하는 문제를 낸 구데기 대회다!) 풀었는데 그래도 쉬웠다.

간단한 관찰로 피보나치라는 믿음을 가지면 OK.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define all(x) ((x).begin()),((x).end())
#define int ll
const int mod = 1000000007;
int dp[202020];

int32_t main()
{
	usecppio
	dp[1] = 1;
	dp[2] = 2;
	for (int i = 3; i<=200000; i++)
	{
		dp[i] = dp[i-2] + dp[i-1];
		dp[i] %= mod;
	}
	int t;
	cin >> t;
	for (int i = 0; i<t; i++)
	{
		int n; cin >> n;
		cout << dp[n] << '\n';
	}
}

D. 철도 여행

문제를 요약하면, 한붓그리기 (Eulerian path) 몇개로 이 그래프의 에지를 전부 돌아볼 수 있는가 하는 문제이다. 잘 알려진 사실로, Connected component에서 이 값은 Odd degree 를 가진 Edge 개수의 절반과 같으며, 이 값이 0일 경우 1임이 알려져 있다. 그대로 구현해서, 각 Connected component 별로 DFS를 돌리면서 Odd degree 인 점의 개수를 세서 더하면 된다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using pii = pair <int, int>;
#define int ll
vector <int> graph[201010];
int cc[202020];
int deg[202020];
int octs[202020];
int n, m;
bool vst[202020];
void dfs(int r, int ccp)
{
	vst[r] = true;
	cc[r] = ccp;
	for (auto it:graph[r])
		if (!vst[it])
			dfs(it, ccp);
}
int32_t main()
{
	usecppio
	cin >> n >> m;
	for (int i = 0; i<m; i++)
	{
		int u, v;
		cin >> u >> v;
		graph[u].push_back(v);
		graph[v].push_back(u);
		deg[u]++;
		deg[v]++;
	}
	int ct = 0;
	for (int i = 1; i<=n; i++)
	{
		if(!vst[i] && (deg[i]>0))
		{
			ct++;
			dfs(i, ct);
		}
	}
	for (int i = 1; i<=n; i++)
		if (deg[i]%2)
			octs[cc[i]] ++;
	int ans = 0;
	for (int i = 1; i<=ct; i++)
		ans += (octs[i]==0?1:octs[i]/2);
	cout << ans << '\n';
}

E. 내 생각에 A번인 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy)

그래서 Hard는 어디 갔지...;;;

트리를 중위순회해서 번호를 매기면, 트리 정점들의 $x$좌표 순서대로 나타내게 된다는 사실을 먼저 관찰해야 한다.

그렇게 하고 나면, 어떤 2차원 공간에 점이 잘 찍혀 있는 상황에서 여기에 적절하게 직사각형을 그려서 안에 든 수들의 합을 최대화하는 문제로 바뀌게 된다. (또 금광이 아닌 문제를 금광 easy 라고 부르고 있던데, ICPC때 얘기 들었던 KOI 금광이 그냥 일반적인 경우에 2차원 공간에서 직사각형 그려서 최대화하는 문제이기 때문이다.)

아무튼, 이 문제는 금광과는 달리 높이가 log n, 즉 최대 18 정도임이 주어져 있다.

높이가 이처럼 제한된 경우에는, 세로를 먼저 고정하고 나서 그 문제를 빠르게 해결할 수 있는지 여부를 생각하는 것이 도움이 된다. 즉, 최대 가능한 세로 (어디부터 어디까지) 가 수백 개 정도로 많이 제한되어 있으므로 세로를 고정한 상태에 수백만 이하의 연산으로 (Reasonably fast) 문제를 해결할 수 있으면 전체 문제도 빠르게 해결할 수 있다.

세로를 고정하고 나면, 우리가 고려할 수 있는 점들이 잘 제한된다. 즉, 어떤 점들을 고려하고 어떤 점들을 고려하지 않아야 하는지가 명확하다. 따라서, 결국 $N$ 개의 점들 중 골라져 나온 점들에 대해 빠르게 최대 값을 얻는 직사각형을 고를 수 있는지 문제이고, 이는 다시 Maximum sum subarray 문제이며 Kadane's Algorithm을 이용해 $O(n)$ 에 풀 수 있음이 알려져 있다.

시간 복잡도는 $O(n \log^2 n)$ 처럼 보이지만, 실제로는 $\log^2 n$ 개 전부 $O(n)$ 개의 점을 보는게 아니라 그보다 적은 점개수만 확인하는 케이스들이 많이 있어서 실제로 계산해보면 $O(n \log n)$ 이라고 한다. 어차피 $n \log^2 n$ 도 시간 안에 잘 돌아갈 복잡도라서 크게 신경은 안 썼지만....

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using pii = pair <int, int>;
#define int ll
int rearr[303030];
int tree[303030];
int n, pt;
int ans;
vector <int> visitorder;
vector <int> tmp;
int kadane(vector <int> &arr)
{
	int nn = arr.size();
	int lm = arr[0], gm = arr[0];
	for (int i = 1; i<nn; i++)
	{
		lm = max(arr[i], lm+arr[i]);
		gm = max(gm, lm);
	}
	return gm;
}
void order(int root)
{
	if (root > n/2) visitorder.push_back(root);
	else
	{
		order(root*2);
		visitorder.push_back(root);
		order(root*2+1);
	}
}

void recmax(int lo, int hi)
{
	tmp.clear();
	int locrit = (1 << lo);
	int hicrit = (1 << hi);
	for (int i = 1; i<=n; i++)
		if (i%locrit == 0 && i%hicrit != 0)
			tmp.push_back(rearr[i]);
	ans = max(ans, kadane(tmp));
}
int32_t main()
{
	usecppio
	cin >> n;
	for (int i = 1; i<=n; i++)
		cin >> tree[i];
	order(1);
	for (int i = 1; i<=n; i++)
		rearr[i] = tree[visitorder[i-1]];
	int mlev = 0;
	for (int i = 0; i<30; i++)
	{
		if ((1<<i) == n+1)
		{
			mlev = i; break;
		}
	}
	for (int i = 0; i<mlev; i++)
		for (int j = i+1; j<=mlev; j++)
			recmax(i, j);
	int nmax = -INT_MAX;
	for (int i = 1; i<=n; i++)
		nmax = max(nmax, rearr[i]);
	if (nmax < 0)
		cout << nmax << '\n'; return 0;
	else cout << max(ans, nmax) << '\n';
}

F. 별이 빛나는 밤에

필요한 관찰과 나름의 기하적인 확신을 가지고 코딩을 시작했지만 중간에 코딩에 실패했다. 구현이 조금 빡세긴 했는데, 기하 문제 풀이 자체를 많이 안 해서 그런것도 있는거 같다.

레일 (선분) 이 주어지고, 이 선분들에 한 선분당 한 점씩 놔서, 만들 수 있는 삼각형들 중 넓이의 최댓값을 최소화하는 문제. 맨 위와 아래에 있는 두 점은 움직일 수 없다.

기하적으로 적당히 생각을 해보면, 최선의 경우는 맨 위와 아래 점을 이은 선분을 절대 건드릴 수 없으므로 이 선분에 최대한 가깝게 붙이는 것이 최선이라는 생각이 들었다. 실제로 몇개 생각해 봐도 당연히 맞는거 같고, 귀류법처럼 생각해서 머리를 굴려 봐도 실제로 그게 최선인거 같았기 때문에 나름 확신을 가지고 짰는데 실패했다.

아무튼, 직선에 점을 최대한 가깝게 붙이는 거야 쉽고, 그다음은 $n$ 개의 점으로 만들 수 있는 최대 삼각형의 넓이를 실제로 구해야 한다. 이러한 과정은 Convex Hull 을 먼저 $O(n \log n)$ 에 구하고 나면 $O(n^2)$ 에 수행 가능한 과정임이 알려져 있다.

이렇게 전체 문제를 $O(n^2)$ 에 풀 수 있다.

무려 200줄이므로 링크로 대체.

http://boj.kr/4db831dcdc864ed69afb6ef515d75877

한해 PS를 정리하는 기분으로 나름 재밌게 참여했다. :)

저작자표시

'알고리즘 문제풀이 > 대회 후기, 문제풀이' 카테고리의 다른 글

Google Codejam 2020 Round 1B 1, 2번 풀이 (3)	2020.04.20
Google Hash Code 2020 후기 (0)	2020.02.21
ICPC Seoul Regional 2019 (Online Mirror) (2)	2019.11.10
2019 ICPC 인터넷 예선 후기 (0)	2019.10.07
서울대학교 프로그래밍 경시대회 (SNUPC) Division 2 후기 (0)	2019.09.08

Gratus' Blog