Codeforces Round #905 (Div.3) -> Virtual Contest

https://codeforces.com/contest/1883

Dashboard - Codeforces Round 905 (Div. 3) - Codeforces

 

8월 말에 저는 블루를 찍었고, 그 후에 저는 코드포스를 한 번도 쳐본적이 없었습니다. 티어가 떨어질 수 있다는 불안감도 없진 않았지만 현재 백준 다이아를 찍어보고 싶어서(그래야 연말에 다이아 키링을 받지 않겠어요? ㅎㅎ) 백준에 좀 더 집중하고 있었습니다.

 

그러다가 최근에 이례적으로 Div.1 ~ Div.3를 동시에 열었다는 소식을 들었습니다. 제가 코드포스를 시작한 후에 처음으로 Div.1 부터 Div.3 까지 열린건데, 그래서 그런지 이번에 Div.2 참가 제한이 블루부터 퍼플까지 였습니다. 딱봐도 레이팅이 떨어질 것도 분명하고 제가 코드포스를 최근에 안 친지 꽤 되었기에 참가하지 않았습니다만 오늘 갑자기 시간도 되고 흥미가 생겨 오랜만에 Div.3을 기준으로 Virtual을 돌려보았습니다. 결과는 아래와 같았습니다.

 

총 8 문제 중에서 6 문제를 맞췄네요.

 

 

E번을 못 푼게 아쉽지만 그래도 꽤 많이 맞춰서 아직 감이 다 죽은 건 아니란걸 확인할 수 있었습니다. 언젠가 직접 칠 수 있으면 좋겠네요.

 

아래는 제가 풀었던 문제에 대한 간략한 리뷰들을 남기고 글을 마치려고 합니다.

 

A . Morning (00:03)

Div.3의 제일 첫 문제답게 쉬운 구현 문제였습니다. (굳이 따지자면 그리디도 포함할 수 있으려나 싶네요.)

 

주어진 문자열에 맞추어 움직이는 걸 전부 계산하거나 수학으로 빨리 계산해도 됩니다.

 

B. Chemistry (00:11)

Ad-hoc 문제였습니다.

 

문자열은 마음대로 배치가 가능하므로, 그냥 각 알파벳이 몇개가 있는 가를 신경써야 합니다.

알파벳 두 개 이상이 홀수개면 불가능하므로 m개를 제거해서 최대 하나만 홀수개가 되도록 맞출 수 있는지를 파악하면 됩니다.

 

이 문제가 Div.2에서의 A번 문제였는데, 난이도도 딱 그정도 일 것 같습니다.

 

C. Raspberries (00:24)

이 문제는 Case-Working이 제일 큰 문제였습니다.

 

k가 2,3,5 일때는 k가 소수이므로 주어진 수열 내에서 적어도 하나는 k의 배수여야 합니다.

a_i가 k로 나뉠 수 있도록 몇 번의 operation을 거쳐야 하는가는 k - (a_i % k) 를 계산하고 결과 값이 k일 때는 0번, 아니면 해당 수 만큼의 operation을 해야합니다. 이를 a_1부터 a_n까지 전부 계산하여 최솟값을 찾으면 됩니다.

 

다만, k가 4라면 이야기가 좀 달라집니다. 수열의 모든 수가 4의 배수가 아니더라도, 2의 배수인 수가 한 번 나오면 최대 한 번의 operation을 거치면 되고, 2의 배수가 두 번 이상 나온다면 operation을 할 필요가 없습니다. 이를 위해서 2,3,5처럼 계산을 하되, 2의 배수인 것들의 개수도 세어줘서 처리해야 합니다. 

 

이 문제는 Div.2에서 B번이었는데, 아이디어는 비교적 쉬운 편이었다고 생각이 듭니다. 다만 저는, Case-working에서 구현 실수를 좀 많이 해 시간이 좀 지체되었습니다.

 

D. In Love (00:31)

이 문제는 그리디 + 자료구조 문제였습니다.

 

모든 segment가 서로 겹치는 경우는 제일 처음으로 나오는 segment의 끝 부분이 모든 segment들의 시작 부분 보다 더 뒤에 있어야 가능합니다. 따라서, multiset을 활용해 시작 및 끝 부분을 관리하여 segment들 중 시작 부분의 좌표값이 제일 큰 것과 segment들 중 끝 부분의 좌표값이 제일 작은 것을 비교하여 각 쿼리마다 O(logN)만에 답을 낼 수 있습니다.

 

이후에 한참을 E번을 보았는데, 큰 수들을 어떻게 관리를 해야할지가 감이 안와서 F, G1번을 훑어보았습니다. 그 중에서 G1번이 제일 쉬워보여 먼저 건드렸습니다.

 

G1. Dances (Easy version) (01:11)

이 문제는 그리디 + 자료구조 문제였습니다.

 

m=1 이라서 a_1 = 1인 것을 제외하고는 그냥 a,b가 주어졌을 때 최소 몇 번의 operation을 하면 되는지를 물어보는 문제였습니다. 그 와중에 일단 a,b는 언제든지 재배열이 가능하므로 순서는 별로 신경을 안 써줘도 될 것 같았습니다. 저는 그래서 일단 a와 b를 정렬한 후에 만약에 현재 a와 b 내에 있는 제일 큰 값이 b에 있는 값이 더 크다면 둘은 일단 a,b에 남겨도 되므로 최종 a와 b에 있는 원소로 남겨둔 후 a,b에서 삭제, 아니라면 a의 제일 큰 값을 b에 있는 제일 작은 값과 같이 삭제하도록 operation을 실행하였습니다.

 

문제 설명이 많이 난해하게 느껴져서 푸는데 시간이 좀 걸렸던 것 같습니다. 이게 Div.2에서는 D1이었는데, D번보다는 더 쉬운 문제였던 것 같습니다. 심지어 아래 후술할 F번이 Div.2의 C번이었는데 이게 더 어려웠던 것 같네요.

 

 

F. You Are So Beautiful (01:47)

이 문제는 애드혹 + 자료구조 + 이분탐색 문제였습니다. 

 

subarray의 시작값과 끝값을 편의상 l, r이라고 합시다. 그러면, subsequence가 단 하나밖에 존재하지 않은 subarray는 l 과 r과의 같은 값들 중에서 각각 제일 첫 번째로 나온 값, 마지막으로 나온 값이어야 합니다. 이유는 간단합니다. 만약에 l이 제일 첫 번째 값이 아니라면 subsequence를 좀 더 앞에 있는 l값을 활용해서 더 만들 수가 있습니다. 반대로 r이 마지막으로 나온 값이 아니면 좀 더 뒤에 있는 r값을 활용해서 만들 수가 있습니다.

 

따라서 저는 map을 활용해서 각 값에 대해서 제일 마지막으로 나온 위치를 저장하고, 제일 첫 번째로 나오는 위치들을 전부 저장하여 관리했습니다. 각 값의 마지막 위치를 r로 두었을 때 가능한 l들의 개수는 이분탐색을 활용하여 찾아냈습니다.

 

앞서 말한것과 같이 G1에 비하면 쉬웠던 문제 같습니다. 

 

E. Look Back (Unsolved)

아마도 그리디 문제 같습니다.

 

일단 문제를 보았을 때 그리디하게 앞의 숫자부터 결정지어주면 되겠다는 생각이 들었습니다.

그래서 그렇게 구현을 해보는데, 예제도 정답이 나와서 이대로 풀려고 했습니다만 숫자가 매우 커지는 상황이 발생하여 이를 어떻게 해결해야할지 고민하였습니다. 그래서 파이썬으로도 구현을 했는데 잘 안 되어 결국 못 풀었습니다.

 

에디토리얼을 잠깐보니 어차피 각 수를 몇 번째 비트가 켜졌는지로 표현이 가능하고 *2는 어차피 각 비트의 위치가 +1하는 것이므로 따로 이를 관리해서 값들을 비교하는 것 같습니다. 이걸 못 떠올린게 아쉬웠습니다.