CodeForces Round 1021 - Div 1

https://codeforces.com/contest/2098

 

 

Performance Rating : 2300

 

A

우선 당연히 한 날짜에 베팅이 4개 이상이면 성립한다는 것을 생각했다. 그 후 같은 날짜로 2개가 있으면 $a_i+1$이나 $a_i+2$ 중 하나를 확정할 수 있다는 것을 관찰했고 이를 통해 앞에서부터 원소를 하나씩 확정해 나가면서 적어도 하나를 맞추도록 베팅이 가능한지 판단했다.

 

B

처음부터 접근을 잘못했다. $dp$로 카운팅을 하면 되는 문제로 파악하여 풀었는데 틀렸다. 틀린 이후 반례를 찾은 뒤 풀이를 고쳐보려 하였으나 도저히 고칠 엄두가 안나 C로 넘어갔다. 업솔빙을 해보니 그래프 모델링을 해서 경우의 수를 카운팅 하는 문제였다.

 

C

$(x, y)$를 지나고 기울기가 $frac{v_x}{v_y}$인 직선이 $(np, nq)$를 만나는지 파악하고 만난다면 $(p+q-2)+(p+q)/2+abs(p-q)/2$를 구하면 되는 문제였다. 우선 $xv_y+yv_x$가 $n\cdot \mathrm{gcd} (v_x, v_y)$로 나누어 떨어지는지 확인하여 답이 존재하는지 확인했다. 이후 유클리드 호제법으로 $p$와 $q$를 찾아 답을 구했다.