PS 이야기

자동차가 C대 있고 각 자동차의 시작 위치가 다를 수 있다. 모든 자동차의 목적지는 1번 마을이고, 각 자동차는 최단 경로 중 임의의 한 경로로 이동한다고 하자. 두 자동차가 동시에 같은 마을에서 같은 도로를 이동할 수 없을 때, 목적지에 갈 수 있는 자동차의 최대 개수를 구하는 문제다. 이 문제는 2013년 월드 파이널 C번 문제와 지문 하나 다르지 않게 출제되었다. 다행히도 이 문제의 풀이를 미리 알고 푼 팀은 없는 것으로 알고 있다. 문제에서 제약 조건은 단 하나, 두 자동차가 동시에 같은 마을에서 같은 도로를 이동할 수 없다는 것이다. 두 자동차가 동시에 같은 마을에서 같은 도로를 이동하기 위한 필요충분조건은 두 자동차의 시작 마을에서 도착 마을로 가는 최단 거리가 같다는 조건이다. 따라서 자동차..

길이가 N인 문자열이 주어지고, 길이가 M인 패턴이 주어진다. 이 패턴의 연속된 일부분 혹은 전체를 한 번 뒤집어서 새로운 패턴들을 만들 수 있다. 길이가 N인 문자열에서 이렇게 만들어진 패턴들과 매치되는 부분 문자열이 몇 개인지 세어주는 문제다. N ≤ 1,000,000 이고 M ≤ 100 이다. 시간제한은 0.2초로 N에 선형인 시간복잡도를 요구한다. 길이가 M인 패턴에서 뒤집는 연산에 의해 만들어지는 새로운 패턴의 개수는 많아야 $M^2$개다. 즉, 이 문제는 길이가 M인 패턴 $M^2$개와 길이가 N인 문자열을 매칭하는 문제로 바꿀 수 있다. 이와 관련된 문제는 Aho-Corasick 자료구조를 이용하면된다. KMP와 같은 문자열 매칭 알고리즘은 하나의 패턴과 전체 문자열을 매칭하는 알고리즘인데,..

2차원 좌표계에 N 개의 점이 주어졌을 때, 유클리드 거리상 가장 먼 두 점을 찾는 문제이다. 가장 먼 두 점 구하기 글에 풀이가 소개되어 있다. #include using namespace std; #define MAXN 200005 #define pb push_back #define sz(v) ((int)(v).size()) typedef long long lld; int T, N; struct Z{ int x, y; } A[MAXN]; int ccw(int ax, int ay, int bx, int by, int cx, int cy) { lld k = (lld)(bx-ax)*(cy-ay)-(lld)(cx-ax)*(by-ay); if (k > 0) return 1; if (k) return -1; r..