Codeforces Round #713 (Div. 3)

딥3라 언레. 너무 급하게 풀어서 그런지 B번에서 뇌절을 심하게 했다.

 

A. Spy Detected!

map을 사용해 등장한 숫자의 개수를 세고, 1개인 원소의 위치를 출력함.

B. Almost Rectangle

두 점의 위치를 각각 (x1, y1), (x2, y2)라고 하면, 조건을 만족하는 위치들은 (x1, y1), (x1, y2), (x2, y1), (x2, y2) 이다.
그런데 만약 x1과 x2가 같거나 y1과 y2가 같으면 직사각형 모양이 나오지 않기 때문에 x'을 임의로 x1+1 또는 x1-1로 정할 수 있다. 둘 중에 가능한 것 하나를 골라서 새로운 위치로 지정한다. 마찬가지로 y에 대해서도 y'을 잘 정한다.
쉬운 문제였지만 x' 또는 y'이 가능한지 확인을 제대로 하지 못해서 두 번이나 틀렸다. 너무 긴장해서 급하게 제출했던 것 같다.

C. A-B Palindrome

constructive하게 해결이 가능하다. 수열에서 0의 갯수와 1의 갯수가 주어지므로(각각 a와 b), 입력된 수열에서 이미 정해진 숫자만큼 미리 센다. 만약에 a나 b가 음수가 되면 더 볼 것도 없이 불가능한 상태이다.
수열을 한 번 순회하면서 S[i] == S[N-1-i]를 만족하도록 ?를 가능한대로 채워 넣는다. 동시에 a와 b를 소모하면서 음수가 되지 않는지 확인한다. 이렇게 하여 먼저 자명한 숫자들에 대해서 팰린드롬을 만족하게 할 수 있다.
남는 ?들에는 숫자를 가능한대로 채워 넣는다. 다 채웠을 때 a나 b가 음수가 되면 불가능한 상태임을 알 수 있다.

D. Corrupted Array

먼저 미리 주어진 수열의 합을 구해둔다. 그 후 주어진 수열 b를 순회하면서 b에서 제외할 숫자 x를 정한다. 수열의 총 합에서 x를 뺀 값은, a의 각 원소들과 a의 모든 원소의 합이다. 다시 말해서 (a의 합)*2이라는 뜻이다. 이를 2로 나눈 뒤 (나눠지지 않으면 예외처리한다.) 그 값이 b에 존재하는지 set등을 사용해 확인한다.

E. Permutation by Sum

구간 [L, R]에 대해서 가장 작은 경우는 [1, 2, ... , L-R+1]이고 가장 큰 경우는 [N, N-1, ... , N-(L-R+1)]이다. S가 가장 작은 경우랑 큰 경우 바깥이면 불가능하다. 반대로 가장 작은 경우랑 큰 경우 안쪽에선 S를 만족하는 수열이 항상 존재한다.
만약 가장 작은 경우에 모든 원소에 1씩 더해준다고 하면, 구간합이 L-R+1씩 증가한다. 그런데 구간의 길이가 L-R+1이므로 한 원소씩 더해주면 사이에 모든 공간이 채워진다.
큰 원소부터 하나씩 더해나가면 구간 [L, R]의 합이 S면서 항상 서로 겹치지 않는 수들의 집합으로 만들 수 있다. [L, R]을 잘 구성하고 남은 위치들에 아직 사용되지 않은 수를 적절히 채워 넣으면 된다.

 

F. Education (업솔빙)

각 위치에서 가진 돈을 일차함수로 그려보면 CHT 처럼 나타난다. O(n)으로 시뮬레이션하면서, 현재 일차식과 다른 일차식을 비교해서 목표하는 돈을 먼저 모으는 쪽으로 계속 업데이트해 나가면 된다.