2020/06/27 ~ 2020/07/03

2020/06/27

길었던 시험기간이 끝나고 다시 PS에 복귀했다.

2020년 IOI 대표 선발고사가 2주 앞으로 다가왔으니, 이제 PS에 집중해서 공부해야겠다.

 

https://codeforces.com/contest/1373

Dashboard - Educational Codeforces Round 90 (Rated for Div. 2) - Codeforces

새벽에 에듀 코포 버추얼을 돌았다. 코포를 안한지 너무 오랜 시간이 지나서 감이 다 떨어졌다... A 푸는데 13분, B푸는데 27분의 처참한 실력이었지만 2시간 안에 어찌저찌 F까지 풀어서 100등정도 했다. F는 정해와는 다른 풀이지만 JOIOC 2019 송금과 비슷한 방법으로 이분탐색으로 풀었다. (사실 함수의 볼록성을 가정하고 삼분탐색으로 열심히 비벼보려고 했지만 결국 이분탐색으로 풀렸다.) 코포 실력이 엄청 떨어진 것을 실감할 수 있었던 것 같다.

 

오늘부터 선발고사에 기하 문제가 100% 나온다는 확신을 갖고(?) 하루에 기하문제를 적어도 한문제씩은 풀어야겠다.

그래서 기본적인 Graham's Scan, Andrew's Algorithm을 다시 한번 짜봤다. (기하를 손절하다 보니 다시 짜는거도 익숙하지 않았다...)

 

https://www.acmicpc.net/problem/15974

15974번: 공룡 발자국

문제에서 요구하는 그대로 $dp1(i, j)$, $dp2(i, j)$를 발가락에서 골로, 골에서 발가락으로 가는 간선을 이용할 때 점의 최대 수라 정의하면 Naive 하게 $O(N^3)$의 dp 풀이가 나온다. $(i, j)$ -> $(j, k)$ 의 transition에서는 $j$하나만 고정된다는 점을 이용하면 누적 최댓값의 느낌으로 최댓값을 뿌려줄 수 있고, $O(N^2logN)$ 의 풀이가 나온다.

 

https://www.acmicpc.net/problem/16191

16191번: Utilitarianism

 

또, 오늘부터 플3~다5 정도 되는 문제들을 좀 많이 빨리 푸는 연습을 하기로 했다.

https://www.acmicpc.net/problem/3012

3012번: 올바른 괄호 문자열

단순히 가장 왼쪽 칸과 매칭될 칸을 나이브하게 정해주고, 그 구간 기준으로 두 개로 쪼갠 후 DP를 하면 된다. 구간의 개수가 $O(N^2)$, 각 구간마다 매칭될 칸을 정하는데 $O(N)$이니, $O(N^3)$에 문제를 해결할 수 있다. 여담으로 출력이 매우 귀찮은 형태여서 약간의 꼼수로 오버플로우를 유도한 후 오버플로우 결과와 모듈러 결과를 비교해서 해결했다. (28분)

 

https://www.acmicpc.net/problem/16119

16119번: Cherrypick

일단 격자의 수들이 1000 이하이고, 거리함수가 체비셰프 거리의 제곱임에 집중하자. 만약 거리가 $sqrt(1000)$ 이상이라면 $A[i][j]-dist^2$값이 음수가 되어서, 가장 넓게 정사각형을 잡아도 최대 31칸임을 알 수 있다. 따라서 각 줄마다 길이 0, 2, 4, ..., 62칸짜리 구간 중 최댓값을 전처리해놓고, 전처리한 값들을 순회하며 각 칸에 대해 따로따로 답을 구해주면 된다. 시간 복잡도는 $O(N^2*sqrt(1000))$이다. 처음에 전처리 값을 슬라이딩 윈도우로 데큐를 이용해서 구하다가 시간초과를 받는 등의 삽질을 해서 시간이 꽤 오래 걸렸다. (48분)

 

https://www.acmicpc.net/problem/2912

2912번: 백설공주와 난쟁이

예전에 어디선가 한번 본 문제였다. 일단 과반수의 가장 유용한 성질은 구간을 여러 개로 쪼갰을 때 전체의 과반수는 그 구간들 중 적어도 하나의 과반수여야 한다는 것이다. 일단 구간 내에 특정 색의 수를 세는 문제는 이분 탐색을 이용해 쉽게 풀 수 있다. 그러니 세그먼트 트리 하나를 관리하며 그 구간 중에서 과반수를 넘는 것을 전처리하자. 이제, 쿼리를 답할 때는 그 구간에 해당하는 세그먼트 트리의 $O(logN)$개의 노드들의 과반수 값이 모두 후보이며, 이를 각각 세주면서 전체 과반수 조건을 만족하는지 확인한다. (15분)

 

https://www.acmicpc.net/problem/17139

17139번: 습격자 초라기와 쿼리 (Normal)

쿼리가 없다면 일반적인 DP문제인데, 쿼리가 있으니 DNC segment tree를 생각할 수 있다. 기본적으로 선택할 수 있는 최대 구간이 두칸이므로, 양쪽 구간에서 2줄 중 어떤 칸을 먹을지 4가지 경우의 수를 양쪽 끝에서 하면 되니, 한가지 상태는$4*4=16$개의 칸을 가진 행렬로 표현된다. 이제 합쳐주는 과정은 $4^3$의 시간을 투자하여 합쳐주면 된다. (28분)

 

2020/06/28

https://www.acmicpc.net/problem/19055

19055번: Nutella's Life

단순한 CHT 문제이다. dp(i) = i번째 대회에 참가했을때까지의 누적 보상의 최댓값 이라 정의하면 $dp(i)=max(dp(j)+(i-j)(i-j-1)/2+A[i])$ 꼴의 점화식이 나오고 식 정리를 하면 $A[j]<=A[i]$인 $j$에 대해서 저 식 중 최댓값을 찾는 문제가 되고, 이는 펜윅 트리에 CHT 자료구조를 하나씩 박아서 해결할 수 있다. 또한, CHT 에 쿼리 넣는 값이 단조 증가함을 이용해 전체적으로 $O(NlogN)$에 해결하도록 할 수 있지만, 이것을 구현했을 때 맞왜틀로 인해 시간을 조금 날렸다. (42분)

 

https://www.acmicpc.net/problem/1805

1805번: 나무수송

2020/06/29

 

11503
18916
1848