Educational Codeforces Round 90 (Rated for Div. 2)

A. Donut Shops (00:05, +)

한 가게는 도넛 하나를 \(a\)원에 판매하고, 다른 가게는 도넛 \(b\)개를 \(c\)원에 판다.

이 때 첫 가게가 유리한 시점은 무조건 도넛을 1개 구매하는 시점이다. 이때 첫 가게가 더 싸지 않다면 언제나 두 번째 가게를 이용하는 것이 효율적이다. 다른 경우도 마찬가지로, 도넛을 b개 구매하는 시점이 두 번째 가게가 가장 효율적인 순간이다.

 

B. 01 Game (00:09, +)

연산 한번당 0과 1이 각각 하나씩 사라지므로 min(0의 개수, 1의 개수)의 홀짝성을 따지면 답을 구할 수 있다.대회 중에는 머리가 빠르게 돌아가지 않아 stack을 통해 구현했다.

 

C. Pluses and Minuses (00:20, +)

주어진 수도 코드를 해석해야 한다. 관찰을 통해, 누적합이 음수 \(k\) 가 되는 최초의 순간만 더해주면 된다는 사실을 알 수 있다. 각각의 \(k\) 에 대해 누적합이 \(k\) 가 되는 순간의 길이를 모두 더해주고, 수도 코드의 종료 조건에 의해 문자열의 전체 길이를 한번 더 더해주면 문제를 해결할 수 있다.

 

D. Maximum Sum on Even Positions (00:40, +)

수열이 주어질 때, 임의의 부분수열을 한번 뒤집어서 짝수 index 원소의 합을 최대화하는 문제이다.문제가 가지는 몇 가지 성질을 관찰해보자.1. 뒤집는 구간의 길이는 항상 짝수여야 한다.2. 구간에 대한 연산을 뒤집는 것이 아닌 인접한 원소끼리 교환해주는 것으로 해석할 수 있다.길이가 5인 수열을 \( A_0...A_4 \) 라 하자.이 때 구간 \( [0..3] \)에 대해 연산을 적용하면 목표값에 더해지는 값은 \( {{A_{1}}-{A_{0}}}\), \( {{A_3}-{A_{2}}}\) 이다.이러한 관찰을 통해, 연산으로 인해 변화하는 짝수 원소들의 합은 \( {A_{2k+1}} - {A_{2k}} \) 또는 \( {A_{2k-1}} - {A_{2k}} \) 꼴의 부분합임을 알 수 있고, 이는 최대 부분합 문제를 해결하는 것과 동치임으로  \( O(N) \) 에 문제를 해결할 수 있다.