CodeForces Round 965 - Div 2

 

https://codeforces.com/contest/1998

 
Performance Rating : 2900
 
A
$(x_c, y_c)$를 중심으로 점대칭 시키는 것이 더 강한 조건이기 때문에 이를 만족시키도록 짰다.
 
B
주어진 $q_i=p_i(\mathrm{mod}\;n)+1$으로 잡으면 $i=1$, $j=n$일 때를 제외하고 $p_i+ \;\cdots\; +p_j=q_i+.\;\cdots\; q_j$가 성립하는 $i$, $j$가 존재하지 않기 때문에 답이 된다.
 
C
$a_i+median(c_i)$에서 $b_i=1$이라면 $k$번의 실행을 모두 $a_i$에 하는 것이 이득이고 $b_i$가 0인 $i$ 중 $a_i$가 최대인 것과 $b_i$가 1인 $i$ 중 $a_i$가 최대인 것 두 개만 보면 된다는 생각을 먼저 하였다. $b_i=1$일 때 최댓값을 구하는 것은 매우 간단하게 할 수 있었다. 하지만 $k$번의 시행을 하여 중앙값을 최대로 만드는 것은 $k$를 적절히 나누어 더해주는 방식으로는 구하기 힘들어 보였다. 그러나 중앙값이 $x$가 되기 위해 시행해줘야 하는 최소 횟수를 구하는 것이 상대적으로 쉬웠기 때문에 파라메트릭 서치를 활용해야겠다는 생각을 했다. 이를 구현해 맞았다.
 
D
Bessie가 $s$에서 시작한다고 했을 때 Elsie는 $s$보다 작은 곳에서 시작하는 bridge를 적절히 활용하여 Bessie보다 $i$칸 이상 앞질러야 한다. 우선 $i$번째 칸에서 시작하는 bridge를 이용해 이동했을 때 Bessie와 좁혀지는 차이를 $v[i]$에 저장해 놓고 Elsie가 $i$에 도착하기까지 따라잡을 수 있는 칸의 수를 $dp$를 활용하여 구했다. 그 후 Bessie가 $i$에서 출발한다고 했을 때 $ \underset{j<i}{\mathrm{max}}\;(dp[j]+\mathrm{max}\;v[j])$칸을 앞서갈 수 있다. 이 값은 앞서 구한 $dp$와 누적 최댓값으로 구할 수 있다. 앞지를 수 있는 칸의 수와 $i-1$을 비교하여 답을 구했다.
 
E1
백준 #10760과 유사하다는 느낌을 받았다. $a_i>a_{i+1}+ \;\cdots\; +a_{j-1}$과 $a_j>a_{i+1}+ \;\cdots\; +a_{j-1}$를 만족하면 $(i+1)$부터 $(j-1)$번째 수들은 절대 $S$에 남을 수 없다. 이후 구현은 백준 #10760과 매우 유사하게 진행했다. 구간합을 계속해서 구해야 하므로 누적합을 구해놓았다. 이후 $a_i$가 감소하는 순서로 정렬을 해놓고 $set$에 인덱스값들을 넣으면서 좌우로 인접한 인덱스에 대해 $a_i>a_{i+1}+. . .+a_{j-1}$과 $a_j>a_{i+1}+. . .+a_{j-1}$가 만족하는지 보고 만족한다면 $[i+1, j-1]$을 $set$에 넣어 겹치는 구간이 없도록 관리해 주었다. 마지막에 $set$에 있는 범위들을 순회하면서 $n$에서 해당 범위의 숫자 개수를 빼주어 답을 구했다.
 
E2
E2에서는 끝 인덱스가 계속 바뀌기 때문에 E1 풀이를 조금 바꿀 필요가 있었다. 배열의 뒷부분을 잘랐을 때 어떤 변화가 일어날지를 먼저 관찰해 보았다. 원래는 가능했던 수가 뒤쪽 구간이 잘려 불가능해지는 경우가 생기고 원래는 불가능했던 수가 뒷쪽 구간이 잘려 가능해지는 경우가 생긴다. 불가능해지는 경우는 원래 $a_i\leq a_{i+1}+\;\cdots\;+a_n$이었지만 $a_i> a_{i+1}+ \;\cdots\; +a_x$가 되는 경우이다. 이 경우에는 모든 $i$에 대해 $a_i\leq a_{i+1}+ \;\cdots\; +a_x$를 만족하는 $x$의 최솟값을 이분탐색으로 구하고 누적 최댓값을 구하면 해결된다. $i$번째가 원래 가능했다면 $cnt$에 1을 더하고 $mx[i]$를 $pq1$에 넣어둔다. $pq1$는 $pq1.top()$이 $i$보다 커질 때까지 $pop$해주고 $cnt-sz(pq1)$를 계산해 주면 된다. 그러나 원래 불가능했던 수가 가능해지는 경우를 세는 것이 쉽지 않았다. E1에서 불가능한 구간을 구하는 과정에서 불가능한 구간이 $[1, x-1]$라는 것은 해당 구간은 길이가 $x$가 되기 전까지는 가능하다는 이야기이다. 그러므로 구간의 시작이 1인 경우에 대해서 레이지 세그먼트 트리를 활용하여 각 인덱스별 $x$의 최솟값을 저장해 두었다. $x$에 도달하게 될 경우 1을 빼주어야 하기 때문에 $pq2$에 각 인덱스별로 $x$의 값을 넣고 $pq1$에 $min(mx[i],x)$의 값을 넣어 $pq2$ 또한 $pq2.top()$이 $i$보다 커질 때까지 $pop$해주어 $cnt-sz(pq1)+sz(pq2)$로 답을 구했다.