CodeForces Round 961 - Div 2

https://codeforces.com/contest/1995

 

 

Performance Rating : 2250

 

A

$n^2$개의 점이 $n$개짜리 그룹 하나, $1,\cdots,(n-1)$개짜리 그룹 각각 2개씩으로 나누어지므로 최대한 큰 그룹으로 사용해 주는 것이 이득인데, 구현과정에서 시간이 조금 걸렸다.

 

B1

map에 나온 숫자들의 개수를 저장해 두고 map을 순회하면서 $x$, $x+1$의 개수를 바탕으로 답을 구할 생각이었다. 답이 $m$을 초과하면 안 되므로 $x$짜리를 몇 개 선택하는지에 따라 최댓값을 모두 계산하여 그중 최댓값을 답으로 출력했다.

 

B2

B1에서 쓴 풀이를 그대로 쓸 수 없었다. 각각의 개수가 $10^9$개까지 나오기 때문이었는데, 고를 수 있는 숫자가 $x$, $x+1$뿐이라는 것을 활용해야겠다는 생각이 들었다. $x$를 골라놓고 $x+1$로 대체하면 1씩 증가시킬 수 있기 때문이다. 고를 수 있는 $x$의 최대 개수는 $m/x$인데 이 값이 $mp[x]$ 이하이면 $x\times (m/x)+\mathrm{min}(mp[x+1],m/x)$까지 모든 수를 만들 수 있다. 그러므로 $\mathrm{min}(m,x\times (m/x)+\mathrm{min}(mp[x+1],m/x))$가 $x$, $x+1$을 가지고 만들 수 있는 최댓값이 된다. $m/x$가 $mp[x]$보다 큰 경우에는 우선 $x$를 $mp[x]$개 골라놓고 $x+1$을 고를 수 있는 만큼 고르고 $x$를 $x+1$로 최대한 바꾸는 과정을 통해 최댓값을 구했다. 식을 적는 과정에서 실수를 하여 1번의 WA를 받았다.

 

C

$a_i>a_{i+1}$인 경우에는 $a_{i+1}$을 몇 번 제곱해야 $a_i\leq a_{i+1}$이 되는지 확인하고 $a_i$를 제곱한 횟수를 더하면 $a_{i+1}$을 제곱해야 하는 횟수를 구할 수 있다. 예제를 보니 $a_i<a_{i+1}$인 경우를 생각할 필요가 있었다. 이때는 $a_i$를 몇번 제곱해야 $a_i> a_{i+1}$이 되는지 확인할 필요가 있어 보였다. $a_i$를 몇번 제곱하여 $a_{i+1}$과 같아지는 경우의 경곗값 처리에 유의하여 풀었다.

 

D

남은 80분의 시간 동안 정말 여러 생각을 했다. $2^c$개의 경우에서 선택된 문자들의 인덱스에는 1, 나머지에는 0을 넣은 배열을 활용해서 길이가 $k$이상인 연속한 0이 나오는지도 보는 풀이는 $O(n2^c)$이라서 포기했다. 생각한 다른 여러 풀이들도 모두 시간복잡도가 $O(n2^s)$이라서 문제를 풀지 못했다. 에디토리얼을 보니 $k$개짜리 연속합을 구하면서 불가능한 조합들을 비트마스킹을 통해 찾아나가는 풀이가 정해였다. 문제를 풀면서 특정 조합이 가능한지에만 집중을 하다 보니 놓친 것 같다. 가능한 조합들을 묻는 문제에서 불가능한 것을 제거하는 풀이도 가능하다는 것을 탑재해야겠다.