[CF] Codeforces Round 913 (Div. 3)

https://codeforces.com/contest/1907

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

 

이전에 하도 컨디션 생각 안 하고 무지성 코포를 했어서 그런지 점수가 잘 오른다.

오늘은 좀 잘 치고 싶어서 20시~22시 동안 자고 학회 영어 스터디 잠깐 참여하고 코포 쳤더니, 머리가 잘 돌아간 것 같다.

잘하면 퍼플 퍼포도 띄우고 블루도 복귀할 수 있을 것만 같았는데, 좀 아쉬워서 글을 쓰게 되었다.

 

A. Rook (00:06)

체스에서 룩이 갈 수 있는 위치를 모두 출력해 주면 된다.

현재 위치는 배재해줘야 하는 걸 까먹고 test 1에서 한 번 틀렸다. 정말 다행이다.

 

B. YetnotherrokenKeoard (00:11)

문자를 쓰고 지우는 상황이므로 스택이 쓰고 싶다.

문자를 쓸 때는 마음대로지만 지울 때는 대문자와 소문자를 구분해줘야 하므로, 각각을 관리하는 스택을 이용해 구현하면 된다.

 

C. Removal of Unattractive Pairs (01:39)

이번 셋에서 가장 헤맸던 문제이다. 결론부터 말하자면, BOJ에 똑같은 문제가 있다.

게다가 D, E를 풀고 나서 고민하다가 풀어서, 여기서 시간을 너무 많이 쓴 게 아쉽다. 여기서 30분가량 아꼈으면, F를 풀었을 거라 생각한다. 

 

어떤 문자열이 주어지고, 인접한 두 문자가 다르면 그 둘을 제거할 수 있다. 이를 반복해서 문자열의 길이를 최소로 만드는 문제이다.

 

처음엔 관찰을 안하고 대충 Proof by AC만 노리고 풀이를 냈더니 계속 예시가 틀렸었다. 매우 안 좋은 습관이다... 이때 그냥 다른 문제를 빠르게 읽으러 가자.

 

머리 한켠에 이 문제를 넣어두고 D, E를 풀고 왔더니, 갑자기 떠오른 사실이 있다.

 

결국 최종적으로 남은 문자열은 오직 한 종류의 문자로만 이루어져 있다.

만약 2개 이상의 문자로 이루어져 있다면, 반드시 제거가 가능하기 때문이다.

 

여기서부터는 비드맨과 똑같이 풀 수 있다.

인접한 두 문자끼리만 제거할 수 있다고 되어있지만, 순서를 잘 정해주면 멀리 떨어져 있는 문자들도 서로 지울 수 있기 때문이다.

 

사실 이 문제가 비드맨과 같다는 사실을 대회 칠 때는 몰랐는데, 끝나고 생각해 보니까 그냥 비드맨이였다 ㅋㅋ

처음에 한 관찰, 뒤에서부터 생각해보자는 게 유효하게 먹힌 점도 있었다. 쨋든 이렇게 공부한 게 나오니까 재밌다.

 

D. Jumping Through Segments (00:42)

최적화 문제이고, 결정 문제로 바꾸면 쉬워질 거 같이 생겼다. 움직일 수 있는 최대 거리 $k$에 대해 이분 탐색을 하면 결정 문제로 바뀐다. 

각각의 이동 시 현재 자신의 가능한 위치의 범위를 관리하면 된다.

$i-1$번째 현재 자신의 가능한 위치의 범위를 $[l, r]$이라고 하면, $i$번째 현재 자신의 가능한 위치의 범위는 $[max(l-k, l_i), min(r+k, r_i)]$이다.

이때 범위가 없어지는 경우, 즉 $r < l$인 경우가 발생하면 조건을 충족하지 못하는 것이다.

위 방식으로 이분 탐색을 진행하면, 조건을 충족하는 최소 $k$를 찾을 수 있다.

 

E. Good Triples (01:23)

$d(x) =$ the sum of digits of number $x$라는 연산이 정의되어 있다.

$n$이 주어졌을 때, $a + b + c = n$과 $d(a) + d(b) + d(c) = d(n)$를 동시에 만족하는 $(a, b, c)$의 개수를 구하는 문제이다.

 

약간 고민하다가 직관적으로, 각각의 digit끼리는 독립적이라는 생각이 들었다. 이건 내가 생각해도 너무 논리의 도약이 많아서 에디토리얼을 꼭 봐야겠다. 어쨌든 위 관찰이 사실이라면, DP식을 세울 수 있다.

 

$dp[i]$를 $n=i$일때 위 조건을 만족하는 $(a, b, c)$의 개수라 하자.

모든 $i$에 대해서 $dp[i] = dp [i/10] + dp[i%10]$이 만족하고, $0 \leq i \leq 9$에 대해서는 나이브하게 초깃값을 구해놓으면 된다.

 

앞선 방식으로 전처리 한 이후에 각 테스트케이스마다 저장한 값을 출력하면 된다.

 

F. Shift and Reverse (Upsolved)

이 문제를 고민하기 시작한 게 대회 종료 36분 전인데, 이때 처음 접근한 풀이가 올바른 풀이였다. 그리고 대회 종료 이후 24분 써서 Accepted를 받았으니, 이 문제를 푸는 데 정확히 1시간이 걸렸다. 흠.. 내 머리의 처리 속도와 구현 속도가 더 빨랐다면 풀었겠지만, 이게 내 실력이니 더 공부하자.

 

Shift, Reverse 연산을 S, R라고 쓰겠다.

S로는 어떤 두 원소 간의 순서가 바뀌진 않는다.

R은 전체를 뒤집으므로, 모든 두 원소 쌍 간의 순서가 바뀐다.

이를 관찰하면, 어느 한 인덱스에서 시작해서 모든 원소가 정렬된 상태여야지만 특정 횟수만큼 S, R을 통해 non-decreasing sorted array를 만들 수 있다는 사실을 알 수 있다.

 

이때, R은 처음 또는 마지막에 사용 여부를 결정하기만 하면 된다. 그 이상으로 사용하는 것은 낭비임을 쉽게 관찰할 수 있다.

• S 여러 번
• R 1번, S 여러 번
• S 여러 번, R 1번
• R 1번, S 여러 번, R 1번

이렇게 4가지 경우를 모두 해서 제일 작은 연산으로 가능한 횟수를 출력하면 된다.

만약 모두 불가능하면 -1을 출력하면 된다.

 

 

에디토리얼 올라오면 C, E, F는 꼭 읽어봐야겠다. 학교 가는 지하철에서 읽으면 딱 조을듯