5/30~6/1 PS

다행히도 요즘은 스트레스를 덜 받나보다. 어제 코포 레이팅을 -50정도 받았는데도 화가 안났다.

 

오늘부터 플3~다5 랜덤디펜스를 시작했다. 마지막 두 문제는 오늘 푼 것임

 

 

BOJ 17473 - 수열과 쿼리 25 (R5)

세그비츠 문제다. 이 글로 풀이를 대체함

 

BOJ 2268 - 수들의 합 7 (G1)

세그트리 슈퍼기초문제다. \(i > j\)인 쿼리가 들어올 수 있음에 유의하면 된다.

 

BOJ 17476 - 수열과 쿼리 28 (D1)

세그비츠 활용문제다. 제곱근 값은 빠르게 감소하는 특징이 있으므로 같은 값을 가지는 리프노드들이 많아지게 된다. 그러나 \([100, 99, 100, 99, ...]\)와 같은 경우에서, 제곱근 연산과 전체 구간 \(+90\)이 번갈아 들어오는 경우가 문제가 된다. 이 경우는 그냥 따로 처리해주면 된다. 구간 제곱근 연산이 아니라, 구간 \(-90\) 연산으로 볼 수 있다.

 

BOJ 19472 - Array and Operations (D1)

notorious coincidence (=17476)

 

BOJ 1704 - 붕어빵타이쿤 (P5)

맨 윗줄은 가능한 \(2^{15}\)가지를 모두 테스트하고, 위에서부터 내려오면서 바로 위의 숫자가 1이면 상태를 반전시켜주면 된다. 문제의 조건이 되게 까다로운 편이니 주의...

 

BOJ 18437 - 회사 문화 5 (P3)

Euler Tour Technique를 사용하는 문제다. 너무나도 간단하게 풀린다. 오일러 투어 + 레이지 세그

 

BOJ 13511 - 트리와 쿼리 2 (P3)

 어떤 정점 u에서 v로 가는 경로는 두 정점의 lca를 p라고 했을 때, u to p와 p to v로 나눌 수 있다. lca는 sparse table을 사용하여 \(O(NlgN)\)에 구할 수 있다.

 k번째 정점을 구하는 것이 약간 까다로울 수 있는데, 두 정점 u와 p 사이에 k번째 정점이 존재하지 않는다면, \(dist(u, v) - k\)로 바꾸고 v와 p 사이에서 찾으면 된다.