ls-al.me hello, world!

SCPC 2017 Onsite Final

작년보다 부대행사는 줄고 참가자 혜택은 늘어나서 즐거웠다. 입상을 못 해도 받을 수 있는 키보드가 마음에 들어 가벼운 마음으로 대회에 임했다.

200: Vowels

주어진 문자열에서 a, e, i, o, u가 차례대로 등장하는 가장 짧은 부분문자열을 찾는 문제이다. 다양한 방법이 있지만 문자열의 길이가 최대 으로 넉넉해 안쪽으로 아무 방법이나 활용해 풀면 된다. 120여명 중 3명을 제외하고 전부 풀었다고 하니 0점방지용 문제인 것 같다.

#include <stdio.h>

const int N = 1000 + 10;

char pat[] = "aeiou";
char str[N];

int main() {
	int tc;
	scanf("%d", &tc);
	for (int t = 1; t <= tc; t++) {
		int n;
		scanf("%d", &n);
		scanf("%s", str);
		int rs = -1, rt = -1;
		for (int i = 0; i < n; i++) {
			int j = i;
			int k;
			for (k = 0; k < 5; k++) {
				for (; j < n && str[j] != pat[k]; j++);
				if (j == n) {
					break;
				}
			}
			if (k == 5) {
				if (rs == -1 || j - i < rt - rs) {
					rs = i + 1;
					rt = j + 1;
				}
			}
		}
		printf("Case #%d\n", t);
		printf("%d %d\n", rs, rt);
	}
	return 0;
}

300: Bridge

2차원 평면에서 두 개의 서로 겹치지 않는 볼록다각형이 주어질 때, 두 다각형 사이의 가장 짧은 거리를 구하는 문제이다.

문제는 매우 간단하고 주어지는 도형이 볼록다각형이므로 적절한 처리를 하면 쉽게 풀릴 수 있는 문제지만 기하 문제가 대개 그렇듯 선뜻 코딩을 시작하기 어려웠다. 간단히 해결할 수 있는 방법이 떠오르지 않아 다음 문제를 먼저 풀었고 결국 rotating calipers를 두 다각형에서 동시에 수행하는 방식으로 접근했다. 두 다각형이 겹치지 않으므로 두 다각형 사이의 최단거리에 해당하는 두 지점에 서로 평행한 접선을 그을 수 있을 것이고 이를 rotating calipers로 포착하고자 했는데, edge case를 포함한 모든 경우의 수를 다 확인한다는 확신을 갖기 어려워 최대한 많은 점-선분 쌍 간의 거리를 비교하도록 적절히 구현했다. Rotating calipers의 시간복잡도는 이므로 거리비교를 몇 배쯤 더 한다고 해도 별다른 무리가 없으리라는 계산이다.

제출하는 과정에서 다소 억울하게 WA를 받았는데, CodeGround 사이트에서 컴파일러를 선택하던 중 실수로 C++11을 선택한 뒤 코드를 붙여넣었고, C++14를 선택하고 제출버튼을 눌러 C++14의 템플릿 코드가 제출되었다. 예선 중에도 같은 실수를 한 번 했던 기억인데, 바람직하지 않은 UI의 전형이 아닌가 생각해 본다.

#include <stdio.h>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 200000 + 10;
const double P = 3.1415926535897932384626433832795;
const double E = 1e-14;
const double M = 1e14;

pair<double, double> pt[2][N];

bool eq(double x, double y) {
	return abs(x - y) < E;
}

double atan(pair<double, double> &a, pair<double, double> &b) {
	double r = atan2(b.second - a.second, b.first - a.first);
	if (r < 0) {
		r += P;
	}
	if (eq(r, P)) {
		r = 0.0;
	}
	return r;
}

double diff(double from, double to) {
	double d = to - from;
	if (eq(d, 0.0)) {
		return 0.0;
	}
	else if (d < 0) {
		return d + 2.0 * P;
	}
	return d;
}

double dist(pair<double, double> &x, pair<double, double> &y) {
	return sqrt(pow(x.first - y.first, 2.0) + pow(x.second - y.second, 2.0));
}

double dist(pair<double, double> &x, pair<double, double> &p, pair<double, double> &q) {
	double r = min(dist(x, p), dist(x, q));
	if (eq(p.first, q.first)) {
		if (min(p.second, q.second) < x.second && x.second < max(p.second, q.second)) {
			r = min(r, abs(x.first - p.first));
		}
	}
	else if (eq(p.second, q.second)) {
		if (min(p.first, q.first) < x.first && x.first < max(p.first, q.first)) {
			r = min(r, abs(x.second - p.second));
		}
	}
	else {
		double sp = (p.second - q.second) / (p.first - q.first);
		double sx = -1.0 / sp;
		double cx = ((x.second - x.first *  sx) - (p.second - p.first * sp)) / (sp - sx);
		pair<double, double> c = make_pair(cx, x.second + (cx - x.first) * sx);
		if (min(p.first, q.first) < cx && cx < max(p.first, q.first)) {
			r = min(r, dist(x, c));
		}
	}
	return r;
}

int main() {
	int tc;
	scanf("%d", &tc);
	for (int t = 1; t <= tc; t++) {
		int n[2], mini[2] = { -1, -1 }, maxi[2] = { -1, -1 };
		scanf("%d %d", &n[0], &n[1]);
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < n[i]; j++) {
				scanf("%lf %lf", &pt[i][j].first, &pt[i][j].second);
				if (mini[i] == -1 || pt[i][j].second < pt[i][mini[i]].second) {
					mini[i] = j;
				}
				if (maxi[i] == -1 || pt[i][maxi[i]].second < pt[i][j].second) {
					maxi[i] = j;
				}
			}
		}
		int pi[2][2] = { { mini[0], maxi[0] }, { mini[1], maxi[1] } };
		double la = 0.0;
		double r = M;
		for (int k = 0; k < (n[0] + n[1]) * 2; k++) {
			int mi = -1, mj = -1;
			double ma;
			double zy[2][2];
			for (int i = 0; i < 2; i++) {
				for (int j = 0; j < 2; j++) {
					auto &p = pt[i][pi[i][j]];
					int ni = (pi[i][j] + 1) % n[i];
					double na = atan(p, pt[i][ni]);
					if (mi == -1 || diff(la, na) < diff(la, ma)) {
						mi = i, mj = j, ma = na;
					}

					if (eq(la, P / 2.0) || eq(la, -P / 2.0)) {
						zy[i][j] = p.first;
					}
					else {
						zy[i][j] = p.second - tan(la) * p.first;
					}
				}
			}
			int ni = (pi[mi][mj] + 1) % n[mi];
			la = ma;
			bool flag = false;
			int a[2];
			if (max(zy[0][0], zy[0][1]) < min(zy[1][0], zy[1][1])) {
				a[0] = zy[0][0] < zy[0][1] ? 1 : 0;
				a[1] = zy[1][0] < zy[1][1] ? 0 : 1;
				flag = true;
			}
			if (min(zy[0][0], zy[0][1]) > max(zy[1][0], zy[1][1])) {
				a[0] = zy[0][0] > zy[0][1] ? 1 : 0;
				a[1] = zy[1][0] > zy[1][1] ? 0 : 1;
				flag = true;
			}
			if (flag) {
				pair<double, double> p[2][5];
				for (int i = 0; i < 2; i++) {
					for (int j = 0; j < 5; j++) {
						p[i][j] = pt[i][(pi[i][a[i]] + n[i] + j - 2) % n[i]];
					}
				}
        double m0 = dist(p[0][2], p[1][0], p[1][1]);
				double m1 = dist(p[1][2], p[0][0], p[0][1]);
				double m2 = dist(p[mi][2], p[1 - mi][0], p[1 - mi][1]);
				for (int i = 1; i < 3; i++) {
					m0 = min(m0, dist(p[0][2], p[1][i], p[1][i + 1]));
					m1 = min(m1, dist(p[1][2], p[0][i], p[0][i + 1]));
					m2 = min(m2, dist(p[mi][2], p[1 - mi][i], p[1 - mi][i + 1]));
				}
				r = min(r, min(m0, m1));
				r = min(r, m2);
			}
			pi[mi][mj] = ni;
		}
		printf("Case #%d\n", t);
		printf("%.10lf\n", r);
	}
	return 0;
}

450: Colony

두 탐사선 A와 B가 주어진 스케쥴대로 2차원 공간을 오가고, 그 과정에서 A에서 B가 방문했거나 방문할 예정인 위치로 메신저를 발사해 B가 받아볼 수 있도록 하려고 한다. 이 때 B가 메신저를 받아 볼 수 있는 가장 빠른 시간을 구하는 문제이다.

메신저의 도달시간이 두 지점의 Manhattan distance로 결정되기 때문에 도달 가능 지역은 마름로로 표현된다. 좌표평면 로 변환하는 잘 알려진 트릭을 활용하면 이를 정사각형으로 바꿔 생각할 수 있다. B가 메신저를 받아 보는 시간을 미리 정해놓으면 메신저가 도달 가능한 위치는 A의 각 시간대별 위치를 중심으로 하는 여러 정사각형의 합집합이 되고, 이 안에 B의 해당 시간 이전의 위치가 있는지를 확인하는 전략으로 parametric search를 할 수 있다.

문제는 개의 정사각형과 개의 점이 주어졌을 때 정사각형 안에 속하는 점이 있는지를 빠른 시간 안에 알아내야 하는데, 의도한 풀이는 plane sweeping이었던 것 같지만 생각해 내지 못했다. 대신 2차원 평면에 대한 segment tree를 구성하는 방식으로 접근했고, 로 비교적 넉넉해 시간에 검사를 하는 것으로 해결이 되었다. 전체 공간에 비해 점의 개수가 매우 적다는 점을 고려해 실제 구현에서는 x축과 y축을 동시에 분할하는 방식의 quaternary segment tree를 사용했다.

Plane sweeping을 생각해내지 못한 부분이나 시간복잡도상 불리한 quaternary segment tree를 사용하기로 한 부분에서 실력이 부족했음을 느낀다. 운 좋게 대회 중에 해결한 문제.

#include <stdio.h>

const int N = 100000 + 10;

const long long S = -(1ll << 31);
const long long L = 1ll << 32;

int n;

long long pt[N][4];

class Node {
	int cnt;
	Node *ptr[2][2];

public:
	Node() {
		cnt = 0;
		for (int tx = 0; tx < 2; tx++) {
			for (int ty = 0; ty < 2; ty++) {
				ptr[tx][ty] = NULL;
			}
		}
	}

	~Node() {
		for (int tx = 0; tx < 2; tx++) {
			for (int ty = 0; ty < 2; ty++) {
				if (ptr[tx][ty] != NULL) {
					delete ptr[tx][ty];
				}
			}
		}
	}

	void set(long long sx, long long sy, long long l, long long ptx, long long pty, int c) {
		cnt += c;
		if (1 < l) {
			l >>= 1;
			int tx = sx + l <= ptx, ty = sy + l <= pty;
			if (ptr[tx][ty] == NULL) {
				ptr[tx][ty] = new Node();
			}
			ptr[tx][ty]->set(sx + tx * l, sy + ty * l, l, ptx, pty, c);
		}
	}

	bool get(long long sx, long long sy, long long l, long long psx, long long psy, long long pl) {
		if (cnt == 0) {
			return false;
		}
		if (psx <= sx && sx + l <= psx + pl && psy <= sy && sy + l <= psy + pl) {
			return true;
		}
		l >>= 1;
		bool x[2], y[2];
		x[0] = psx < sx + l;
		x[1] = sx + l < psx + pl;
		y[0] = psy < sy + l;
		y[1] = sy + l < psy + pl;
		int s = 0;
		for (int tx = 0; tx < 2; tx++) {
			if (!x[tx]) continue;
			for (int ty = 0; ty < 2; ty++) {
				if (!y[ty]) continue;
				if (ptr[tx][ty] != NULL) {
					if (ptr[tx][ty]->get(sx + tx * l, sy + ty * l, l, psx, psy, pl)) {
						return true;
					}
				}
			}
		}
		return false;
	}
};

bool check(Node *head, int &d, int r) {
	for (int i = r + 1; i < d; i++) {
		head->set(S, S, L, pt[i][2], pt[i][3], -1);
	}
	for (int i = d; i < r + 1; i++) {
		head->set(S, S, L, pt[i][2], pt[i][3], 1);
	}
	d = r + 1;
	for (int i = 0; i <= r; i++) {
		int l = r - i;
		if (head->get(S, S, L, pt[i][0] - l, pt[i][1] - l , l * 2 + 1)) {
			return true;
		}
	}
	return false;
}

int main() {
	int tc;
	setbuf(stdout, NULL);
	scanf("%d", &tc);
	for (int t = 1; t <= tc; t++) {
		scanf("%d", &n);
		for (int i = 0; i < n; i++) {
			long long dt[4];
			for (int j = 0; j < 4; j++) {
				scanf("%lld", &dt[j]);
			}
			pt[i][0] = dt[0] + dt[1];
			pt[i][1] = dt[0] - dt[1];
			pt[i][2] = dt[2] + dt[3];
			pt[i][3] = dt[2] - dt[3];
		}
		int s = 0, e = n;
		Node head;
		int d = 0;
		while (1 < e - s) {
			int m = (s + e) / 2;
			if (check(&head, d, m - 1)) {
				e = m;
			}
			else {
				s = m;
			}
		}
		printf("Case #%d\n", t);
		if (check(&head, d, s)) {
			printf("%d\n", s + 1);
		}
		else {
			printf("%d\n", -1);
		}
	}
	return 0;
}

550: 방 바꾸기

설명이 길고 장황하지만 잘 살펴보면 주어진 cactus-ish graph 위에서 푸는 sliding puzzle 내지는 파즈도라 문제이다.

문제는 일단 이해하면 그렇게 복잡하지 않고 풀이를 떠올리기도 어렵지 않다. 빈 칸에 해당하는 노드를 움직이는 문제로 생각하면, 어차피 시작점에서 도착점까지 가는 경로에는 선택의 여지가 없고, 그 과정에서 들리는 사이클에서 어떻게 행동할지가 중요하다. 사이클을 지나쳐 가거나 도로 나가는 경우 그 안에서 여러 바퀴를 돎으로서 사이클의 구성원을 회전시킬 수 있기 때문에 원하는 상태가 되도록 잘 조절하는 최단경로를 구해야 한다.

다만 수많은 예외들을 한 치의 오차도 없이 처리해야 만점을 기대할 수 있는 문제인 만큼 대회 중에는 맨 정신으로 해결이 불가능할 것임을 직감했고, 대회가 끝날때까지 단 두명만이 문제를 해결하면서 직감이 옳았음을 확인했다. 다른 세 문제를 해결하고 나니 시간도 넉넉하지 않아 가장 쉬운 부분점수를 확보하는데 그쳤다.

Epiloge

두 번째 문제와 세 번째 문제는 거의 요행으로 만점이 나왔다고 생각한다. 문제를 풀면서도 세 문제를 풀고 마지막 문제에서 부분점수를 받으면 최선이겠다는 생각을 했는데 실제로 나올 수 있는 가장 좋은 성적이 나온 것 같다. 다만 온라인 예선은 비교적 난이도가 있다고 느껴졌던 것에 비해 오히려 본선 문제가 변별력이 떨어진 감이 없잖아 있는데, 나랑 같은 점수인 참가자들이 많았고 점수 다음 기준인 제출횟수에 따라 등위가 갈렸다고 한다. 사람 마음인지라 아쉬울 수밖에 없다.

대회 운영이 전반적으로 디테일하다고 느꼈다. 급조한게 분명함에도 퀄리티 있는 비디오라던지, 군더더기 없으면서도 알찬 사후 행사라던지, 딱히 칭찬해달라고 부탁받아서 하는 이야기는 아니지만 수상자 회식이라던지, 긍정적인 변화이다. 앞으로도 이런 기회가 계속 확대되었으면 한다.