Codeforces Round #603 (Div 2) 풀이

이번 코포는 진짜 포텐이 제대로 터졌다. 한 번도 풀어보기는커녕 건드려본 적도 없는 E번을 풀어냈다!!!! 그 결과 135점 떡상. 이제는 퍼플이 민트보다 가깝다!!! 그럼 풀이 시작해보겠다.

 

A. Sweet Problem

https://codeforces.com/contest/1263/problem/A

Problem - A - Codeforces

일단 가능한 횟수가 (r+g+b)/2 이하인 것은 자명하다. 또한 어떤 두 색의 합보다도 가능한 횟수가 작거나 같을 것이다. 그러므로 답은 min((r+g+b)/2,r+g,g+b,b+r)이다.

 

B. PIN Codes

https://codeforces.com/contest/1263/problem/B

Problem - B - Codeforces

 

엄청나게 역겨운 구현 문제다. 먼저 n이 10 이하로 무척 작다는 것에 주목하자. 끝 자리수만 적당히 갈아주면 같은 수를 쉽게 모두 다른 수로 만들 수 있다. 그럼 변경 횟수를 구하는 건 쉽다. 여러 개의 같은 핀 코드가 있으면 그 중 하나를 빼고 모두 바꾸면 되므로 (n-(서로 다른 핀 코드의 개수))라고 정의할 수 있다. 바꾸는 건 이미 등장한 일의 자리를 카운트해주고 등장하지 않은 일의 자리로 바꿔주는 트릭을 쓰면 되는데 구현이 제법 귀찮다. 그 구현을 위해 쓴 크기 10짜리 배열이 대체 몇 개인지 모르겠다. 코드는 이렇게 된다.

C. Everyone is a Winner!

https://codeforces.com/contest/1263/problem/C

Problem - C - Codeforces

 

그냥 n을 자연수로 나눠서 나올 수 있는 몫을 모두 구하라는 문제다. n의 범위가 10억이므로 일일히 구했다가는 TLE를 맞는다. 그러니까 적당히 점프를 뛰어서 시간을 절약하는 방법을 이용하자. 일단 0은 항상 가능한 몫임이 자명하다. 그러니까 결과를 저장한 배열에 먼저 0을 넣어놓고 시작한다. n을 나누는 수를 val이라 하자. 먼저 val=n부터 시작한다. 그리고 몫을 구한 다음 val을 min(n/(이전에 구해진 가능한 몫의 값)+1,val-1)로 바꾼다. 그러면 시간복잡도가 O(sqrt(n))으로 변해서 시간 안에 해결할 수 있다.

코드는 이렇게 된다.

D.Secret Passwords

https://codeforces.com/contest/1263/problem/D

Problem - D - Codeforces

겹치는 단어가 있으면 두 패스워드는 equal하다. 그리고 서로 equal하지는 않지만 각자 equal한 문자열로 연결이 된다면 그 두 문자열 또한 equal하다. 그러므로 우리가 풀어야 할 문제는 이렇게 바꾸어 정의할 수 있다. "겹치는 문자가 있으면 두 문자열을 union한다. 그런 후 컴포넌트의 개수를 구한다." 그러면 어떻게 하면 20만개의 문자열에서 겹치는 문자의존재를 빠르게 확인할 수 있을까? 만약 무식하게 20만개를 비교한다면 O(N^2)의 시간이 걸린다. 하지만 우리는 등장하는 단어가 a~z까지의 26개뿐임에 주목할 필요가 있다. a부터 z까지 for문을 돌면서 그 내부에서 문자열을 모두 탐색하며 그 문자가 등장하면 그 문자열을 그 문자가 등장한 다른 문자열과 union한다. 그러면 우리는 26*(문자열 길이 합)의 시간에 이 과정을 완료할 수 있다. 문자열 길이 합은 최대 100만이라 나와있으므로 2600만이고 이 정도면 충분히 시간내다. 그 다음으로는 문자열을 모두 돌면서 그들의 부모가 총 몇 개가 있는지 확인하면 된다.

코드는 이렇게 된다.

E. Editor

https://codeforces.com/contest/1263/problem/E

Problem - E - Codeforces

내가 풀고 나서 신나서 노래 부르며 춤췄던 그 문제다. 이 문제의 풀이법은 세그먼트 트리 레이지 프로퍼게이션이다. 각각의 세그먼트 트리의 리프 노드의 값을 이렇게 정의한다. "여는 괄호를 1, 닫는 괄호를 -1이라 했을 때 그 index까지의 값들의 합". 그리고 최솟값 세그 트리와 최댓값 세그 트리 두 개를 구축한다. 그리고 입력을 받으면서 그 문자가 'L'이라면 현재 위치를 가리키는 point에서 1을 빼주고, 'R'이라면 1을 더해준다. 또 '('이라면 그 index부터 끝까지 1을 update해준다. ')'이라면 -1을 update해준다. 그런데 여기서, 사실 우리가 문자를 적은 위치에 다른 문자가 있었을지도 모른다. 만약 여기에 '('가 있었다면 반대로 -1을 update하며 되돌려주고, ')'였다면 1을 update한다. 그리고 이제 처리를 해야 되는데 0부터 끝까지의 최솟값이 0보다 작다면 '('없이 등장한 ')'가 한 개 이상 있다는 의미이므로 -1을 출력한다. 또 '('와 ')'의 개수를 세는 변수 하나를 만들어두어서 이 문자열의 괄호가 제대로 닫혔는지 판단한다. 이까지 통과한다면 이 문자열은 올바른 괄호 문자열이란 뜻이다. 그러면 이제 최대로 겹친 괄호의 개수를 구하면 되는데, 0부터 끝까지의 최댓값을 구하면 되는 것이다.

코드는 이렇게 된다.

이번 contest의 결과 135점의 떡상을 이뤄낼 수 있었고 1769점이 되었다. 퍼플의 고지가 눈앞에 보인다!!!