취미로PS하는사람

KMP.. 아픈 기억이 있는 알고리즘. 아무튼 그동안 이러저러한 이유로 KMP 공부를 미루고 있다가 최근에야 다시 제대로 배웠다. 아이디어 자체는 간단하다. 문자열 $S$에 패턴 $P$를 매칭할 때, $P$의 $i$번째까지의 문자열에 대해 접두사이면서 접미사인 문자열의 최대 길이(여기서 접두사와 접미사는 원래 문자열을 제외하고 말한다.)를 실패 함수라고 정의한 후 이를 잘 이용하면 $O(|S|+|P|)$에 패턴이 존재하는지 찾을 수 있다. $S$의 중간 부분부터 $i-1$번째까지 문자열과 $P$의 $p$번째까지 문자열이 일치한다고 하자. $S$의 $i$번째 문자를 새로 매칭시키려고 할 때, 만약 성공한다면 $p$를 1 증가시키면 그만이지만 실패할 경우, Naive하게 할 때는 매칭을 시작한 곳 다음 부분..

https://www.acmicpc.net/problem/19833 간단한 수열에서의 문제. 앳코더 스타일 같아서 마음에 들었고 충분히 대회에도 나올만 한 문제라고 느꼈다. 다만 코딩미스라던지 생각을 깔끔히 정리하지 못해 시간이 꽤나 걸렸다.. 다른 사람들의 답안을 훑어보니, 나와 비슷하게 푼 사람도 있었고 스택(?)을 이용하여 푸는 방법도 있는 것 같았다. 성실한 사람이라면 둘 모두 알아보면 좋을 것 같다. 문제 수열$\{a_i\}$가 주어진다. 서로 겹치는 원소가 없는 두 구간의 최댓값이 같은 경우의 수(즉, 구간쌍의 개수)를 구하시오. 풀이 더보기 수열의 수들을 좌표압축하면 $[1, n]$의 숫자로만 이루어져있다고 봐도 무방하다. 이제 $a_k=x$인 $k$들을 순서대로 $v_{x,1}, v_{x,..

https://www.acmicpc.net/problem/3121 그 테크닉을 배웠다. (2022.1.5 추가: rotating sweep line 이라고 부르는 것 같다.) $N$개의 점이 있을 때, 특정 기울기의 법선 벡터를 가지는 직선에 점들을 정사영하여 그 순서를 알고 싶다. 만약 Naive하게 구현한다면 각도는 최대 $O(N^2)$개, 점들의 정렬에 대략 $O(Nlog{N})$이 소요될 것이므로 시간이 너무 오래 걸린다. 하지만 잘 생각해보면 정렬된 상태는 법선벡터와 어떤 두 점을 잇는 직선의 기울기가 동일해질 때 그 두 점의 위치만 인접한 상태에서 바뀌기 때문에, 점 쌍들을 기울기로 정렬하여 순서대로 두 점의 위치만 바꾸어주면 모든 $N^2$개의 각도에서 정사영한 순서를 알 수 있다. 각도 정..

https://oj.uz/problems/source/377 1. Two Antennas (두 안테나) 극한의 스위핑 문제... 우선 쿼리에 변화가 없으므로 오프라인으로 쿼리를 처리해야겠다는 생각을 할 수 있다. R이 증가하는 순서대로 쿼리를 정렬하자. 통신을 할 수 있는 조건은 1 P[i]; sumA[i] = sumA[i-1] + A[i]; } for(int i = 1; i > B[i] >> T[i] >> Q[i]; sumB[i] = sumB[i-1] + B[i]; ans += Q[i]; } for(int i = 1; i = 0) po.eb(i, temp, P[i]); } for(int i = 1; i b.y; return a.x < b.x; }); ll rem = 0; for(int i = 0; i ..

https://www.acmicpc.net/problem/8128 나의 접근 방식은 이러하다. 1. 리프 노드 사이로만 길을 놔야 한다. 이는 너무 당연하다. 2. 가장 점이 많이 포함되도록 길을 놓았을 때 그 점들의 집합은 끊어져 있지 않다. 만약 끊어져있다면 한 쪽의 한 경로와 다른 쪽의 한 경로의 한 끝점을 맞바꾸면 떨어진 두 컴포넌트 사이의 모든 정점도 포함되기 때문에 언제나 최적의 상태에서 위 조건을 만족하지 않을 수 없다는 것을 알 수 있다. 위 두 조건으로부터 최적 정점 집합은 리프 노드가 총 2*k개인 서브그래프라는 것을 알 수 있다. 이 때 포함된 정점 개수를 최대화 해야 한다. 3. 최적 점의 집합은 트리의 지름을 포함한다. 몇 번 그려보면 왠지 그럴 것 같다는 느낌을 받을 수 있다. ..