PS 이야기

인접한 도시 사이를 이동하는데 걸리는 시간 1, 한 도시에 있는 관광지를 모두 둘러보는 시간 1이 걸리고 시작점이 주어졌을 때, 가장 관광지를 많이 방문하는 문제다. 물론 같은 관광지를 여러 번 방문해서는 안된다. 답이 될 수 있는 이동 경로는 아래 두 가지 중 하나이다. 1) 시작점에서 왼쪽으로 0칸 이상 가다가 어느 순간 오른쪽으로 이동하여, 시작점 보다 오른쪽으로 간다. 2) 시작점에서 오른쪽으로 0칸 이상 가다가 어느 순간 왼쪽으로 이동하여, 시작점 보다 왼쪽으로 간다. 즉, 쉽게 말하자면 방향을 한 번만 바꾼다는 것이다. 두 번 이상 방향을 바꾸어 왔다갔다 하는 것은 이동하는 시간만 늘리므로 항상 안좋다는 것을 알 수 있다. 2번 경우는 전체를 좌우로 뒤집었을 때 1번 경우와 같아지므로, 1번 ..

0. 표지 1. horses 문제: 말을 한 번 팔 때, 모두 팔아버리는 것이 좋음을 알 수 있다. $i$번 해에 말을 파는게 제일 좋기 위한 필요조건은 $i 1$인 $i$들 중 30개 보다 앞에 있는 날에 말을 파는 것은 안좋다는 것을 알 수 있다. 결국 답으로 가능한 구간이 최대 30개 생기는 꼴인데 매 쿼리마다 각 구간 별로 최대 $Y[i]$를 인덱스트리나 세그먼트 트리로 구해놓은 다음에 말을 팔고 남은 최대 이익을 계산하면 된다. 그러면 하나의 쿼리를 $30 \lg N$ 에 조금 비례한 회수의 연산으로 해결할 수 있다. #include using namespace std; #define MAXN 500005 #define TS 1048576 #define pb push_back #define sz..

0. 표지 1. boxes 문제: 최적의 이동 방법이 있다고 하자. 이 이동 방법에서는 절대 반시계방향으로 이동한 경로와 시계방향으로 이동한 경로가 교차하는 일은 없다. 이 때 경로라 함은 선물을 주러 이동하는 경로만을 얘기하며 선물을 다시 가지러 0번 지점으로 이동한 경로는 제외하고 말했다. 그렇기 때문에 문제에서 원형의 일부를 끊어 선형으로 바꾸어 생각할 수 있다. 선형으로 바꾼 경우, 0번 지점을 기준으로 음수 좌표와 양수 좌표를 나누어 생각할 수 있다. 결국 선형인 경우에 대해 욕심쟁이 기법으로 답을 전부 구해놓은 뒤, 모든 지점에 대해 끊어 선형으로 바꾼 뒤 답을 계산하면 된다. 선형일 때 주의해야할 점은 K개의 지점에 선물을 나누어주고 다시 0번 지점으로 돌아가는 경로는 원형에서 이루어지는게 ..