[알고리즘] Educational Codeforces Round 122 (Rated for Div. 2)

버추얼에 참가했다.

 

이번 대회는 다른 대회보다 쉬웠던 것 같다.

퍼포가 엄청났겠는데

 

A - Div. 7 [Solved!]

정수가 하나 주어졌을 때 변화하는 자릿수를 최소로 하며 7의 배수로 만드는 문제이다.

 

7의 배수이면 그냥 출력하고 아니라면 1의 자리를 0~9까지 변화하면서 7의 배수가 되는 수를 출력한다.

자릿수를 하나만 변화시켜도 7의 배수를 만들 수 있다.

 

B - Minority [Solved!]

이진문자열이 주어졌을 때 부분 문자열을 골라 0, 1중에 개수가 작은 문자를 전부 삭제한다.(같으면 무효) 이때 삭제한 문자의 수의 최댓값을 구하는 문제이다.

 

전체 문자열을 부분문자열로 선택하고 둘 중에 개수가 작은 문자의 수를 출력하면 된다.

만약 같은 경우는 갯수-1을 출력하면 된다.

 

C - Kill the Monster [Solved!]

몬스터와 플레이어의 능력치가 주어졌을 때 플레이어가 몬스터를 해치울 수 있는지 출력하는 문제이다.

단, 플레이어가 먼저 공격을 하고 플레이어는 전투 전에 아이템을 구입할 수 있다.

코인 $1$을 소비하여 공격력을 $ w $, 체력을 $ a $증가시킬 수 있다.

 

얼마 전에 RPG Extreme을 풀어서 재밌게 풀었다.

몬스터 체력, 몬스터 공격력, 플레이어 체력, 플레이어 공격력을 각각 $h_m, d_m, h_c, d_c$라고 하자.

몬스터가 플레이어를 이기려면 $\lceil \frac {h_c}{d_m} \rceil$번, 플레이어가 몬스터를 이기려면 $\lceil \frac{h_m}{d_c} \rceil$번 공격해야 한다.

위 두 수를 각각 $n_m, n_c$라고 하면 $n_m \ge n_c$일 때 플레이어가 이기고, $n_m < n_c$일 때 몬스터가 이긴다.

또한 코인이 $k$개 주어졌으므로 $0\le i \le k$에서 플레이어의 능력치를 $ h_c + ai, d_c + w(k-i)$로 정하고 한 번이라도 이기는지 확인하면 된다.

$k$제한이 $2\cdot 10^5$이므로 완전 탐색하면 된다.

 

D - Make Them Equal

길이가 $n$이고 $1$로 초기화된 배열 $a$를 적당한 연산을 $k$번 사용해서 배열 $b$로 만들고 싶다.

연산은 $a_i := a_i + \lfloor \frac{a_i}{x} \rfloor$이다. ($x$는 자연수)

연산이 끝난 후 $a_i = b_i$인 $i$에 대해 $c_i$의 코인을 얻는다고 할 때 얻을 수 있는 코인의 최댓값을 구하는 문제이다.

 

떠오르는 아이디어는 있는데 계속 WA를 받아서 포기했다. Editorial이 올라오기 전이어서 생각했던 아이디어를 적어보고자 한다.

우선 $b_i$를 만드는 최소 횟수를 $dp$테이블에 저장하자.(제한이 $1000$이므로 $O(n^2)$으로 충분하다.)

예를 들어 $2 \rightarrow 1, 4 \rightarrow 2, 5 \rightarrow 3$

그러면 최대 무게가 $k$이고 $dp[b_i]$를 무게로 하고 $c_i$를 가치로 하는 배낭문제로 바뀐다. (근데 난 배낭문제 푸는 법을 몰랐다.)

그렇게 그리디하게도 풀어보고, 배낭문제 구글링을 통해서도 풀어봤는데 WA가 나왔다...

(추가)

Editorial에서 standard problem이라고 하는걸 보니 배낭문제는 맞는거같고 최대가 12인걸 고려해서 TLE도 안나왔는데 그냥 구현을 잘못한 것 같다.

 

슬슬 코포에 감이 잡히는게 느껴지고 조금만 더 노력하면 블루 갈 수 있을 것 같다.