취미로PS하는사람

https://www.acmicpc.net/problem/9022 랜덤 icpc 플래 dp 뿌시기 하면서 나온 문제. 정렬에서 잘못해 몇번 틀리다가 맞았다. 이후 시간복잡도를 줄여보았다. [2022.06.16 추가] IOI 2016의 Alien에서 Alien Trick을 제외한 것과 거의 동일한 문제이다. 문제 평면에 여러 정수좌표 점들이 주어진다. x축 위의 여러 점을 중심으로 각 변이 x축과 45도 기울어진 정사각형들을 그려 모든 점들이 적어도 하나의 정사각형의 경계나 내부에 있게 할 것이다. 정사각형 면적 합의 최소는? 풀이 더보기 우선 $y_i

https://www.acmicpc.net/problem/19274 앳코더를 사랑하는 나에게는 정말 익숙한 이름인 Snuke좌가 나오는 문제다. 대학생을 대상으로 하는 러시아 캠프(페트로 뭐시기)에서 앳코더쪽 사람들이 낸 문제인 것 같았다. 그래서 그런지 문제 스타일도 앳코더 스타일 느낌이 강하다. 코딩 간단, 디스크립션 간단, 아이디어성. 문제 정점이 $N$개인 트리가 주어진다. 우리는 적당히 $K$개의 정점 $x_1, x_2, \cdots, x_K$를 선택하여 임의의 정점 $i$에 대해 $(d(x_1, i), d(x_2, i), \cdots, d(x_K, i))$가 모두 다르도록 할 것이다. 다시 말해, $K$개의 정점을 골라 각 정점들로부터의 거리 정보 벡터로부터 어떤 점인지 알아낼 수 있도록 $K..

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$개의 각도에서 정사영한 순서를 알 수 있다. 각도 정..