Codeforces Round #710 (Div. 3)

 

.올솔!

 

 

개인적으로 뭔가 제 자신에 대해 매우 찝찝했던.. 대회였습니다.

 

A. Strange Table [3분]

 

화이팅!! 여러분은 충분히 짤 수 있습니다!!

 

B. Partial Replacement [11분]

 

B 치곤 살짝 어려운 감이 있었는데 그렇게 어렵진 않습니다.

* 가 나오는 제일 왼쪽 지점과 제일 오른쪽 지점을 구합니다.

그 구간이 없거나 같을 때 예외 처리를 해줍니다.

다르다면 $ ( l + 1 ) $ ~ $ ( r - 1) $ 를 보면서 체크를 해줍니다.

제가 한 방법은 제일 최근 본 * 위치를 $ a_{1} $ 이라고 하고 그 바로 전 * 위치를 $ a_{2} $ 라고 합시다.

그럼 지금 위치를 $ x $ 라고 했을 때 이 $ x $ 랑 $ a_{2} $ 거리가 k  이하를 만족하면 $ a_{1} $ 이랑 $ x $ 를 바꿔주면 되고

아니면 $ answer $ 값을 증가시켜주면 됩니다.

 

C. Double-ended Strings [14분]

 

완탐!

 

D. Epic Transformation [18분]

 

제일 갯수가 많은 거 두 개를 뽑아서 빼주면 됩니다.

 

E. Restoring the Permutation [35분]

 

이 문제에서 살짝 말렸습니다.

그냥 쉬운 구현 문제라 늦어도 10분 안에 풀었어야 하는 문젠데 너무 느리게 풀었습니다..

사소한 것 때문에 계속 코드에서 런타임 에러가 나서 디버깅 하느라 시간을 많이 써서 좀 아쉽습니다.

 

F. Triangular Paths [65분]

 

이 문제에서도 좀 말렸습니다.

복잡해보이지만 수학 + 아이디어 문제입니다.

$ (r,c) $ 에서 $ r - c $  값이 같은 노드들은 연관성이 있다는 사실을 알면 쉽습니다.

 

1. $ r - c $ 를 2로 나눈 값이 같을 때

 

$ r - c $ 가 2로 나눠지는 곳으로 가는 것은 항상 그 위치의 높이 - 지금 위치 높이를 더해주어야 하고

$ r - c $ 가 2로 나눠지지 않으면 안해주어도 됩니다.

 

2. $ r - c $ 를 2로 나눈 값이 다를 때

 

그냥 그 지점으로 가는 길만 이어주면 됩니다.

따로 높이만큼 내려갈 필요가 없습니다.

 

G. Maximize the Remaining String [92분]

 

알파벳 별로 현재 이 알파벳이 있는 위치를 set 에다 다 넣어줍니다.

그러고 난 뒤 알파벳 $ a $ 가 알파벳 $ b $ 보다 앞설 수 없는 조건은

$ a $ 가장 왼쪽 위치가 $ b $ 의 가장 오른쪽 위치보다 클 때 입니다.

즉 그런 조건이 없는 알파벳을 priority_queue에다가 넣은 뒤 순서대로 string 에다 추가해줍니다.

그런데 여기서 중요한 점은 string 에 추가된 그 알파벳의 왼쪽 위치보다 적은 위치를 가지는 알파벳들에 대해서 set에서 제거를 해줘야 한다는 점입니다.

그러므로 한 알파벳이 string 에 추가되면 다시 그 위치 조건을 재계산해서 prioritiy_queue 를 돌려주면 됩니다.

 

 

##후기

 

오랜만에 대회 후기를 적네요 ㅋㅋ

후기를 적는 게 살짝 귀찮은 감이 있지만 그래도 꾸준히 적을려고 노력해야 겠습니다.

이번 대회 20~30분은 더 빨리 풀 수 있었는데 E 에서 구현 실수와 F 에서 잘못된 논리를 코딩 하느라 버린 시간들 때문에 너무 아쉬웠습니다.

그래도 오랜만에 패널티 없는 올솔이라 기분은 좋긴 하네요 ㅎㅎ

딥3라 70등이 큰 의미가 있는 등수는 아니지만 100등안에 든 게 정말 오랜만이라 또 기분이 좀 좋습니다.