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식을 모두 구할 수 있다.