취미로PS하는사람

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

https://codeforces.com/contest/1628 A를 봤는데 막막했다. 그래서 일단 D부터 잡았고(사실은 standing을 봤는데 Petr가 D1을 4분만에 풀었길래 풀만해 보여서) $O(nm)$ 풀이는 15분정도에 나왔으나 D2도 딱히 어려워보이지 않아서 일반화를 거친 후 45분만에 D1 D2를 모두 AC 받았다. 다만 시간 패널티를 고려해봤을 때, 앞으로는 이런 문제에서 D1을 일단 빨리 맞는 편이 나을 것 같긴 하다. 아무튼 그 이후에 A를 세그 2개씩 써야 하는 건가 할 정도로 뇌절하다가 그냥 하면 된다는 걸 깨닫고 30분이나 걸려 AC를 받았다. 이후 B를 잡았는데 도저히 모르겠어서 C로 넘어갔다가 그냥 하면 된다는 걸 깨달았지만, 대충 짜다가 컷당하고 다시 일반화시켜 AC를 받..

https://atcoder.jp/contests/arc133 이 바보같은 과거의 내가 무조건 한다는 마인드로 rated register를 해버렸다. 이게 최근에 atcoder에 생긴 제도인데, rated register을 하면 문제를 보거나 제출하지 않아도 rated가 된다. 하는 수 없이 집에 오는 버스에서 부랴부랴 폰코딩으로 A B C를 맞았다. 집에 도착한 이후 D를 풀고 있었는데 접근은 잘 한 것 같으나 결국 풀이에는 실패했다 ㅜㅜ 그래도 점수 떡락은 면했다. 다행히 오늘 A B C는 모두 쉬웠고 구현도 쉬웠다. A 길이 $n$의 수열이 주어진다. 수열에서 어떤 숫자 $x$를 골라 $x$를 모두 제거한 수열이 사전순으로 가장 크도록 하고 싶다. $a_{n+1}=0$이라 두고, $1 \leq 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하게 할 때는 매칭을 시작한 곳 다음 부분..