취미로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..

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

https://www.acmicpc.net/problem/23386 플래티넘 1의 수문장 사수아탕이 있다면 플래티넘 3의 수문장은 Lopsided Lineup이라고 생각한다. 진짜 접근을 못하면 몇시간이 저세상으로... ㅋㅋ ㅠㅠ 랜덤 영어 플래 디펜스 하는 중 가장 어려웠던 문제 같다. 사실 이것도 나랑 red1108이 올려놓은 난이도다.. 도대체 이걸 처음 준 사람은 왜 플5를 준 것일까.. 문제 짝수인 $n$에 대해 $n \times n$ 크기의 대칭행렬 $c_{i,j}$가 있다. $c_{i,j}$가 의미하는 것은 $i$번째 사람과 $j$번째 사람이 같은 팀일 때 해당 팀의 점수?같은 것이 $c_{i,j}$만큼 상승한다는 것이다. 사람 수가 같도록 팀을 두 개로 나눌 때, 두 팀의 점수 차이를 최대..

https://www.acmicpc.net/problem/13329 팀연습에서 맞춘 문제 중 가장 어려운 문제가 아닐까 싶다. 정확히 말하면 맞추지는 못했고 풀이를 낸 이후에 코딩을 완성하지 못했다가, 조금만 손 보고 맞았다. 문제 y좌표가 모두 0보다 큰 영역에 대해, 컨벡스 헐이 $N$개 있다. $(0, 0)$에서 볼 수 없는 컨벡스 헐의 개수는? 풀이 더보기 우선 생각할 점은, 하나의 컨벡스 헐은 그 컨벡스 헐의 점 중 각도가 가장 큰 것과 작은 것의 선분으로 대체할 수 있다는 것이다. 문제에서 컨벡스 헐이 겹치지 않는다고도 했으니.. 아무튼 이 처리를 하고 나면 이 문제는 볼 수 없는 선분의 개수를 세는 문제로 바뀐다. 이 때 어떤 선분을 볼 수 없으려면, 그 선분이 커버하는 각도를 다른 선분들이..