오늘의 PS (18) - 220629

어제는 노느라 문제를 풀지 못했다. 오늘은 플레 랜덤 문제를 몇 개 풀었다.

 

20670 - 미스테리 싸인

 

볼록다각형 이분탐색 문제를 연습하고 싶어 풀었다. 다각형을 위 아래로 나누는 방법과 각도로 나누는 방법 두 가지가 있는 것 같다. 이거 말고 접선 긋는 문제도 있는데, 한번 연습해 볼 계획이다.

 

18373 - N!!!...! mod P

 

K가 크면 답이 0이 될 것이라고 추측할 수 있다. 그러면 경우의 수가 몇개 남지 않는데, 이를 열심히 짜주면 시간 초과를 받는다. (12!~=5e8)!을 구하는 게 1초 안에 돌아가지 않는 것 같다. 도저히 모르겠어서 열심히 풀이를 찾았는데, FFT를 쓰는 어려운 풀이와 윌슨 정리라는 걸 쓰는 풀이가 있었다. 티어를 봐선 FFT는 절대 아닌 것 같아서 윌슨 정리를 공부해보았다. 정수론 쪽에서는 굉장히 유명한 정리라고 하는데, 수학적 깊이가 얕아서인지 처음 알았다..

 

9623 - 부분 수열의 길이 

 

세그를 짜기 싫어 대충 짠 풀이가 틀려서, 로그 제곱 풀이를 짰다. 역시나 TLE라 고민을 좀 해 로그 풀이를 생각해냈다. 짜면서도 더 쉬운 풀이가 있을 것 같아 찜찜했는데, 역시 있는 것 같아 슬펐다.

 

13704 - 수열과 쿼리

 

플레 상위권 수쿼 문제 단골 소재 중 하나가 Mo's이다. 이를 유추해냈다면 풀이 만들기는 크게 어렵지 않은 것 같다.