오늘의 PS (8) - 220611

종강을 했다. 시험기간에는 문제가 그렇게 풀고 싶었는데, 종강하자마자 의욕이 확 식길래 랜덤 디펜스를 시작하기로 했다.

범위는 G2~D4이며, 하루에 5문제씩 뽑아서 진행할 예정이다. https://www.acmicpc.net/group/14908에서 진행 중이니 제가 뭘 푸는지 구경하고 싶거나 같이 문제를 풀고 싶으신 분들은 언제든 환영입니다ㅎㅎ

 

오늘은 첫날이라 시간을 기록하지 않았는데, 다음부터는 시간도 잴 예정이다.

 

15678 - 연세워터파크

 

웰노운이라 짜서 맞았다. 최근 \(k\)개 항의 최대 또는 최소를 관리해야 하는 DP는 세그 또는 PQ 또는 덱을 사용해서 해결할 수 있음이 널리 알려져 있다.

 

2136 - 개미

 

이것도 웰노운이라 신나게 짜긴 했는데, 생각해보니 번호를 구하는 방법을 몰라서 시간이 좀 걸렸다. 이 문제에 대해서는 좋은 자료가 인터넷에 많을 것이라 생각하니 설명은 생략한다.

 

1653 - 양팔 저울

 

그냥 10!짜리 브루트포스를 잘 구현해주면 된다. 티어를 까봤는데 P5라 많이 놀랐다. 가볍게 G3 주고 왔다.

 

9614 - 잠금 패턴과 스패닝 트리

 

문제에 설명이 잘 써있다. 이를 그대로 구현하면 된다. 행렬식은 가우스 소거법 후 대각 성분들을 모두 곱한 것과 같은 값을 가진다. 부호가 바뀌긴 하는데, 이 문제에서는 크게 중요하지 않은 것 같다. 여담으로, OEIS에 검색하면 나온다고 한다.

 

20368 - 트리 위의 폴 가이즈

 

조금 생각하다가 어려워서 접었다. 업솔빙 예정