오늘의 PS (17) - 220627

오늘의 랜덤 검색 태그는 아래와 같았다.

 

변태라고 생각할 수도 있지만, 그게 아니라 내가 약하다고 생각한 분야를 모았더니 저렇게 됐다. 공평하게 각 태그에서 하나씩 골라서 풀었다.

 

18862 - 이제 다시 시작이다

 

기하인 척 하는 자료구조 문제이다. 식 정리를 열심히 하면 넓이를 4가지 경우에 따라 이차함수 꼴으로 계산할 수 있다. 다행히도 좌표의 범위가 주어져 있으니, seg[a]를 \(ex,ey\)와의 거리가 \(a\)인 스피커의 개수로 정의하자. 이러면 4가지 경우의 범위를 잘 나눠준 후 1, \(a\), \(a^2\)의 누적합을 저장하는 펜윅 트리로 답을 구해줄 수 있다.

 

11406 - 책 구매하기 2

 

플로우 기본 문제이다.

 

2814 - 최소인수

 

기본적인 풀이는 1557번 등과 비슷하다. 이분 탐색을 씌워준 후, 해당 수보다 작으면서 조건을 만족하는 수의 개수를 구해야 하는데, \(n/p\)가 클 수 있어 포함배제를 일일히 할 수는 없다. 정해는 p의 범위에 따라 작으면 완전탐색을 하고, 크면 \(n/p\)가 작아지므로 에라토스테네스의 체를 쓰는 것 같은데 나는 뭔가 맘에 들지 않아서 그냥 남은 경우에 대해 백트래킹을 돌렸다. 그랬더니 1초 제한 문제를 984ms로 통과할 수 있었다. 재미있는 경험이었다.

 

10256 - 돌연변이

 

조금의 생각을 한 후 아호코라식을 구현해주면 된다.

 

4개중 2개가 그냥 짜면 되는 문제라 크게 연습이 되었을 지는 모르겠다. 물론 진짜 응용문제들이 나왔을 때 풀 자신은 없다 ㅎㅎ