ARC 194 - Div 2

 

https://atcoder.jp/contests/arc194

 

 

 

Performance Rating : 1900

 

A

수열에서 연속한 2개의 항을 함께 제거할 수 있고 제거한 뒤 수열의 합을 최대로 만드는 문제인데 $dp[i]$를 $A_1$,$\cdots$,$A_i$까지의 숫자들로 만들 수 있는 합의 최댓값이라고 정의하면 $dp[i]=\mathrm{max}(dp[i-1]+A_i,dp[i-2])$라는 식을 세울 수 있다.

 

B

가장 큰 원소를 뒤로 보내는 방식으로 버블정렬을 할 때가 최선이라고 생각했다. $x$가 $x$번째로 가기 위해서는 자신보다 뒤에 있는 $x$보다 작은 수들을 앞으로 보내야 하는데 이를 최대한 앞에서 하려면 자신보다 큰 수들을 모두 제자리에 놓고 해야하기 때문이다. 이렇게 정성적으로 생각한 뒤 맞을 것 같아 제출했다. 

 

C

결국 비용을 최소화하려면 $1$을 $0$으로 만드는 것을 먼저 해주고 $0$을 $1$로 만드는 것을 나중에 해야한다는 것을 먼저 생각했다. 구체적으로는 $v$에 $A_i=0$, $B_i=1$인 $i$에 대해서는 $-C_i$를 넣어주고 $A_i=0$, $B_i=1$인 $i$에 대해서는 $C_i$를 넣어서 정렬한 뒤 순차적으로 진행하는 것이 최선이다. 그러나 $A_i=B_i=1$인 경우에 대해서 먼저 $A_i$를 0으로 만들고 나중에 1로 만드는 과정을 하는 것이 비용을 더 줄일 수도 있겠다는 생각이 들었다. 처음에는 $A_i=B_i=1$인 $i$에 대해서 $C_i$의 값들을 저장해 두고 $C_i$의 값이 작은 것부터 $i$번째 항을 0으로 만들었다가 1로 만드는 것이 전체 비용 측면에서 이득이 되는지 확인했다. 그러나 이 방법은 작은 항을 넣었는지 여부가 큰 항을 넣을 때 비용 변화량에 영향을 주기 때문에 문제가 생겼다. 그래서 우선 $v$에 $A_i=B_i=1$인 $i$에 대해서 $-C_i$와 $C_i$를 넣어두고 $C_i$의 값이 작은 것부터 빼는 것이 이득인지 확인한 뒤 이득이면 빼주고 손해면 과정을 끝내는 방식으로 풀었는데 WA를 받았다. 생각해보니 작은 것부터 빼갈 때 $C_i=C_j$이면 비용 변화량 계산에 문제가 생겼다. 그래서 빼는 것이 손해여도 반복문을 끝내지 않고 끝까지 돌리면서 최솟값을 찾는 방식으로 변경해 맞았다.