CodeForces Round 951 - Div 2

 

https://codeforces.com/contest/1979

 

Performance Rating : 2600

 

A

$\mathrm{min}( \mathrm{max}(a_1,a_2),\cdots, \mathrm{max}(a_{n-1},a_n))-1$을 출력했다.

 

B

예제를 보고 $|n-m|$의 최소 비트에 해당하는 숫자를 출력하는 것 같았고 proof by AC를 했다.

 

C

결국 어떤 수가 걸리더라도 비슷한 금액을 받아야 낭비가 없다는 생각을 했다. $1$부터 $n$까지 어떤 수가 걸리더라도 $1$부터 $20$까지의 최소공배수인 232792560만큼을 돌려받게 설정한 뒤 베팅 금액의 통합이 232792560보다 작은지 확인했다.

 

D

예제를 바탕으로 관찰을 한 뒤 casework를 했다. 결국 모두 $k$개씩 연속하게 만들어야 하는데 한 번의 시행으로는 마지막 그룹과 마지막인 그룹 하나만을 변경할 수 있다는 점을 바탕으로 casework를 진행했다. casework로 풀다 보니 실수를 좀 해서 2번 WA를 받았다. jiangly님의 코드를 보니 casework가 필요 없는 문제였다.

 

E

세 쌍의 점이 Manhatten triangle이 되려면 세 점중 두 점의 $x+y$ 또는 $x-y$가 같아야 한다는 것을 관찰했다. 점들의 좌표를 $(x+y,x-y)$로 저장하면 정렬해 두면 $(p,q)$점을 기준으로 $(p,q+d)$, $(p\pm d, r)\;(q\leq r\leq q+d)$인 점 2개가 있으면 된다는 것을 관찰한 뒤 이분탐색으로 각각의 점이 존재하는지 확인할 생각을 했다. 세 점 중 두 점의 $x-y$가 같은 경우는 배열에서 $x+y, x-y$를 swap 하고 다시 정렬한 뒤 같은 과정을 반복해 줄 생각을 했다. $d$가 정해져 있다는 것을 까먹고 어떻게 복잡도를 줄일까 20분을 고민하다가 $d$가 정해져 있다는 것을 보고 풀었다.