2개월만에 참여하는, 종강 후 첫 대회이다.
A번 문제 치고 문제가 복잡해서 시간을 많이 뺐겼다.
6분에 AC
B: Red and Blue
각각의 누적합 최댓값을 더해주면 된다. 이게 왜 11분 걸렸지..?
17분에 AC
각 x축 위치마다, fence를 build할 수 있는 구역이 하나의 연속된 구간으로 정해짐이 문제 풀이의 핵심이다. O(n)으로 이 구역을 계산해나가면 된다.
43분에 AC
정말 많은 시간을 투자한 문제다. 대회 종료 후 두명의 친구에게 물어본 결과, 세명이 전부 다 다른 풀이로 해결했었다. n과 하나의 숫자만을 남기고 전부 다 1로 바꿔놓고, 두 숫자를 남은 횟수 이내에서 1 하나와 2 하나로 만들려고 했었다. 남겨놓을 숫자를 deterministic하게 찾으려고 하다가, 결국 찾지 못하고 세개의 숫자를 남겨놓는 풀이로 넘어갔다. 4,8,n을 남겨놓은 후, n을 8로 여섯 번 나눈 후 4,8을 1,2로 만들면 항상 n+5번만에 처리가 가능하다. 그런데 대회 종료 이후에 친구 풀이를 보니, 두개의 숫자를 남기는 풀이에서 남겨둘 숫자 하나를 deterministic하게 정할 이유가 없었다. n 이외에 남겨놓을 숫자를 O(n)으로 탐색하면서 횟수 이내로 들어오는지 검사하는 것이 가능하다...
1시간 33분에 AC
반쯤 풀고 대회가 종료되었다. 처리해야 하는 문자열들이 하나의 문자열의 substring들이라는 사실에 초점을 두어 생각을 해보다가, 진전이 없어 방향성을 틀었다. 각 substring에 대해, 'bit similar'하지 않은 문자열은 하나씩밖에 없다는 사실까지 발견하고 대회가 끝났다.
대회 종료 이후 pasa3232로부터 풀이의 나머지 절반을 들었다. Substring의 개수는 106개에 불과하므로, bit similar하지 않은 문자열 중 그 integer값이 106보다 작은 경우만 기록해주면 된다. Bit similar하지 않은 문자열의 집합에 포함되지 않는 문자열 중 integer값이 제일 작은 문자열을 찾는 문제이므로, 이보다 큰 경우는 정답에 영향을 주지 못함을 알 수 있다.
총평
오랜만에 한 대회라 살짝 실력이 녹슨 것 같았다. (특히 초반 문제들에서..)
하지만 우려했던 바와는 달리 무난하게 레이팅 방어를 할 수 있었다. 컨디션이 좋았더라면 E를 해결하고 더 큰 폭으로 올랐을수도?
레이팅 변화 1917 + 26 = 1943
My Performance: ★★☆☆☆
연습지

'Competitive Programming > Codeforces' 카테고리의 다른 글
대회후기: Codeforces Round #694 (Div. 2) (0) | 2021.01.08 |
---|---|
대회후기: Good Bye 2020 (0) | 2021.01.02 |
대회후기: Codeforces Round #678 (Div. 2) (0) | 2020.10.26 |
대회후기: Codeforces Round #663 (Div. 2) (0) | 2020.08.10 |
대회후기: Codeforces Round #662 (Div. 2) (0) | 2020.08.10 |