[2020-09-08] Codeforces Round 543 (Div.1)

unrated된 대회라 등수가 애매하다. 실제 대회였다면 A도 C도 훨씬 많이, 빨리 풀렸을 듯. 이번에도 코딩 미스가 너무 많았다. 풀이도 충분히 빨리 떠올릴 수 있는 문제들을 제대로 못 떠올리고, 모호한 상태에서 구현에 들어가면서 더 많은 실수를 한 것 같다.

A. Diana and Liana

간단한 투 포인터로 해결할 수 있는 문제다. 어떤 l 위치에서 l...r이 문제에서 주어진 schematic 조건을 만족하기 위해 제거해야하는 원소 개수를 구하고, 그 중 최소가 되는 것을 출력하면 된다. 간단한 off-by-one 에러, 수식에서의 예외 케이스 처리 등을 제대로 못해서 두 번이나 틀리고 맞았고, 26분이나 걸렸다. 10분 내외로 풀었어야할 문제 같은데 너무 구현 정확도가 떨어졌다는 기분이 든다.

C. Compress String

문제를 이상하게 이해해서 망했다. 문제에서 제대로 적혀 있었는데도 왜.. 온갖 실수는 다 하는 것 같다. 처음 빠르게 제출하고 틀린 후 내가 문제를 잘못 이해했다는 걸 깨달았고, 이 부분에서 풀이를 조금만 수정하면 그대로 통과할 수 있는 거였는데 괜히 이상하게 해싱을 쓰는 걸로 코드를 바꿨다가 여러번 틀렸다. 그 다음에 다시 풀이를 복구하는 과정에서 코딩 실수를 엄청나게 한 뒤에야 겨우겨우 AC. 그냥 처음에 z-algorithm을 한 번만 썼던걸 N번 써서 O(N^2) 전처리하면 풀리는 거였는데 도대체 왜 이렇게 삽질을 한 건지.. 뭔가 요즘 대회 중간에 망했다는 생각이 들면 멘탈이 쉽게 부서지는데, 이게 떨어진 구현 정확도랑 시너지를 내면서 퍼포먼스가 바닥을 뚫고 내려가는 듯. 다음 대회때는 좀 더 침착하게, 천천히 한다는 기분으로 풀어야겠다.

B. Once in a casino

 이게 왜 B? 죽었다 깨어나도 못 풀었을 것 같다. 원본 문자열을 s라고 했을 때, b[i] = i가 짝수면 s[i], 홀수면 9 - s[i]라고 하자. 주어진 연산은 b[i]의 합을 변화시키지 못한다(이걸 어떻게 생각할 수 있는지 모르겠다.. 이게 증명의 제일 중요한 포인트. 이런 식으로 수열을 변화시키는 게 가능하다는 거 기억해둬야겠다). 따라서, 주어진 두 문자열에 대해 이렇게 변환한 후의 합이 서로 다른 경우 -1을 반환한다.

 

그게 아닌 경우 항상 a를 b로 바꿀 수 있다. 어떤 i번 자리에서 a[i]와 b[i]가 다르다고 하자. 0 이하 / 9 이상으로 못 바꾼다는 조건을 빼고 연산을 하면 항상 b로 바꾸는게 가능한데(당연히), 이렇게 연산의 순서를 구한 후 그 연산들의  순서를 적절히 바꿔 0 이하 / 9 이상 조건을 만족시킬 수 있는지 생각해보자.

 

어떤 i번째 위치에서 +1 연산을 할 수 없게 되었다면 a[i] == 9 거나 a[i+1] == 9라는 이야기인데, a[i] == 9일 수는 없다(a[i] < b[i] 일 때만 i 번째 위치에서 +1을 할 것이므로) 따라서, a[i+1] == 9 라는 이야기이고 그러면 i+1번째 위치에서 -1을 하는 연산을 미리 하나 끌어와서 하면 된다. 이 과정을 반복해서 연산을 끌어오면 얼마든지 순서를 바꿀 수 있다.