3/20~3/21 업다운랜디

최근에 업다운랜디의 존재를 알게 되어서 재밌어 보이길래 시작하게 되었다.

IBory님 블로그 보다가 알게 된 듯? 링크는 양해가 될 수 있으니 달지 말자..

 

내가 한 방식은 solved.ac에서 *g5 -@$me s#100.. 걸고 검색한 다음, 시프트 마음대로 누르고 가장 위에 나오는 문제를 풀었다. 타이머를 키는 시점은 문제 지문을 열어본 순간부터고, T분 안에 문제를 풀면 윗 티어로 넘어가고 못 풀면 아래 티어로 내려간다. T = (티어 - G5)*5분 + 30분이다. 예를 들어 P5 문제를 풀어야 하면, T = 5*5분 + 30 = 55분 안에 풀어야 한다.

 

나는 G2정도부터 시작했다. 

 

2632 피자판매(G2)

누적합 관리하는 문제였던 걸로 기억한다.

 

4198 열차정렬(G1)

조금의 관찰을 하면, i번부터 시작하는 LIS, i번부터 시작하는 LDS 구하기라는 것을 알 수 있는 문제였다.

 

15708 미네크래프트(P5)

개인적으로 재밌게 풀었다.

O(n^2)을 O(nlogn)으로 줄이는 과정이 필연적이라서 재밌었던 듯.

디디가 i개 돌을 채취한다고 했을 때, 몇 번째까지 가야될까를 생각하는 게 필연적이었다.

i개 돌을 채취할 수 있으면, i개 이하의 돌을 채취하는 것은 모두 가능하다는 것도 당연한 관찰이었다.

 

15783 세진 바이러스(P4)

플4의 벽에 막혀버렸다. SCC라는 건 눈치챘는데, 모든 SCC의 크기가 1인 경우는 구현 결과가 어떻게 되는지 제대로 모르고 있어서 SCC를 버리고 다른 풀이를 생각하다가 시간 안에 못 풀었다. Vermeil한테 힌트 듣고 풀었음.. 그냥 웰논인 문제였다. 

 

13016 내 왼손에는 흑염룡이 잠들어 있다(P5)

일단 트리에서 최대 거리이니 딱 트리의 지름이 떠올랐었다. 귀류법으로 답을 만드는 경로의 한쪽 끝은 무조건 트리의 지름임을 증명할 수 있다. 나는 dfs로 막 거리 찾아서 구현했는데, LCA를 통해 구현하면 더 간단한 것 같다.

 

2618 경찰차(P4)

역시나 플4에서 막혔다. dp인 거는 문제 읽고 5분 정도 보니까 나왔던 것 같은데, 끝끝내 풀 지 못해서 답 보고 해결했다.

dp[i][j] = 1번 경찰차가 i번 사건을 마지막으로, 2번 경찰차가 j번 사건을 마지막으로 처리했을 때 앞으로 이동해야 할 거리

로 dp table을 정의해서 풀 수 있다고 한다. 이렇게 dp table을 정의하는 방식을 처음 만나본 것 같다. 담에 비슷한 문제 만나면 풀어야겠다. 

이렇게 dp table을 정의하면 좋은 게, (i, j)만으로 다음 해결해야 할 사건 번호와 이동해야 할 거리까지 바로 알 수 있다. 

 

3015 오아시스 재결합(P5)

일단 O(n^2)이 안되니, O(nlogn)이나 O(n)을 생각해야 하는 문제였다. i번째를 기준으로 앞에서 쌍을 만드는 전형적인 생각을 하면 되었다. 모노톤 스택을 관리하면서, 이분탐색으로 자신보다 앞에 있으면서 자신보다 처음으로 큰 모노톤 스택의 인덱스를 찾아서 계산하면 되는 문제였다. 

 

평소에 G3~P3 정도 잡고 풀었는데, 맨날 골드 문제만 푸는 것 같아서 플레 좀 풀려고 업다운랜디를 하게 된 것도 있는데, 이 취지에 의하면 나름 성공한 것 같기도 하다. 별일 없으면 재밌어서 계속할 듯?