Codeforces Round 910 (Div. 2)
Codeforces Round 910 (Div. 2)에 참가했다.
예상했던 것보다 훨씬 어려워서 놀랐다. 풀다가 벽에 막힌 느낌이 강하게 들었고, 문제도 얼마 풀지 못해서 처음으로 레이팅이 떨어질까 걱정했다.
00:05 AC
항상 1회 이하의 연산으로 가능하다.
B의 개수를 세서 $k$보다 클 때, 같을 때, 작을 때로 분류해서 처리하면 된다.
00:23 AC
어떤 수를 쪼갤 때, 어떻게 해야 최적인지의 여부는 뒤에 존재하는 수들에 따라 달라진다. 따라서, 뒤에서부터 본다는 접근은 자연스럽다.
$a_i > a_{i+1}$인 $i$에 대해, $a_i$를 모두 $a_{i+1}$이하인 수들로 나눠야 한다.
이 때 수행해야 하는 연산 횟수가 최소여야 함이 1순위 목표이고,
쪼갠 수들 중 가장 작은 수가 가능한 한 커야된다는 것이 2순위 목표이다.
수행해야 하는 연산의 최솟값 $x = \lfloor \dfrac{a_i-1}{a_{i+1}} \rfloor$이고,
이 때 가장 작은 수 $v = \lfloor \dfrac{a_i}{x+1} \rfloor$이다.
쪼개는 연산을 수행한 뒤에는, $a_i = v$로 만들어주면 된다.
00:55 AC
$N\times M$ 그리드에서의 최단 경로 길이는 $N+M-2$이고, $k$가 이보다 작은 수면 볼 필요도 없이 "NO"이다.
또한, $K$의 parity와 최단 경로 길이의 parity가 다르다면 역시 "NO"이다. 최단 경로가 아닌 모든 방법은 최단 경로에서 불필요한 이동을 상쇄할 이동이 반드시 짝을 이뤄야하기 때문이다.
지금까지 "NO"가 나오지 않았다면, 사이클을 적절히 이뤄 항상 가능하게 만들 수 있다.
구현 방법은 여러 가지가 있을 것 같다.
C를 풀고 나서 DEF를 하나씩 읽어봤는데, 얘 말고는 가망이 없어보여서 남은 시간을 여기에 모두 쏟아부었다.
$i, j$를 고르는 경우의 수를 여러 개 생각해봤다.
1. $a_i < b_i$이고 $a_j < b_j$인 경우
2. $a_i < b_i$이고 $a_j \ge b_j$인 경우
등등 생각해봤는데, 도저히 모르겠다.
정렬해서 이분 탐색으로 찾을 수 있는지 보려고 식을 짜보는데 이건 그냥 안되는 것 같다.
읽어보자마자 도망쳤다. 감도 안 잡힌다.
E에서 도망치고, 이 문제는 타입 별로 분류해서 풀면 되겠다 싶어서 생각해보았다.
1st type : 모든 빈 칸을 다 막는다.
2nd type : 최단 경로를 찾고 역추적해서 이 곳을 제외한 모든 빈 칸을 막는다.
3rd type : 최단 경로를 찾고, 그 최단 경로에 포함된 모든 칸을 한 점으로 본 뒤에 그 점에서의 최단 경로를 한 번 더 찾는다. 모두 역추적해서 그 칸을 제외한 빈 칸을 막는다.
근데 내가 F를 풀 확률보다 D를 풀 확률이 더 높다고 판단해서 D로 다시 갔다.
대회가 끝나고 이 선택을 제일 후회했다.
Rating
+178
1406 -> 1584
블루까지 단 16점 남았다..