이제 플래티넘 이하 난이도 문제는 총 3개가 남았다. 내일 모레쯤 끝날 듯. 다이아는 천천히 풀어야지(천천히 풀기 싫어도 천천히 풀게 되겠지) 18260. Bessie's Snow Cow 내가 비교적 잘 푸는 유형이라 쉽게 풀었다. 이 문제도 일단 오일러 투어 테크닉을 써서 구간으로 펴서 생각한다. 이렇게 펴서 생각하면, 업데이트는 특정 구간에 색깔 c가 없는 위치에 전부 c를 추가하는 연산으로 생각할 수 있다. 쿼리는 그 구간에 존재하는 색 개수의 합을 구하는 형태가 되는데, 여기까지만 놓고 보면 제일 기본적인 형태의 Lazy propagation Segment Tree로 생각할 수 있다. 다만 색깔 c가 없는 위치만 골라서 c를 추가하는 부분이 조금 어려운데, 여기서 각 구간이 하나의 서브 트리를 나..
한 문제 한 문제가 고역이다 11990. Load Balancing (Platinum) 이 문제는 비교적 뻔한 문제여서 풀이는 금방 생각했다. 우선 모든 점을 x좌표를 기준으로 정렬해보자. 임의의 i번째 점과 i + 1번째 점 사이에 선을 그으면, 1 ~ i번째 점과 i +1 ~ n번째 점은 서로 다른 평면으로 분할이 된다. 이제 여기서 좌우로 선을 어떻게 긋는 경우가 최적인지를 찾아야 하는데, 이 때는 x좌표는 고려할 필요가 없다(x좌표는 이미 평면 분할된 걸 고려했으니). 그래서 y 좌표만 있는 일차원 배열 두 개에서 최적인 경우를 찾는게 되는데, 이 최적 그래프는 unimodal한 형태를 띈다(양쪽 평면 각각을 나눠서 생각했을 때 unimodal한 건 쉽게 생각할 수 있는데, 이 둘에서 다시 최대를..
벌써부터 점점 풀기가 어려워지고 있다. 14446. Promotion Counting 15899번 문제와 완전히 똑같은 문제. 이제는 너무 널리 알려진 테크닉이 아닌가 싶다. 일단 오일러 투어 테크닉을 써서 트리를 배열로 펴주고 나면 각각의 서브트리를 구간으로 나타낼 수 있다. 이제 이 구간에서 루트의 값 x보다 큰 원소의 개수를 세는 문제가 되는데, 이는 여러 가지 자료구조를 이용해서 풀 수 있다. 나는 그냥 머지소트 트리 써서 풀었다. 14522. Modern Art(Platinum) 문제를 잘못 읽어서 약간 헤맸다. N^2개 수를 각각 최소한 한 번씩 쓴다는 조건이 있는데 이것 때문에 생기는 예외를 처리를 안 했음. 우선 각각의 색에 대해 그 색이 칠해진 사각형 영역의 크기를 구한다. 이 사각형 영..