CodeForces Round 953 - Div 2

 

https://codeforces.com/contest/1978

 

Performance Rating : 2750

 

A

$a_1,\cdots, a_{n-1}$중의 최댓값과 $a_n$을 더하여 출력하는 문제였다.

 

B

$a>b$, $a<b-n+1$, $a\leq b\leq a+n-1$으로 경우를 나누면 쉽게 구할 수 있다.

 

C

$n$이 홀수일 때와 짝수일 때 Menhattan value의 최댓값을 계산해보았다. $n=2k$이면 $2k^2$, $n=2k+1$이면 $2k(k+1)$이 최대였다. $k$가 홀수이거나 최댓값보다 크면 "No"를 출력해주었다. 나머지 경우에 대해서는 처음에 $a_i=i$로 설정해두고 $k$가 $0$이 될 때까지 양 끝의 숫자를 바꾸는 것을 반복해주면 되겠다는 생각을 했다. 그러나 WA를 받았고 오버플로우가 문제일 것이라고 생각해 $n$의 자료형을 $ll$으로 바꿨으나 또 WA가 나와 문제점을 찾다가 $n$이 홀수일 때 최댓값 식을 잘못 썼다는 것을 알았고 고쳤다.

 

D

결국 $c$는 몇개를 제거한 뒤 첫 번째 요소에 더해지기 때문에 $a_1$에 더해놓고 시작해도 된다는 것을 생각했다. $a_i$가 최댓값인 것이 아니라면 $a_i$를 최댓값으로 만들기 위해 $a_1,\cdots,a_{i-1}$가 모두 제거되어야 한다는 것을 관찰했다. 결국 $a_1+\cdots+a_i$가 최대가 아니라면 최대인 $a_j$까지 제거하여 $i$가 답이 되고, 최대라면 $i-1$이 답이 된다.

 

E

$s_i$가 $1$이 될 조건부터 떠올려 보았다. $s_i=1$이거나 $t_{i-1}=1$, $t_{i+1}=1$이거나 $s_{i-2}=0$, $t_{i+1}=1$이거나, $t_{i-1}=0$, $s_{i+2}=0$이거나, $s_{i-2}=0$, $s_{i+2}=0$이면 된다. 다섯 가지 경우에 대해 $s_i$가 $1$이 되기 위해 필요한 앞뒤 숫자의 개수가 달라지므로 이를 저장해 두었다. $s_i$가 $1$이 되기 위한 조건으로 $i-2$, $i+2$인덱스 까지만 보므로 누적합으로 1로 만들 수 있는 위치를 모두 세주고 구간의 앞 2개, 뒤 2개에서 앞뒤가 잘려 불가능해진 것의 개수를 빼주는 방식으로 답을 구할 수 있겠다는 생각을 했다.

 

F

$b_{i,j}=b{i+1,j+1}$이라는 점과 $k\geq 2$라는 점에 주목해 우하향하는 대각선 상의 숫자들끼리는 무조건 연결되어 있다는 것을 관찰했다. 이를 관찰하고 나니 문제가 $v_i=a_{i+1}(1\leq i\leq n-1)$, $v_i=a_{i-n+1}(n\leq i\leq 2n-1)$에서 component의 개수를 구하는 문제로 바뀌었다. $a_i\leq 10^9$인줄 알고 모든 소인수를 보는 방법을 포기했는데, $a_i\leq 10^6$이라는 제한을 보고 $10^6$이하의 자연수에 대해 소인수를 모두 구해놓을 수 있다는 것을 알게 되었다. 각 소인수에 대해 직전에 나왔던 그 소인수의 배수의 인덱스를 map에 넣어두고 거리가 $k$이하일 때 묶어주면 모든 소수에 대해 그 소수를 공약수로 가지는 숫자들을 묶어줄 수 있다. Dsu를 이용해서 component의 개수를 관리해주는 풀이를 작성했으나 WA를 받았다. 고민을 해보니 $a_i=1$이면 우하향하는 대각선 상의 숫자들도 연결되지 않는다는 점을 빼먹었다. 그래서 이를 고려한 풀이를 재작성했으나 답의 범위가 int 범위를 넘어간다는 사실을 간과하여 WA를 한번 더 받았다.