Codeforces Round #785 (Div. 2)

오렌지 복귀

A. Subtle Substring Subtraction (00:04, +)

평소 A치고 어려웠다. 문자열의 길이가 짝수면 자명하게 선공이 다 지울 수 있고, 홀수라면 첫 글자를 남기거나 마지막 글자를 남기는 것이 최적이다.

 

B. A Perfectly Balanced String? (00:14, +)

B답게 쉬울 것 같아서 적당히 찍었더니 맞았다. 내가 한 가정은 '두 같은 알파벳 사이에 다른 모든 알파벳이 최소 하나씩은 있어야 한다' 이다.

 

C. Palindrome Basis (00:18, +1)

팰린드롬의 수가 적당히 작기 때문에 \(O(NM)\)에 냅색을 써주면 풀 수 있다.

 

D. Lost Arithmetic Progression (01:18, +1)

우선 예외 케이스를 잘 분석해서 0, -1에 대한 케이스 분류를 해준 후, 수열 A의 공차가 될 수 있는 수들을 모두 구해 알맞은 경우의 수만큼 더해주면 된다.

 

F. Anti-Theft Road Planning (01:55, +)

D를 푼 후, F가 꽤 많이 풀렸길래 보러 갔다. 우선, 1차원일 때는 https://www.acmicpc.net/problem/24043과 비슷한 아이디어를 사용해 1, 2, 1, 4, 1, 2, 1, 8 .. 꼴으로 채워주면 됨을 알 수 있다. 가로줄을 이렇게 채웠으면 16까지의 숫자를 사용했으므로 세로줄은 32, 64, 32, 128.. 꼴로 채워주면 될 것 같으나, 이러면 가중치의 합이 90000을 넘는다. 이를 어떻게 잘 줄일지 생각해 보면 가로줄은  1, 4, 1, 16, 1, 4, 1.. 꼴, 세로줄은 2, 8, 2, 32, 2, 8, 2... 꼴로 채워주는 것이 최적임을 알 수 있으며, 이러면 가중치 합이 47584정도가 된다.