7/14~7/15 Codeforce 연습

학기가 끝났다. 정말 열심히 놀았다.

학점도 적당히 받았고 하니 이제 PS를 해보자!

1000-1500 rating의 그리디 문제들을 잡았다.

1703F. Yet Another Problem About Pairs Satisfying an Inequality

문제에서 요구하는 식이 웃깁니다. $a_i<i<a_j<j$라..

 

sol) DP를 사용합니다.

$a_1$부터 $a_n$까지의 원소들에 대해 위 조건을 만족하는 쌍의 개수를 $dp[n]$이라고 합시다.

그러면 이제 두 가지로 나뉘는데..

1. $n+1 \leq a_{n+1}$

이러면 $a_{n+1}$이 $dp[n+1]$에 미치는 영향은 없습니다.

 

2. $a_{n+1}<n+1$

이러면 고민해야 하는 것은 앞의 $a_k < k$ ($k<n$)을 만족하는 $k$들에 대해서 $k < a_{n+1}$을 만족하는 $k$의 개수가 몇 개이냐는 것입니다.

DP의 앞쪽 항을 채우면서 $a_k < k$($k<n$)를 만족하는 것들을 순서대로 저장해 두고, 이를 $\{b\}$라 하면,

$\{b\}$에서 std::lower_bound를 통해 우리가 원하는 값을 찾을 수 있습니다.

이를 $tmp$라 하면 $dp[n+1] = dp[n]+tmp$가 성립합니다.

 

이제 점화식이 완성되었으므로 풀립니다. 시간복잡도는 $O(n\log n)$ 입니다.

 

1702D. Not a Cheap String

전형적입니다.

 

sol) a, b, c..순으로 가능한 만큼 많이 써서 점수보다 작게 만들면 됩니다.

1. 전체 알파벳 개수를 각각 세 줍니다.

2. a, b, c.. 순서대로 (개수)*(해당 점수) 를 더해 주어진 점수보다 작은 최대 점수를 얻습니다.

여기서 최종 문자열에 포함된 알파벳 개수를 얻습니다.

3. 이후 문자열 전체를 돌면서 2.에서 얻은 개수만큼의 알파벳을 남겨 최종 문자열을 얻습니다.

시간복잡도는 $O(n)$입니다.

1702C. Train and Queries

마음에 안 드는 문제지만 풀었으니 그만입니다.

 

sol) std::map을 활용합니다.

$a \rightarrow b$로 이동하고 싶을 때, 가장 왼쪽에 있는 $a$가 가장 오른쪽에 있는 $b$보다 왼쪽에 있으면 됩니다.

두 map을 관리하는데, 하나는 시작점을 관리하고, 하나는 끝점을 관리합니다.

전체 정류장을 순회하면서 처음 등장하면 시작점에, 그렇지 않으면 끝점을 계속해서 갱신합니다.

이제 위 방법대로 쿼리를 해결하면 $O(n\log n)$에 풀립니다.

1701C. Schedule Management

아..이런 걸 잘 풀어야 하는데

사실상 알고리즘 분류 안 봤으면 못 풀었을 문제

 

sol) 사실 전형적인 Parametric Search 문제입니다. 

진짜 말도 안되게 많은 경우의 수가 있고, 최솟값을 물어보는.. 그런 문제입니다. 3년 전 Reply Challenge에서도 털린 유형입니다. 

"시간 $k$ 이하로 모든 Task를 해결할 수 있는가?" 라는 결정 문제를 풉시다. 

일단 proficient한 Task들을 $k$개 아래로 다 집어넣고, 남은 Task들을 적당히 끼워넣을 수 있는지 확인하면 됩니다. 

구현 방법에 따라 다르겠지만, 저는 $O(n)$에 했습니다. 시간복잡도는 $O((n+m)\log X)$입니다.

 

코딩 고수 되고 싶다.

이틀 뒤 Div2 참여로 또 돌아오겠습니다.