Educational Codeforces Round 167 (Rated for Div. 2)

https://codeforces.com/contest/1989

A에서부터 2번 꼬이고 시작한... 흠...

E 풀고 F는 감이 잘 안 잡혀서 그냥 딴거하러 갔다.

 

A. Catch the Coin

 

Monocarp의 최적 플랜은 코인을 향해 (+1, -1) 혹은 (-1, -1)로 이동하는 것이다.

코인이 (p, q)에 위치했을 때 Monocarp이 x = p에 도달하는 순간을 보면 (단, 편의상 p >= 0)

-> 코인은  (p, q - p + 1), Monocarp은 (p, -p)에 위치하게 된다.

따라서 q - p + 1 >= -p만 성립하면 되고, q >= -1이 Monocarp이 도달가능한 조건이다.

 

B. Substring and Subsequence

 

답이 되는게 S라고 하자.

그러면 S의 일부는 정확히 a와 일치해야할 것이고, 앞뒤에 적당히 b의 앞부분과 b의 뒷부분이 올 것이다.

따라서 a가 b의 [l, r]을 subsequence로 가진다면, 답은 a.length + b.length - (r - l + 1)이 될 것이다.

그러면 [l, r]의 크기를 최대한으로 늘려야 한다.

이때 a, b의 길이가 100으로 짧기 때문에 모든 l에 대해서 가능한 r의 최댓값을 직접 확인해보면 된다.

 

C. Two Movies

 

둘의 rating 변화가 다르다면 무조건 더 큰 것을 고르는게 이득이다.

왜냐하면, 더 작은 나머지 하나는 무조건 +0이나 -1이기 때문에 안하는게 손해가 아니고, 오히려 이득이기 때문이다.

그러면 맨 마지막에 남는것은 (+1, +1)들과 (-1, -1)들

(+1, +1)은 더 작은 쪽에 몰아주고, (-1, -1)은 더 큰 쪽에 몰아주면 된다.

 

D. Smithing Skill

만일 x > y라면 x개로 얻는 경험치가 y개로 얻는 경험치 이상이다. (무조건 같은 행동을 따라할 수 있음)

따라서 항상 a - b가 제일 작은 weapon을 만들었다가 녹이는게 이득이다.

-> a - b가 제일 작은 weapon을 만들었다 녹여야 녹인 이후 남는 ingot의 개수가 제일 많기 때문이다.

 

일단 dp로 1e6까지 ingot의 개수당 얻을 수 있는 최대 경험치를 계산해보자.

위에서 말한 것에 의해서 dp[x] = dp[x - (a[p] - b[p])] + 2 (단, k는 x >= a[q]인 모든 q중 (a[q] - b[q])가 제일 작은 것)

O(lgn) : 모든 weapon을 a값에 대해 정렬하고, x >= a인 모든 무기들의 (a - b)값의 최솟값을 관리하면 된다.

O(1) : 어차피 a, b값의 최대치가 1e6밖에 안되므로 정렬 대신 radix sort 하듯이 관리해주면 된다.

 

각 쿼리당 제일 효율이 좋은 무기를 여러번 만들면 무조건 1e6개 이하로 떨어트릴 수 있다.

즉, 제일 효율이 좋은 무기를 times번 만들 수 있다면 ans(c) = 2 * times + dp[c - (times) * (a - b)]

 

E. Distance to Different

 

A에서 같은 원소가 2번 반복되었을 때와, 서로 다른 두 원소가 1번씩 나타났을 때 B에서는 구분할 수 없다.

-> 1 2 2 1과 1 2 3 1의 B가 똑같다는 것이다.

-> 다만, 맨 앞과 맨 뒤의 경우에는 예외로 구분 가능하다 (1 1 2 2와 1 2 3 4의 결과는 다르다)

-> 따라서 맨 앞과 맨 뒤를 빼고 같은 숫자를 두 번 쓰는 것을 금지할 수 있다. (서로 다른 두 숫자로 대체)

 

설명과 풀이의 간결성 때문에 jiangly의 풀이를 기준으로 한다.

dp[x][y] = (길이가 x이고 사용한 숫자의 종류가 y개인 B의 경우의 수)로 정의하자.

단, y = K일 때는 예외적으로 'K개 이상'을 의미한다.

그러면 당연히 답은 dp[N][K]가 될 것이다.

-> dp[x][y] = dp[x - 1][y - 1] + dp[x - 1][y - 3] + dp[x - 1][y - 4] + ...이다.

-> sum[x][y] = dp[x][y - 1] + dp[x][y - 2] + dp[x][y - 3] + ...으로 정의하면,

-> dp[x][y] = sum[x - 1][y] - dp[x - 1][y - 2]를 통해서 dp식을 모두 구할 수 있다.