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\ast (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)$에 풀 수 있다.