Educational Codeforces Round 114 (Rated for Div. 2) (Virtual)

2021.10.06

실수를 많이 했는데도 좋은 성적을 얻었다.

A

Problem - A - Codeforces

2n개의 bracket을 사용해 서로 다른 n개의 제대로된 bracket set을 만드는 문제였는데

그냥 n = 4인 경우

(((()))), ((()))(), (())()(), ()()()() 이렇게 해주면 되므로 잘 생각해보면 쉬운 문제였다.

B

Problem - B - Codeforces

연속된 문자가 나타나는 횟수를 조절하는 문제로 실제로 해당 문자를 만들지 않아도 되어 훨씬 쉬워진 문제였다.

최대로 만들 수 있는 경우와 최소한으로 만들 수 있는 경우 사이에 존재하면 전부 만들 수 있다고 말하면 되는 문제였는데, sort시 오름 차순 정렬인것을 내림차순으로 착각하고 풀어서 1번 WA가 나왔다..

제대로 풀자 제발...

C

Problem - C - Codeforces

팀에서 드래곤의 방어력 $x$보다 힘이 높은 인원 한명을 뽑아 드래곤을 죽이러 가고 드래곤의 공격력 $y$ 보다 나머지 전체 팀의 힘이 높게 막아야하는 게임이다.

이분 탐색(lowerbound)를 사용해 팀내에서 드래곤의 방어력보다 높은 인원을 탐색하여 없다면 코인을 써서 만들고, 있다면 그 인원과 그 인원보다 약한 인원중 가장 강한 인원이 나가서 싸울때의 경우를 비교하면 된다.

$x$보다 힘이 높은 인원이 없는 경우

1. 남은 인원의 힘의 합계가 $y$보다 낮을 경우

$x - maxpower + y - sum +maxpower = x+y-sum$ 만큼의 코인을 사용해야 막을 수 있다.

2. 남은 인원의 힘의 합계가 $y$보다 높을 경우

$x-maxpower$ 만큼의 코인을 사용해야 막을 수 있다.

$x$보다 힘이 높은 인원이 존재하는 경우

$$min(x-team[lowerbound] + max(y-sum+team[lowerbound],0), \x-team[lowerbound-1] + max(y-sum+team[lowerbound-1],0))$$

이때 주의할 점으로 lowerbound가 0인 경우를 제외해 주면 됩니다.

본 문제를 풀때 범위 생각을 안하고 int를 사용해서 2번 정도 틀려버렸다... 꼭 범위를 보자...

D

Problem - D - Codeforces

ban된 빌드를 제외한 최적의 빌드를 짜는 문제다.

선택할 아이템의 개수 10개, 각 slot별 아이템의 개수 20만개, 밴 된 빌드 수 10만개로 bitmasking도 안되고 이걸 어케 풀지 하다가 그냥 무지성 10차원 bfs를 박아보기로 했다.

나는 priority queue를 사용해서 맨 뒤에서부터 bfs를 하는 형식으로 해결하였으나 제출 할 때에도 이게 과연 TLE를 버틸 수 있을까 했는데 다행히도 TLE는 나지 않았다.

에디토리얼에 따르면 ban된 빌드에서 1칸씩 이동한 것 + 맨뒤의 아이템들을 선택한 경우(밴이 없을 경우 가장 좋은 경우)를 비교해 가장 좋은걸 리턴하면 되어 훨씬 빠르게 푸는 풀이가 있었는데 Time limit이 1초였다면 이 해답으로 풀어야만 했다.

시간 내에 이 문제를 이 방식으로 생각해 낼 수는 없었을것 같다...