Educational Codeforces Round 101 (Rated for Div. 2)

 

A. Regular Bracket Sequence

( , ) , ?가 포함된 괄호문자열을 주고 ?에 적절한 괄호를 넣어서 온전한 괄호문자열을 만들 수 있는지 출력하는 문제.

문제의 조건에서 There is exactly one character ( and exactly one character ) in this sequence. 라는 문장을 제대로 이해하지 못해서 헤맸다. 해석하면 주어진 문자열에 (가 한 개, )가 한 개, 나머지는 ?이다. 라는 뜻인데 이 조건 없이 그냥 풀다가 구현 말리고 결국 뇌절해서 DP로 풀었음.

정해로는 1. 길이가 짝수고, 2. )로 시작하지 않으면서 3. (로 끝나지 않는다. 3가지 조건을 만족하면 무조건 가능하다. 중간은 적당히 아무거나 채워 넣으면 되기 때문.

 

B. Red and Blue

빨간색으로 칠한 수열과 파란색으로 칠한 수열이 주어질 때, 두 수열의 순서를 바꾸지 않으면서 잘 배치해서 합친다. 합친 수열 a에서 f(a)=max(0,a1,(a1+a2),(a1+a2+a3),…,(a1+a2+a3+⋯+an+m)) 에 대하여 f(a)의 최대값을 구하는 문제.

이 문제도 뇌절와서 DP로 풀다가 틀리고 다시 풀었다. 순서를 바꾸지 않으므로, (빨간 수열에서 누적합의 최대) + (파란 수열에서 누적합의 최대) 가 답이다. 각 수열에서 누적합이 최대가 되는 지점까지만 잘 배치한다면 그 지점이 a의 최대값이 되기 때문. 예를 들어 -1 4 5 2 -9 3 3 9 0 -2 -5 이렇게 있다면 (-1 4 5 2 3 9 0) -9 3 -2 -5 이런 식으로 최대 지점을 앞에다 몰아놓으면 된다.

 

C. Building a Fence

조건을 만족하면서 fence를 세울 수 있는지 알아내는 문제. fence는 이웃한 fence와 1칸 이상 겹쳐야 하고, 바닥에서 k-1칸 이상 떨어지면 안된다. 양 끝의 fence는 바닥에 붙어있어야 한다.

왼쪽 끝 fence를 고정시키고, 오른쪽으로 fence를 구성해나간다. 현재 위치에 대하여 조건을 만족하는 최대 fence 위치와 최소 fence 위치를 관리해주면 된다. 오른쪽 끝 fence가 이 영역 내에 있는지 확인하면 ok.

 

D. Ceil Divisions (업솔빙)

1부터 n까지 수열에서 ax = ceil(ax / ay) 연산을 할 수 있다.(x != y) 잘 치환해서 수열에서 2가 하나, 나머지가 전부 1이 되게 바꾸는 문제. 단, 치환 횟수는 N+5번 이하여야 한다.

2^(2^k) 가 키워드다. 2^(2^(i+1)) 는 2^(2^i)로 나누면 2^(2^i)가 나오므로 2번 만에 1로 만들 수 있다. (ex. 64, 256 -> 256/64=64, 64/64=1) 2부터 n미만의 모든 2^(2^k), n을 따로 관리한다. (2, 4, 16, 256, ... , n) 이들을 제외한 나머지 수는 전부 인접한 수와 나눠서 1로 만들어버리고, 남은 2^(2^k)들을 이웃한 원소끼리 나눠서 2번만에 1로 만들어버리면 된다.