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

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

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

SCPC 2017 R2

생각보다 많은 삽질을 했지만 문제 내용이 알찼다. 대회 직후에 문제와 풀이를 공식적으로 공개하기를 계속해서 바래 본다.

100: Hanoi

하노이 탑 문제에서 주어진 상태가 문제를 해결하는 최적의 경로에서 등장하는지 여부를 구하면 된다. 일반적인 하노이 탑 문제와 다른 점은, A, B, C 세 개의 기둥에서 각각 A에서 B로, B에서 C로, C에서 A로만 디스크를 옮길 수 있다는 점이다. 즉, A기둥에서 C기둥으로 디스크를 옮기기 위해서는 B기둥을 한번 거쳐야 한다.

하노이 탑 문제를 푸는 것은 어렵지 않은데, 일반적인 풀이 - 개의 디스크를 A에서 B로 옮기기 위해 개의 디스크를 A에서 C로 옮기고, 번 디스크를 A에서 B로 옮기고, 개의 디스크를 다시 C에서 B로 옮기는 - 를 그대로 적용하되 필요한 경우 다른 디스크를 거쳐가도록 하면 되며 이것이 유일한 최적의 방법임을 증명하기는 어렵지 않다. 여기서 주어진 상태가 등장하는지를 구하는 것 역시 가장 아래 디스크부터 시작해 현재 디스크 무더기를 옮기고 있는 출발지와 도착지를 유추해가며 판단하면 된다. 주어진 상태가 풀이 과정에서 등장하지 않는 유일한 경우는 디스크가 경유할 필요가 없는 기둥에서 발견되는 경우이다.

#include <stdio.h>

const int N = 1000000 + 10;

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 from = 0, to = 1, i;
    for (i = n - 1; 0 <= i; i--) {
      int now = str[i] - 'A';
      if ((from + 1) % 3 == to) {
        if (now == from) {
          from = now;
          to = (now + 2) % 3;
        } else if (now == (from + 1) % 3) {
          from = (now + 1) % 3;
          to = now;
        } else {
          break;
        }
      } else if ((from + 2) % 3 == to) {
        if (now == from) {
          from = now;
          to = (now + 2) % 3;
        } else if (now == (from + 1) % 3) {
          from = (now + 1) % 3;
          to = (now + 2) % 3;
        }
        else {
          from = (now + 1) % 3;
          to = now;
        }
      } else {
        break;
      }
    }
    printf("Case #%d\n", t);
    if (0 <= i) {
      printf("NO\n");
    } else {
      printf("YES\n");
    }
  }
  return 0;
}

150: 오래달리기

명의 선수마다 속도, 트랙의 길이, 출발 위치가 주어질 때 모든 선수가 원형 트랙의 출발점에 도착하는 가장 빠른 자연수 시간 를 구하면 된다.

선수 의 속도, 트랙의 길이, 출발 위치를 각각 , , 라고 할 때, 모든 에 대해 다음이 성립한다:

가 서로소라고 가정하고 이를 조금 변형하면:

여기서 를 제외한 모든 항이 주어지므로 중국인의 나머지 정리를 활용해 가장 작은 자연수 를 구할 수 있다.

주의해야 할 점이 크게 두 가지가 있는데, 첫째는 모든 가 0인 경우로 들의 최소공배수를 출력해야 하는 점이며, 둘째는 주어진 중 서로소가 아닌 쌍이 있을 경우 이를 정규화해야 한다는 점이다. 후자를 해결하면서 많은 실수를 했는데, 결국 모든 를 소인수분해했다.

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

const int L = 1000;

long long nmod(long long x, long long m) {
  if (x < 0) {
    x += ((-x) / m) * m + m;
  }
  return x % m;
}

pair<long long, long long> egcd(long long a, long long b) {
  if (a == 0) {
    return make_pair(0, 1);
  }
  pair<long long, long long> t = egcd(b % a, a);
  return make_pair(t.second - (b / a) * t.first, t.first);
}

long long modinv(long long a, long long m) {
  return nmod(egcd(a, m).first, m);
}

long long crt(vector<long long> &q, vector<long long> &r) {
  long long c = 1;
  for (auto x : r) {
    c *= x;
  }
  long long x = 0;
  for (auto qt = q.begin(), rt = r.begin(); qt != q.end() && rt != r.end(); qt++, rt++) {
    long long a = nmod((*qt) * modinv(c / (*rt), *rt), *rt);
    x = nmod(x + a * (c / (*rt)), c);
  }
  return x;
}

long long gcd(long long a, long long b) {
  if (a == 0) {
    return b;
  }
  return gcd(b % a, a);
}

int main() {
  vector<long long> primes;
  for (int i = 2; i <= L; i++) {
    int j;
    for (j = 0; j < primes.size() && i % primes[j] != 0; j++);
    if (j == primes.size()) {
      primes.push_back(i);
    }
  }
  int tc;
  scanf("%d", &tc);
  for (int t = 1; t <= tc; t++) {
    int n;
    scanf("%d", &n);
    map<long long, pair<long long, long long> > cnt;
    for (int i = 0; i < n; i++) {
      long long s, l, d;
      scanf("%lld %lld %lld", &s, &l, &d);
      long long g = gcd(gcd(l, d), s);
      s /= g, l /= g, d /= g;
      long long q = nmod(modinv(s, l) * (l - d), l);
      for (int p : primes) {
        long long j;
        for (j = 1; l % p == 0; l /= p, j *= p);
        if (j == 1) {
          continue;
        }
        if (cnt.find(p) == cnt.end() || cnt[p].first < j) {
          cnt[p] = make_pair(j, q % j);
        }
      }
    }
    vector<long long> q, r;
    for (auto &kv : cnt) {
      r.push_back(kv.second.first);
      q.push_back(kv.second.second);
    }
    long long v = crt(q, r);
    if (v == 0) {
      v = 1;
      for (auto x : r) {
        v *= x;
      }
    }
    printf("Case #%d\n", t);
    printf("%lld\n", v);
  }
  return 0;
}

200: Divisor

주어진 수열에 대해, 수열의 일부 구간과 자연수 가 주어질 때 의 약수들 중 수열의 수를 하나도 나누지 못하는 수의 개수를 구하는 질의가 여럿 주어진다. 정리하자면 각 질의마다 주어진 수의 약수의 집합에 주어진 구간의 수들의 약수들의 합집합을 뺀 차집합의 크기를 구하면 된다. 시간제한이 10초로 매우 넉넉하다.

풀이는 어렵지 않지만 대회 중 생각해내지 못했다. 주어진 수열에 대해 binary indexed tree를 구성하되, 각 노드가 해당 구간의 수들의 약수의 합집합을 나타내는 일종의 merge sort tree를 구성하면 된다. 다만 이 방법으로 시간은 아슬아슬하게나마 주어진 제한을 만족시킬 수 있으나 메모리가 부족할 수 있겠다는 생각을 하는데, 약수의 개수가 흔히 생각하는 것보다는 적겠지만 그 합집합을 여러차례 중복해서 유지해야 하는 만큼 결코 넉넉하지는 않을 것 같다.

250: 중심

주어진 가중치 트리 에서 의 부분트리 에 대해 에 속하는 정점에서 에 속하지 않는 정점까지의 최단거리의 최댓값을 최소화하도록 을 고르려고 한다. 쉽게 말해서 를 적절히 잘 커버하는 개의 정점을 잘 골라내서 가장 먼 정점까지의 거리를 최소화하라는 것인데, 이 연결된 부분트리리를 구성해야 하므로 의 중심에 가까운 어딘가에 위치해야 한다는 점을 유추할 수 있다. 이러한 부분트리 이라고 부른다고 한다.

다음 lemma를 이용하면 문제를 쉽게 해결할 수 있다:

증명은 귀류법을 이용하여 을 포함하지 않는 에서 가장 먼 정점까지의 거리가 에서 가장 먼 정점까지의 거리보다 멀거나 같음을 보이면 된다. 을 포함하도록 을 잡는 쪽이 항상 손해가 아니기 때문에 모든 에 대해 을 포함하는 이 항상 존재한다.

답을 계산할때는 먼저 을 구하고, 해당 정점을 기준으로 가장 먼 정점까지의 거리가 가장 먼 개의 정점을 추가로 선택하면 된다. 에 속하는 정점을 하나 정하고 시작하기 때문에 각 정점에서 가장 먼 정점까지의 거리를 만에 구할 수 있다.

다만 가 최대 이기 때문에 재귀함수를 이용해 DFS를 수행하면 stack overflow가 발생한다. 처음부터 이를 염두에 두지 못한 바람에 재귀함수를 사용하지 않는 방향으로 DFS를 구현하도록 수정하느라 코드의 가독성이 대폭 희생되었다.

#include <stdio.h>
#include <algorithm>
#include <list>
#include <tuple>
#include <stack>

const int N = 100000 + 10;

using namespace std;

long long dist[N];
long long rdist[N];
long long mdist[N];

list<pair<int, long long> > lnk[N];

void calc_dist(int now, int par) {
  stack<tuple<int, int, list<pair<int, long long> > ::iterator> > stk;
  stk.push(make_tuple(now, par, lnk[now].begin()));
  while (!stk.empty()) {
    auto &ctx = stk.top();
    int now = get<0>(ctx);
    list<pair<int, long long> > ::iterator &it = get<2>(ctx);
    if (it == lnk[now].end()) {
      dist[now] = 0;
      for (auto p : lnk[now]) {
        if (p.first == get<1>(ctx)) {
          continue;
        }
        rdist[p.first] += p.second;
        dist[now] = max(dist[now], rdist[p.first]);
      }
      rdist[now] = dist[now];
      stk.pop();
      continue;
    }
    if (it->first == get<1>(ctx)) {
      it++;
      continue;
    }
    stk.push(make_tuple(it->first, now, lnk[it->first].begin()));
    it++;
  }
}

void aggr_dist(int now, int par, long long pdist) {
  stack<tuple<int, int, long long, int, long long, int, list<pair<int, long long> > ::iterator> > stk;
  stk.push(make_tuple(now, par, pdist, now, 0, -1, lnk[now].begin()));
  while (!stk.empty()) {
    auto &ctx = stk.top();
    int now = get<0>(ctx);
    long long &v1 = get<2>(ctx), &v2 = get<4>(ctx);
    int &i1 = get<3>(ctx), &i2 = get<5>(ctx);
    list<pair<int, long long> > ::iterator &it = get<6>(ctx);
    if (it == lnk[now].begin()) {
      mdist[now] = max(dist[now], get<2>(ctx));
      for (auto p : lnk[now]) {
        if (p.first == get<1>(ctx)) {
          continue;
        }
        long long v = dist[p.first] + p.second;
        if (v1 < v) {
          v2 = v1;
          i2 = i1;
          v1 = v;
          i1 = p.first;
        } else if (i2 == -1 || v2 < v) {
          v2 = v;
          i2 = p.first;
        }
      }
    }
    if (it == lnk[now].end()) {
      stk.pop();
      continue;
    }
    if (it->first == get<1>(ctx)) {
      it++;
      continue;
    }
    if (i1 == it->first) {
      stk.push(make_tuple(it->first, now, v2 + it->second, now, 0, -1, lnk[it->first].begin()));
    } else {
      stk.push(make_tuple(it->first, now, v1 + it->second, now, 0, -1, lnk[it->first].begin()));
    }
    it++;
  }
}

int main() {
  int tc;
  scanf("%d", &tc);
  for (int t = 1; t <= tc; t++) {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
      lnk[i].clear();
    }
    for (int i = 1; i < n; i++) {
      int x, y;
      long long w;
      scanf("%d %d %lld", &x, &y, &w);
      x--, y--;
      lnk[x].push_back(make_pair(y, w));
      lnk[y].push_back(make_pair(x, w));
    }
    calc_dist(0, -1);
    aggr_dist(0, -1, 0);
    int mi = 0;
    for (int i = 1; i < n; i++) {
      if (mdist[i] < mdist[mi]) {
        mi = i;
      }
    }
    calc_dist(mi, -1);
    sort(rdist, rdist + n, greater<long long>());
    int p;
    scanf("%d", &p);
    rdist[n] = 0;
    printf("Case #%d\n", t);
    printf("%lld\n", rdist[p]);
  }
  return 0;
}

300: 자석

1차원 공간에 여러 막대들이 겹쳐 있을 때, 모든 막대에 대해 자기 자신 혹은 겹쳐있는 막대 중 최소 하나 이상이 포함되도록 최소한의 막대를 고르면 된다. 겹쳐 있는 막대를 그래프로 표현하면 Mincost-Maxflow 문제가 되지만 막대가 최대 개 존재하기 때문에 제한시간을 초과하게 된다. 막대들이 1차원 공간에 있음을 이용해 적절한 DP를 수행하면 된다고 한다.

SCPC 2017 R1

올해도 찾아온 대회. 작년에 비해 전체적인 난이도가 상승했다고 느꼈다. 대회가 끝나고 문제가 닫혀버린 바람에 기억에 의지해서 작성해 본다.

100: 괄호

세 가지 종류의 괄호로 이루어진 문자열이 주어질 때 올바른 괄호인 부분분자열의 최대 길이를 구해야 한다.

첫 문제인데다가 자주 보는 소재여서 간단한 문제로 생각했는데 그렇지만은 않았다. 해답에 있어 중요한 아이디어는 앞에서부터 보면서 특정 부분문자열이 올바른 괄호가 아니게 되는 순간 무조건 지금까지의 스택을 비우고 새로 시작해야 한다는 부분이다. 문자열의 길이가 최대 이기 때문에 재귀함수를 사용할 수 없는데, 스택을 직접 구현하는 쪽이 오히려 편리하다.

#include <stdio.h>
#include <cstring>
#include <stack>
#include <algorithm>

using namespace std;

const int N = 1000000 + 10;

int tc;

int dyn[N];

char str[N];

int main() {
  scanf("%d", &tc);
  for(int t = 1; t <= tc; t++) {
    scanf("%s", str);
    stack<int> stk;
    int n = strlen(str);
    for (int i = 0; i < n; i++) {
      dyn[i] = 0;
      if (str[i] == '(' || str[i] == '{' || str[i] == '[') {
        stk.push(i);
      } else {
        if (!stk.empty()) {
          int p = stk.top();
          stk.pop();
          if ((str[p] == '(' && str[i] == ')') ||
              (str[p] == '{' && str[i] == '}') ||
              (str[p] == '[' && str[i] == ']')) {
            dyn[p] = i - p + 1;
          } else {
            for (; !stk.empty(); stk.pop());
          }
        }
      }
    }
    int res = dyn[n] = 0;
    for (int i = n - 1; 0 <= i; i--) {
      dyn[i] = max(dyn[i], dyn[i] + dyn[i + dyn[i]]);
      res = max(res, dyn[i]);
    }
    printf("Case #%d\n", t);
    printf("%d\n", res);
  }
  return 0;
}

100: 주식거래

매일의 주가가 주어질 때, 최적보다 나쁘지 않은 거래를 하면서 사고팔 수 있는 최대 횟수를 구해야 한다.

첫 문제보다 쉬웠다. 더 이상 싸지지 않을때까지 기다렸다가 사고, 더 이상 비싸지지 않을때까지 기다렸다 팔면 문제의 모든 조건을 만족한다.

#include <stdio.h>

const int N = 200000 + 10;

int tc;

int num[N];

int main() {
  scanf("%d", &tc);
  for (int t = 1; t <= tc; t++) {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
      scanf("%d", &num[i]);
    }
    int c = 0;
    for (int i = 0; ; ) {
      if (i == n) {
        break;
      }
      for (; i + 1 < n && num[i + 1] <= num[i]; i++);
      c++, i++;
      if (i == n) {
        break;
      }
      for (; i + 1 < n && num[i + 1] >= num[i]; i++);
      c++, i++;
    }
    int res = c ^ (c & 1);
    printf("Case #%d\n", t);
    printf("%d\n", res);
  }
  return 0;
}

150: 전광판

격자에 배치되어 있는 전구가 각각 행과 열의 스위치와 연결되어 있을 때, 모든 전구를 켤 수 있는 스위치의 조합을 묻는 문제이다.

모든 전구가 정확히 두 개의 스위치에 연결되어 있고, 모든 전구를 켤 수 있는 스위치의 조합을 찾아야 하므로 전형적인 2-SAT 문제로 보인다. 그러나 잘 생각해 보면 2-SAT보다 훨씬 쉬운 경우라는 것을 알 수 있는데, 한 전구에 연결된 두 스위치 모두는 하나의 상태로 다른 하나의 상태를 확정할 수 있기 때문이다. 2-SAT 문제로서 그린 그래프에서 SCC간의 간선이 존재하지 않는 경우이다.

굳이 2-SAT을 해결할 필요 없이 Union-Find 만으로 해결 가능하다. 2-SAT으로도 같은 시간복잡도에 풀리기 때문에 점수에 영향은 없지만, 문제를 좀 더 분석함으로서 구현에 필요한 시간을 크게 절약할 수 있다는 점에서 좋은 문제였다고 생각한다.

#include <stdio.h>
#include <set>

using namespace std;

const int N = 100 + 10;
const int K = 4 * N * N;

int tc;
int n, m, k, l;

int com[K];

int row_node(int i, int j, bool t) {
  int p = 4 * (i * m + j);
  return t ? p : p + 1;
}

int col_node(int j, int i, bool t) {
  int p = 4 * (i * m + j);
  return t ? p + 2 : p + 3;
}

int find(int now) {
  if (com[now] == -1) {
    return now;
  }
  return com[now] = find(com[now]);
}

void link(int s, int t) {
  int su = find(s), tu = find(t);
  if (su != tu) {
    com[tu] = su;
  }
}

int main() {
  scanf("%d", &tc);
  for (int t = 1; t <= tc; t++) {
    scanf("%d %d", &n, &m);
    k = 4 * n * m;
    for (int i = 0; i < k; i++) {
      com[i] = -1;
    }
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        int st, ri, ci;
        scanf("%d %d %d", &st, &ri, &ci);
        if (st == 0) {
          link(row_node(i, ri, false), col_node(j, ci, true));
          link(row_node(i, ri, true), col_node(j, ci, false));
        } else {
          link(row_node(i, ri, false), col_node(j, ci, false));
          link(row_node(i, ri, true), col_node(j, ci, true));
        }
      }
    }
    printf("Case #%d\n", t);
    bool skip = false;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        int rtu = find(row_node(i, j, true)), rfu = find(row_node(i, j, false));
        int ctu = find(col_node(j, i, true)), cfu = find(col_node(j, i, false));
        if (rtu == rfu || ctu == cfu) {
          skip = true;
        }
      }
    }
    if (skip) {
      printf("Impossible\n");
      continue;
    }
    set<int> chosen;
    for (int j = 0; j < m; j++) {
      for (int i = 0; i < n; i++) {
        int ctu = find(col_node(j, i, true)), cfu = find(col_node(j, i, false));
        if (chosen.find(ctu) != chosen.end() || chosen.find(cfu) == chosen.end()) {
          chosen.insert(ctu);
        } else {
          printf("C%02d%02d ", j, i);
        }
      }
    }
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        int rtu = find(row_node(i, j, true)), rfu = find(row_node(i, j, false));
        if (chosen.find(rtu) != chosen.end() || chosen.find(rfu) == chosen.end()) {
          chosen.insert(rtu);
        } else {
          printf("R%02d%02d ", i, j);
        }
      }
    }
    printf("\n");
  }
  return 0;
}

200: Monotone

기하 문제이다. 주어진 다각형이 모든 직선이 해당 다각형을 한 번만 만나는 기울기를 갖는가를 묻고 있다.

점수에 비해 풀이는 어렵지 않다. 주어진 다각형의 모든 꼭짓점이 볼록하다면 모든 기울기의 직선이 주어진 조건을 만족하며, 오목한 꼭짓점은 두 선분의 기울기가 이루는 범위를 주어진 조건을 만족하지 못 하게 만든다. 따라서 모든 오목한 꼭짓점을 이루는 두 선분의 기울기의 범위를 구간에서 지워나가면 된다.

다만 많은 기하 문제들이 그러하듯이 실수 오차때문에 골머리를 앓았다. “실수 오차 이상의 기울기 범위가 존재한다”는 조건을 간과한 상태로 여러 차례 시도해 틀렸고 결국 범위를 지워나가는 범위를 넓혀 잡음으로서 해결 할 수 있었다.

#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <stack>
#include <queue>

using namespace std;

const int N = 50000 + 10;
const double P = M_PI;
const double E = 1e-14;

int tc;

pair<long long, long long> pt[N];

bool mark[N];

bool right(int p, int q, int r) {
  long long s = 0;
  s += pt[p].first * pt[q].second + pt[q].first * pt[r].second + pt[r].first * pt[p].second;
  s -= pt[p].second * pt[q].first + pt[q].second * pt[r].first + pt[r].second * pt[p].first;
  return s < 0;
}

int main() {
  scanf("%d", &tc);
  for (int t = 1; t <= tc; t++) {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
      scanf("%lld %lld", &pt[i].first, &pt[i].second);
    }
    priority_queue<pair<double, double>, vector<pair<double, double> >, greater<pair<double, double> > > que;
    for (int i = 0; i < n; i++) {
      int j = (i + 1) % n, k = (i + 2) % n;
      mark[j] = right(i, j, k);
    }
    for (int i = 0; i < n; i++) {
      int j = (i + 1) % n, k = (i + 2) % n;
      if (mark[j]) {
        double sa = atan2(pt[k].second - pt[j].second, pt[k].first - pt[j].first);
        double ta = atan2(pt[j].second - pt[i].second, pt[j].first - pt[i].first);
        ta += E;
        while (ta < 0.0) {
          ta += P;
        }
        while (P < ta) {
          ta -= P;
        }
        sa -= E;
        while (sa < 0.0) {
          sa += P;
        }
        while (P < sa) {
          sa -= P;
        }
        if (sa < ta) {
          que.push(make_pair(sa, ta));
        } else {
          que.push(make_pair(sa, P + E));
          que.push(make_pair(-E, ta));
        }
      }
    }
    double r = 0.0;
    for (; !que.empty(); que.pop()) {
      if (r < que.top().first) {
        break;
      } else {
        r = max(r, que.top().second);
      }
    }
    printf("Case #%d\n", t);
    if (!que.empty() || r < P) {
      printf("YES\n");
    } else {
      printf("NO\n");
    }
  }
  return 0;
}

250: Covernent

개의 단말 노드를 가진 트리가 주어지고, 이 중에서 조건을 만족하는 개의 노드를 적절히 골라 해당 노드들이 이루는 부분트리의 간선의 가중치의 합을 최대화해야 한다.

문제 조건이 전형적인 Mincost-Maxflow 스타일이었지만 이를 그래프로 나타낼 적절한 방법을 찾지 못했다. 대회가 끝난 후 주어진 트리를 그대로 이용할 수 있다는 이야기를 들었지만 아직 명확한 풀이가 떠오르지 않는다.

Reporting tax in two countries

미국에서의 인턴십은 흔히 하기 어려운 다양한 경험을 선사했는데, 그 중 하나가 무려 1년이란 시간이 지난 뒤에야 마무리된 세금 보고이다. 그 과정을 이곳에 정리해 본다.

Tax Report to US

SSN

미국에서 납세자가 되기 위해서는 한국의 주민등록번호에 해당하는 Social Security Number을 발급받아야 한다. 나는 J-1 비자로 입국한 인턴이었기 때문에 여권과 DS-2019, 인터넷으로 발급받은 I-94, 직접 작성한 SS-5를 들고 가까운 Social Security Administration을 방문해 신청했다. 보고한 거주지로 Social Security Card가 발송되기까지 2주가 조금 안 걸렸는데, 입국하고 2주가 지나야 SSN을 신청할 수 있다는 점을 감안하면 최소 한달정도의 시간이 필요하다고 볼 수 있다. 인턴십을 시작하고 2주가 지나서야 SSN을 회사에 제출했는데 별다른 문제는 없었다.

Form W-4

W-4는 소득세의 원천징수(Withholding)를 위한 공제정보를 보고하기 위한 양식이다. 해당 양식에 작성된 공제내역에 따라 원천징수액이 달라지게 된다. 고용주가 고용인에게 받아 제출해야 하는데 나는 회사에서 제공하는 시스템에 필요한 정보를 기입하는 것으로 끝냈다.

Form W-2

W-2는 원천징수영수증에 해당한다. 1년간의 총 급여액과 원천징수된 연방 및 주 소득세 내역이 나와있고, 회사마다 차이가 있지만 다음 해 4월중에 마감되는 세금 보고를 위해 1~2월 중 고용주가 고용인에게 발급한다. 내가 받은 W-2는 같은 내용의 표가 각각 연방 세금 보고, 주 세금 보고, 보관용으로 한 장씩 들어있었다. 이것으로 고용주의 의무는 끝나고 고용인에게 세금 보고의 책임이 지워진다.

Form 1040

미국의 세금 보고는 다음 해 4월중에 마감된다. 연간 1달러 이상의 소득이 있는 개인의 경우 1040을 IRS에 제출해 소득을 보고하고 세금을 정산해야 하며, 한국의 연말정산처럼 정산된 소득세가 원천징수한 금액보다 클 경우에는 추가 납부를, 정산된 소득세보다 많은 금액을 원천징수한 경우에는 차액을 환급받게 된다. 다만 근로자를 위해 간편화된 연말정산과는 달리 서류를 작성해 IRS에 제출해야 하는 번거로움이 있는데, 한국과는 달리 모든 납세자가 종합소득세 신고를 한다고 생각하면 이해가 빠르다.

1040은 작성 메뉴얼이 백여 장에 이를 정도로 방대하고 내용도 복잡해 전문적인 지식 없이는 작성이 쉽지 않다. 이를 돕기 위한 것이 TurboTax 등의 세금 보고 프로그램인데, 세무사의 역할을 비교적 저렴하게 대신해준다고 생각하면 된다. 매년 세금 보고 시즌만 되면 비슷한 프로그램들이 앱스토어 랭킹에 줄줄이 올라오는것을 볼 수 있는데, 저렴한 가격의 플랜은 입력한 정보를 토대로 IRS에 제출할 서류를 출력해 주는 것에 그치지만 가격이 비싸질수록 추가로 공제받을 수 있는 항목을 찾아 세금을 절감해주거나 IRS에 제출까지 대행해 주는 등 기능이 다양해진다. 다만 대부분의 플랜은 일반적인 납세자에 맞춰져 있어 일반적이지 않은 소득이나 공제항목이 있는 경우에는 선택의 폭이 매우 좁아진다.

Non-resident alien인 나는 미국 영주권자가 제출하는 1040이나 1040이 간소화된 1040-EZ가 아닌 1040NR이나 1040NR-EZ를 제출해야 했는데, 해당 서식을 지원하는 서비스가 많지 않았다. 다행히도 비자를 후원해준 스폰서에서 Glacier Tax Prep의 사용권을 제공해주었고 이를 이용해 연방 세금 보고에 필요한 1040NR-EZ와 8843을 작성했다. 다만 해당 플랜이 주 세금 보고까지는 지원하지 않아 Sprintax의 캘리포니아 세금 보고 플랜을 따로 구매해 540NR을 작성했다.

1040 계열 서식의 내용은 대동소이한데, W-2에 나와있는 총 소득금액에서 시작하게 된다. 일반적으로는 한국의 기본소득공제와 유사한 Personal Exemption과 한국의 근로소득공제와 유사한 Standard/Itemized Deduction을 공제하며, 나의 경우에는 한미조세협정에 의거해 $2,000의 소득공제를 추가로 기입했다. 공제항목을 모두 적용한 뒤 남은 금액이 한국의 과세표준에 해당하는 Taxable Income이 되며 해당 금액을 기준으로 최종적인 소득세를 산정하게 된다.

산정한 소득세를 다시 W-2에 나와있는 원천징수액과 비교해 정산하게 되는데, 원천징수한 금액이 더 크다면 즐거운 일이 아닐 수 없다. 나의 경우에는 연방세와 주세를 합해 수천달러 가량의 환급이 발생하는 것으로 정리되었다.

Tax Return

1040이나 1040-EZ의 경우 최근들어 온라인으로도 제출할 수 있게 되었으나 내가 작성한 1040NR-EZ과 540NR은 해당사항이 없어 각각 IRS와 California State tax office로 직접 보내야 했다. IRS는 Fedex나 DHL을 이용할 것을 권장하고 있으나 필수는 아니다. IRS와 California State tax office로 각각 W-2, 1040NR-EZ, 8843과 540NR, W-2를 순서대로 잘 포장해 우체국 EMS로 발송했다. 사서함은 수신확인이 제대로 되지 않는다는 설명을 들어 조금 불안했으나 결과적으로 1주일정도 걸려 도착한 것으로 보인다.

세금 환급은 미국 내 은행 계좌로의 이체와 수표 중 하나로 받을 수 있는데, 나는 양 쪽 모두 전자를 선택했다. 연방세는 서류를 부친지 한 달 가량 뒤에 계좌로 잘 환급되었으나 주세는 환급되지 않아 궁금해하던 참에 집으로 우편이 도착했는데, 내가 제출한 540NR에 잘못된 점이 있어 이를 수정했다는 통보와 함께 환급액에 해당하는 수표가 동봉되어 있었다. 알고보니 Sprintax에서 작성해 준 540NR에 공제항목이 잘못 기입되어 있었고 결과적으로 수백달러의 세금을 더 내는 것으로 보고된 것이었는데, 이를 정정해 준 덕분에 손해를 보지 않을 수 있었다.

Tax Report to Korea

비록 미국에서 미국 회사에 근로를 제공하고 소득을 창출했으나 나는 한국에 거주중이기 때문에 대한민국 세법에 의해 한국 정부에도 소득세를 납부해야 한다. 세법상 국외근로소득에 해당되어 소득세가 발생하는데, 다만 이중 납세를 방지하기 위해 외국 정부에 납부한 세금을 면제해주는 제도인 외국납부세액공제 혜택을 받을 수 있다. 국외근로소득은 을종근로소득으로 연말정산만으로 끝나는 갑종근로소득과는 달리 종합소득세 신고를 통해 정산해야 한다.

연말정산

귀국한 뒤 서울의 회사에서 근무하고 있었으므로 해당 소득에 대해 연말정산을 했다.

종합소득세 신고

종합소득세 신고의 경우에도 내용이 간단한 경우는 국세청 사이트를 통해 직접 신고하거나 저렴한 대행서비스를 이용한다고 한다. 하지만 국외근로소득과 외국납부세액공제는 흔히 있는 경우가 아니라 애를 먹었는데, 다행히도 지인을 통해 소개받은 세무사사무실에서 비교적 저렴한 비용에 처리해 주었다. 일반적으로는 국문이 아닌 서류는 번역본으로 세무에 사용한다고 하는데 그런 사정을 잘 몰랐기에 원문을 그대로 전달했고, 나중에 요청을 받아 간단한 각주를 달아서 다시 전달했다. 세무사님도 오랜만에 세법을 다시 들여다봤다고 하니 번거로웠을텐데 고마울 따름이다.

외국납부세액공제는 납부액을 전부 공제하는 것이 아니고 전체 소득에서 해당 외국근로소득이 차지하는 비율까지만 공제한다. 나는 과세년도에 국외근로소득과 국내근로소득이 모두 발생했으므로 공제한도가 해당 비율에 따라 결정되는데, 국세청 안내를 보고 직접 계산해 본 결과 상당금액이 공제한도를 넘겨 추가로 납부해야 하는 것으로 보였으나 실제로 추가로 납부할 금액은 없었다. 세무사사무실을 통해 받아본 서류의 사본에는 구체적인 계산 과정이 나와있지 않아 참고하지 못한 점이 다소 아쉬웠다.

Epilogue

적지 않은 금액을 환급받고 소득세를 추가로 납부하지는 않았으니 성공적이었다고 평할 수 있겠다. 이런 일은 언제나 환영이야!

Facebook Hacker Cup 2017 R1

35점 이상을 획득하면 R2에 진출할 수 있다.

10: Pie Progress

일동안 가게에서 개의 파이를 판매한다. 매일 이 판매하는 파이들의 부분집합을 구매해서 일동안 총 개의 파이를 구매하는 최소 비용을 구해야 한다. 단 파이의 가격은 매일 달라지며 하루에 개의 파이를 구매하면 파이의 가격에 추가로 의 세금이 발생한다.

가장 쉬운 방법은 각 날마다 가게에서 판매하는 파이를 저렴한 순으로 정렬한 뒤 하나씩 구매할 때 발생하는 세금의 차액까지 파이의 가격에 추가하는 것이다. 예를 들어 3개의 파이를 판매한다면 가장 저렴한 파이에는 1, 그 다음 파이에는 3, 그 다음 파이에는 5의 가격을 추가한다. 이 상태에서 모든 날에 판매하는 파이들 중 가장 저렴한 개의 파이를 선택하면 된다.

하지만 대회중에는 간단한 방법을 생각해 내지 못하고 DP로 접근했는데, 일까지 개의 파이를 구매하는 최소 비용으로 정의하면 에 해결 가능하다. 하지만 제출 과정에서 dictionary로 구현한 코드의 버그를 발견했고 이를 남은 시간동안 제출하기 위해 list를 사용하도록 수정하는 과정에서 삽질을 반복하면서 결국 제한시간을 초과했다. 부끄러울 따름이다.

25: Fighting the Zombies

좌표평면에 좀비를 나타내는 점이 개 주어진다. 이 좀비들에 대해 임의의 원 안에 들어있는 좀비들을 임의의 변위로 평행이동한 뒤 주어진 크기의 정사각형을 잘 위치해 최대한 많은 좀비가 정사각형 안에 위치하도록 해야 한다.

좀비의 이동은 임의의 크기의 원을 기준으로 하므로 충분히 큰 원을 적절한 위치에 잡으면 원의 경계는 직선이나 다름없어진다. 이를 이용해 임의의 두 정사각형을 빠져나가는 좀비 없이 항상 겹칠 수 있음을 증명할 수 있는데, 개의 좀비 중 넷을 이용해 두 정사각형을 결정하고 두 정사각형에 들어있는 좀비의 합집합의 크기의 최댓값을 구하면 된다.

시간복잡도는 로 여유롭지는 않지만 제한시간 내에 제출은 가능하다. 대회중에는 풀이에 근접은 했으나 해답 완성과 구현의 가성비가 떨어진다고 생각해 마지막 문제로 바로 넘어갔다.

40: Beach Umbrellas

직선상에 1m 간격으로 있는 개의 구멍에 다양한 반지름의 우산 개를 꽂으려고 한다. 우산끼리 겹치지 않도록 주어진 우산을 모두 꽂는 방법의 수를 구해야 한다.

먼저 가장 왼쪽 또는 오른쪽의 우산 역시 우산 전체가 개의 구멍들이 이루는 선분에 완전히 포함되어야 한다고 생각해 보자. 선분은 길이의 구간이며, 각 우산이 겹치지 않기 위해서는 지름에 해당하는 구간이 필요하다. 에서 각 우산의 지름에 해당하는 길이를 모두 빼고 남는 구간의 길이를 이라고 하면 문제는 개의 서로 다른 점과 개의 동일한 구간의 순서를 배치하는 문제가 된다. 답은 가지이다.

문제는 가장 왼쪽 또는 오른쪽의 우산의 경우 바깥쪽을 향한 절반은 다른 우산과 겹쳐질 일이 없으므로 구간이 필요하지 않다는 점이다. 이를 고려하기 위해서는 가장 왼쪽과 오른쪽의 우산을 미리 정해 놓은 뒤 해당 우산들은 반지름만큼의 구간이, 다른 우산들은 지름만큼의 구간이 필요하다고 생각하여 계산해야 한다. 미리 정해진 우산의 크기에 따라 의 값이 변할 수 있으며, 답은 가지이다.

수식의 값을 계산하는 과정에서 결과값이 매우 커질 수 있으므로 로 나눈 나머지를 구해야 하는데 나눗셈은 modular inverse를 구해 곱해야 하며 이 소수이므로 굳이 Extended Euclidean algorithm을 구현할 필요 없이 페르마의 소정리를 이용해 쉽게 구할 수 있다. 또한 이 최대 까지 커질 수 있으므로 필요한 팩토리얼 값을 일일히 계산하지 말고 적절한 최적화 과정을 거쳐야 한다.

구현한 코드의 시간복잡도는 가장 큰 우산의 반지름을 라 할 때 이지만 코드의 효율성을 자신할 수 없어 Python 2로 구현, PyPy로 실행했다. 직접 만들어 본 데이터 셋을 수행하는데 약 25초, 실제 데이터 셋을 수행하는데 약 2초가 걸렸으며 각각 CPython으로 실행했을 때보다 수십배가량 빠른 속도였다.

L = 1000000007

def power(n, p):
    if p == 0:
        return 1
    r = power(n, p >> 1) ** 2
    if p & 1:
        r *= n
    return r % L

DI = {}
def modinv(n):
    if n in DI:
        return DI[n]
    DI[n] = power(n, L - 2)
    return DI[n]

def init(n, m):
    global DV, DC
    if m < 0:
        m = 0
    t = modinv(n) * modinv(n - 1)
    t %= L
    for i in xrange(1, n + 1):
        t *= i + m
        t %= L
    DC = [t]
    DV = m

DC = []
DV = 0
def calc(n, m):
    if m < 0:
        return 0
    for i in xrange(DV + len(DC), m + 1):
        DC.append((DC[-1] * (n + i) * modinv(i)) % L)
    return DC[m - DV]

for tc in xrange(int(raw_input())):
    DC = []
    N, M = map(int, raw_input().split())
    R = [int(raw_input()) for _ in xrange(N)]

    C = {i: 0 for i in set(R)}
    S = 0
    for i in R:
        C[i] += 1
        S += i

    if N == 1:
        A = M
    else:
        m = (M - 1) - (S * 2)
        A = 0
        init(N, m)
        for lm, lc in C.items():
            for rm, rc in C.items():
                if lm == rm and lc < 2:
                    continue
                m += lm + rm
                a = calc(N, m)
                if lm == rm:
                    c = lc
                    a *= c * (c - 1)
                else:
                    a *= lc * rc
                A = (A + a) % L
                m -= lm + rm

    print("Case #{}: {}".format(tc + 1, A))