오늘의 PS (7) - solved.ac D3 달성

6월 5일에 solved.ac 시즌이 갱신된다는 공지가 있었다. 이를 확인했을 때 내 티어가 D4였는데, 4는 예로부터 불길한 숫자였기 때문에 D3으로 올리려고 문제를 좀 풀었다. P2~D3 범위에서 골랐는데, 랜덤으로 뽑은 것도 있고 풀이를 대충 알고 있어서 짠 것도 있고 그냥 재밌어보여서 푼 것들도 있다. 일당 하나씩은 해당 범위의 문제들을 풀었기 때문에 날짜별로 정리해보려고 한다.

 

5/16 - 15879 Edge Coloring

5/13 팀 연습에서 Cycle Basis가 들어가는 문제를 풀었는데, 이 문제도 비슷한 원리를 이용하는 문제라는 것이 생각나서 풀었다. 풀이는 Cycle Basis를 안다면 쉽게 찾을 수 있는 것 같다.

 

5/17 - 1739 도로 정비하기

랜덤으로 걸린 문제이다. 각 도로에 0 혹은 1의 방향성을 부여해야 하니 대충 2-SAT 일 것이라 유추할 수 있다. 쓰는 도로가 하나일 경우 1-SAT 항을 넣어주면 된다. 두 개일 때는 식을 써보면 뭔가 잘 안맞는 식이 나오는데, 이를 잘 정리하면 2-SAT에 맞는 식으로 바꿀 수 있고, 그대로 코딩하면 된다. if문을 여러 개 써야 하는게 조금 짜증나긴 한다.

 

5/18 - 25019 날다람쥐

2022 선발고사 문제이다. 문제가 떴을 때부터 뭔가 재밌어 보여서 눈여겨둔 문제라 잡았다. 우선 나이브하게 생각할 수 있는 2차원 DP를 \(DP(i,x)\)를 \(i\)번째 기둥 높이 \(x\)에 도착할 때 최소 비용으로 정의하면, \(x\)를 \(x\)축으로 생각해 좌표평면에 나타낼 수 있다. i가 증가하면 그래프를 왼쪽 아래로 평행이동한 후 새 직선을 넣어주는 것을 반복하면 되는데, 이를 Slope Trick과 비슷하게 직선들을 잘 관리해주면 된다. 그래프의 평행이동은 원점이 되는 좌표를 갱신하는 것으로 처리할 수 있고, 앞 또는 뒤에서 직선을 뺀 후 새로 넣는 것은 Deque을 이용해 처리하면 된다. Slope Trick 문제를 처음 풀어봤는데 재밌는 것 같았다.

 

5/19 - 16914 K번째 부분 문자열

우선 11479의 풀이를 알면 서로 다른 부분 문자열의 개수를 구할 수 있다. 여기서 K번째 부분 문자열은 앞에서부터 보면서 해당 Suffix로 만들 수 있는 개수를 계산해주다가 0이 될 때를 잘 찾아서 출력해주면 된다. 누적합+이분탐색을 이용하면 각 쿼리를 \(O(logN)\)에도 처리할 수 있지만, 이 문제는 쿼리의 수가 작아서 각 쿼리를 \(O(N)\)에 처리해도 된다.

 

5/20 - 팀 연습

팀 연습에서 P2 하나, D4? 하나를 풀었다. 사실 M번은 아직까지도 적정 티어가 어디인지를 모르겠다. 이 글 보시는 분들은 푸시고 기여 부탁드려요

 

5/21, 22 - 7626 직사각형, 3392 화성 지도

주말은 여행 중이었기 때문에 새로운 문제를 풀기엔 무리가 있었고, 팀 연습에서 푼 16421 코드를 이용해 비슷한 문제들을 풀었다. 대충 비슷하게 하면 될 줄 알았는데, XOR 세그보다 훨씬 어려운 세그를 써야 해서 놀랐다. 저런걸 어떻게 생각하지?

 

5/23 - 8217 유성

PBS라는 것은 알고 있었기 때문에 풀이를 내는 것은 어렵지 않았다. 다만, 생각지도 못한 예외가 하나 있어서 여러 번 틀렸다.

 

5/24 - 3319 전령들

D4 이상을 풀면 한방에 올라가는 상황이라 좀 높은 티어 문제를 골랐다. Tree DP 식 세우기와 그 식이 CHT가 된다는 것을 아는 것 까지는 적당히 쉬웠던 것 같은데, CHT를 롤백하는 방법을 몰라서 좀 헤멨다. 리차오 트리를 쓰면 된다는 것은 알고 있었지만 짜본 적이 한번도 없었다. 나름대로 몇 가지 방법을 써봤지만 TLE이거나 틀리거나 MLE길래 풀이를 까봤다. 핵심 아이디어는 직선 삽입을 스위핑이 아니라 \(O(logN)\) 이분탐색으로 하는 것이었고, 이분탐색으로 삽입을 하면 한 직선의 정보만 바뀌기에 롤백을 \(O(1)\)에 할 수 있다. 리차오 트리도 한 번쯤은 짜봐야겠다고 생각했다.

 

어려운 문제 푸는건 너무 어렵다. 연습해야지..