[알고리즘] Codeforces Round #811 (Div. 3)

D 메인테스트에서 틀림 ㅠㅠ

오랜만에 코드포스 컨테스트 글을 올려보려고 한다.

rated대회는 무서워서 못치겠고 버추얼을 돌리면서 실력을 키우고 도전하려고 한다.(그리고 파란색이 너무 예뻐서 유지하고 싶다.)

 

Codeforces Round #811 (Div. 3)

 

A - Everyone Loves to Sleep [Solved!]

현재 시간이 주어지고 $n$개의 시간이 주어질 때 현재 시간 이후의 시간 중 가장 빠른 시간과의 차이를 구하는 문제이다.

 

시간을 분으로 고쳐서 정렬한 후 완전탐색 해서 구하면 된다.

다만 현재 시간이 주어진 시간보다 뒤일 수 있으므로 주어진 시간중 가장 빠른 시간에서 $24 \times 60 = 1440$을 더해 맨 뒤에 추가한 후 탐색한다.

 

B - Remove Prefix [Solved!]

앞에서부터 몇개를 제거해야 그 이후에 나오는 수들이 중복이 없는지 구하는 문제이다.

 

뒤에서부터 시작하여 중복된 원소가 나오면 멈추고 그 수가 $i$ 번째에서 나왔다면 $n-i+1$이 답이다.

중복 확인은 원소의 최대가 $200000$이므로 해당 크기의 배열을 선언해서 확인해도 되고 set을 이용해도 된다.

파이썬은 해시 주의!!

 

C - Minimum Varied Number [Solved!]

$n$이 주어지고 각 자리수의 합이 $n$이면서 모든 자릿수가 다른 자연수의 최솟값을 구하는 문제이다.

 

뒤에서부터 그리디하게 수를 채워나가도 되고 테이블을 만들어서 $O(1)$에 처리해도 된다.

나는 풀이가 바로 떠오르지 않아서 테이블 제너레이터를 만들어서 돌리고 D를 보러갔다. ㅋㅋ(제너레이터 돌리는데 6분걸림)

 

D - Color with Occurrences

문자열이 주어지고 패턴이 주어질 때 패턴으로 문자열을 덮을 수 있는지 확인하고 가능하다면 최소 횟수와 그 방법을 출력하는 문제이다.

 

제한이 그렇게 크지 않아서 완전탐색하며 그리디하게 접근했는데 프리텟은 통과하고 메인텟에서 반례가 나왔다.

 

>>> ----- 뇌피셜풀이 -----

 

지금 떠오르는 풀이는 패턴이 문자열에서 어디부터 어디까지 나타나는지 확인하고 최소로 합집합을 하여 구하면 될 것 같다.

https://www.acmicpc.net/problem/25393

25393번: 교집합 만들기

위에서 패턴 범위를 구하고 그 범위들로 25393번문제를 합집합 버전으로 해결하면 될 것 같다.

패턴은 KMP나 완탐으로 범위를 찾을 수 있고(제한이 작아서 KMP는 약간 오버킬) 발견된 범위도 크지 않기 때문에 난이도는 그렇게 높지 않을 것 같다.

 

>>> 결과

이 방법으로 맞았다. ^o^

 

E - Add Modulo 10

배열의 각 원소에 다음 연산을 수행할 수 있다.

 - $a_i = a_i + a_i \% 10$을 수행한다.

위 연산을 적당히 수행한 후 모든 원소를 같은 값으로 만들 수 있는지 판별하는 문제이다.

 

연산을 수행하다보면 1의자리 숫자는 자기 자신으로 돌아온 후 반복될 것이다.

그리고 그 주기는 10을 넘지 않는다.

모든 원소에 대해 1의자리 숫자가 돌아올 때 까지 연산을 수행하면 그 차이가 나올 것이다.

예를들어 어떤 원소가 $1$이라고 하자.

$ 1 \rightarrow 2 \rightarrow 4 \rightarrow 8 \rightarrow 16 \rightarrow 22 \rightarrow \dots $

$2, 22$의 1의자리 숫자가 같아졌고 주기는 5, 차이는 20이 된다.

같아지기 전까지의 수들을 그 차이로 나눈 나머지들을 집합에 넣는다.

위 작업을 모든 원소에 대해 진행하면 각각의 원소에 대한 집합이 $n$개 나올 것이다.

$n$개의 집합을 교집합해서 원소가 하나라도 있으면 YES이고 아니면 NO이다.

 

G - Path Prefixes

루트가 1인 트리가 주어지고 간선에 파란 가중치와 빨간 가중치가 주어진다.

루트에서 각 정점까지 파란가중치의 합은 진행 경로에 있는 빨간 가중치의 합의 상한이 되는 간선의 개수를 구하는 문제이다.

 

나는 DFS 2번을 사용해서 해결했다. (dfs라서 MLE 날까봐 cpp로 제출했다.)

한번은 각 정점에 도달하는 빨간 가중치의 합을 구했다.

두번째 DFS를 돌면서 파란 가중치들의 합을 배열로 저장하여 이분탐색을 이용하여 해당 정점의 빨간 가중치의 합의 상한을 찾는다.

이분탐색으로 나온 인덱스가 정답이다.