20.03.13 ~ 20.04.10 PS Training

PS 실력을 키우기 위해 3월 13일부터 4월 10일까지 총 4주동안 적절한 문제들을 골라서 연습했습니다.
이 글에서는 연습에서 사용한 문제들과 문제에 관한 후기와 몇 가지 스포를 포함하고 있으니 주의 바랍니다.

1주차

1번 : 듀얼 그래프를 만들고, 각 점이 위치한 평면을 스위핑으로 구해주면 됩니다.. 구현이 많이 귀찮습니다.
3번 : 재밌는 문제입니다. 풀이는 여기에서 볼 수 있습니다.
4번 : 서로 다른 팰린드롬의 개수가 최대 N개라는 것에서 풀이가 시작됩니다. 풀이는 여기에서 볼 수 있습니다.
5번 : 세그먼트 트리의 각 노드가 최대 몇 번 값이 변하는지 생각해보면 풀이가 나옵니다. 풀이는 여기에서 볼 수 있습니다.
7번 : 갓문제. 조만간 풀이를 작성할 예정입니다.
8번 : 꽤 직관적인 풀이가 존재합니다. 조만간 풀이를 작성할 예정입니다.
9번 : 1행과 1열의 값만 정해주면 나머지 칸을 채울 수 있다는 것은 자명합니다. 1행과 1열의 값을 고정했을 때 $A_{i, j}$의 값을 O(1)에 계산하는 수식을 찾고 열심히 식을 잘 만지면 웰노운 자료구조 문제가 튀어나오게 됩니다.
10번 : 웰논
12번 : PBS
14번 : 각 식물의 키를 h-tk로 저장하면 편하게 처리할 수 있습니다. 세그먼트 트리의 리프노드에 pq를 넣어주고, 트리의 각 노드에서는 (현재 구간의 식물 개수, 현재 구간의 식물 키의 최댓값)을 관리해주면 문제를 풀 수 있습니다.
15번 : mcmf

2주차

1번 : 기-하. 풀이는 여기에서 볼 수 있습니다.
4번 : 어떻게 설명해도 rkm0959님보다 잘 설명할 수는 없을 것 같습니다. orz
6번 : Lazy Propagation 연습 문제. 풀이는 여기에서 볼 수 있습니다.
7번 : 그래프 모델링 후 오일러 투어를 해주면 됩니다. 더 쉬운 풀이가 존재하는 것 같습니다.
9번 : 14번과 비슷하게 풀 수 있습니다.
10번 : songc님 블로그에 잘 나와있습니다. 1월에 비슷한 테크닉을 쓰는 문제를 본 기억이 있는데, 이런 류의 문제를 더 풀어보고 싶습니다.
12번 : Tree DP식을 세우면 CHT꼴이 나옵니다. CHT에 있는 직선을 y축 방향으로 평행이동하는 연산과 두 개의 CHT를 합치는 연산을 잘 구현해주면 풀 수 있습니다.
13번 : Tree DP식을 세우면 CHT꼴이 나옵니다. 점화식이 조상들만 참조하기 때문에 구현이 깔끔해집니다. CHT RollBack만 어떻게 잘 구현하면 됩니다. 풀이는 여기에서 볼 수 있습니다.
14번 : 풀이는 여기에서 볼 수 있습니다.
15번 : 맞았는데 왜 틀려요?
16번 : 씨너리. koosaga님 블로그 orz