6/8 ~ 6/16 PS

어제부터 시험이 시작됐지만 ps는 해야지..

 

 

BOJ 17429 - 국제 메시 기구 (D4)

Euler Tour + HLD + Lazy Segtree. 구현 양이 너무 많아서 티어가 높아졌다.

오일러 투어를 할 때, 무거운 정점 우선으로 내려가서 numbering을 해 주고, HLD를 했기 때문에 경로에 대한 update와 sum은 빠른 시간에 구할 수 있다.

 

BOJ 10350 - 은행 (R5)

(음수가 되는 구간합) / (전체 구간합) 의 올림의 합이 답이다. 시간 제한이 5초라서 \(O(N^2)\)가 가능하다. 실수로 알고리즘 분류를 봐서 쉽게 풀렸다..

 

BOJ 16680 - 안수빈수 (P5)

\(x *(1e9 - 1)\)

 

BOJ 18185, 18186 - 라면 사기 (D4)

B<=C라면, 1개씩만 먹는 것이 이득이다. B>C인 경우를 생각하자.지금 k번째를 보고 있다고 해보자. \(A_{k+1} < A_{k+2}\)일 때, \(k\)~\(k+2\)에서 먹고 \(k\)번째에서 먹는 것이 이득이다. 반대의 경우는, 3개부터 먹는다면 \(k+1\)~\(k+3\)에서 먹을 수 있음에도, \(A_{k+2}=0\)이 되므로 최적이 아니다. \(k, k+1\)에서 먹고 \(k\)번째에서 먹으면 된다. 

 

BOJ 19651 - 수열과 쿼리 39 (D5)

수열 \(B\)를, \(B_i=A_i-A_{i-1}\)이라고 정의하자. 그러면 2번 쿼리는 구간에서 원소의 값이 모두 같은, 연속하는 부분수열의 최대 길이 + 1을 구하는 문제로 바뀐다. 금광 세그를 활용하면 된다.

 

BOJ 18975 - Jaw-Dropping Set (D4)

오른쪽 절반을 먹으면 되므로 subset의 최대 크기는 \(\lceil\frac{N}{2}\rceil\)이고, 이는 set의 홀수의 개수와 같다. 1, 3, 9, 27... 이렇게 있을 때 오른쪽 끝부터 \(2^0\), \(2^1\), \(2^2\), ... 이렇게 곱해주면 가능한 모든 수들이 서로소가 된다는 것(그리고 합은 최소가 된다)을 이용해보자. N보다 작거나 같은 모든 홀수는 \(2^0\)을 곱한다. 그리고, \(N/3\)보다 작거나 같은 모든 홀수는 \(2^1\)을 곱한다. 이렇게 1까지 쭉 가면 각 테스트케이스 당 \(O(logN)\)에 풀 수 있다.