Codeforces Round 1123 (Div. 2) 후기

오랜만에 심심해서 Codeforces Div. 2에 참가해봤습니다.

A - Turn Into a Palindrome - 0:02 AC

문자열에서 임의의 문자를 c로 바꾸는 연산을 이용해 팰린드롬으로 만드는 최소 비용을 구하는 문제였습니다.

간단한 브론즈 문제라 슥삭했습니다.

B - Fashionable Array - 0:05 AC

누적해서 가장 많이 등장한 수를 출력하되, 등장 횟수가 같다면 더 큰 수를 골라 결과를 사전순으로 가장 크게 만드는 문제였습니다.

쉬운 구성적 아이디어였고, 정렬한 뒤 한 겹씩 큰 수부터 출력하면 됐습니다.

체감상 실버였습니다.

C - GCD Treasury - 0:21 WA

수열에서 $\gcd(x, a_i) \ne 1$인 원소를 삭제하고, $x=\gcd(x,a_i)$로 갱신하면서 삭제한 원소의 합을 최대화하는 문제였습니다.

$x$의 소인수만 뽑은 뒤, 그 소인수의 배수인 원소들을 찾으면 됐습니다.

첫 제출에서는 소인수분해 구현을 잘못 짰습니다.

C - GCD Treasury - 0:22 AC

고쳐서 바로 맞았고, 체감 난이도는 G4였습니다.

D - Backrooms Hill - 0:43 AC

어떤 원소를 기준으로 양쪽으로 갈수록 값이 엄격하게 감소하는 산을 만들 수 있는지 판별하는 문제였습니다.

$a_i$와 $a_{i+2}$를 바꾸는 연산만 가능했고, Yes/No만 판별하면 됐습니다.

짝수 인덱스와 홀수 인덱스를 각각 묶은 뒤, 큰 값부터 두 개씩 짝지었을 때 매번 서로 다른 그룹에서 하나씩 가져올 수 있는지만 확인하면 됐습니다.

체감 난이도는 G1~P5 정도였습니다.

F1 - XOR Transformations (Easy Version) - 1:30 AC

E를 고민하다가 감이 안 와서 F1으로 도망쳤습니다.

길이 $N$의 수열에서 모든 수 쌍의 XOR 값 중 작은 $N$개로 수열을 다시 만들고, 이 변환을 반복했을 때 $\max-\min$이 어떻게 되는지 묻는 문제였습니다.

한 번 변환하면 최상위 비트 하나가 항상 사라지므로, Easy에서는 브루트포스로 충분했습니다.

체감 난이도는 G3 정도였습니다.