Codeforces Round 898 (Div. 4)

2023년 9월 22일에 진행한 코드포스 898번 대회 일지입니다. G까지는 잘 풀었는데 H에서 막혀서 90분 올솔했습니다. 아깝네요

0:00~0:01

• A번을 잡았습니다.
• 발상 1(0분):제자리에 있는 게 1개라도 있으면 YES, 아니면 NO입니다.
• 제출했습니다.
• 후기: 전형적 코포식 브론즈 그리디 문제였습니다. 빠른 구현 방법에 대해 n초 정도 고민한 것 같습니다.

0:01~0:02

• B번을 잡았습니다.
• 발상 1(0분): 작은 수에 1을 더하는 것이 효과가 더 큽니다. 즉 정렬해서 1번에 1을 더하고 곱하면 됩니다.
• 제출했습니다. A를 맞은 것을 확인했습니다.
• 후기: 브론즈 그리디 정도, 작은 것인지 큰 것인지 n초 정도 고민했습니다. 구현이 A보다 조금 더 어려웠습니다.

0:02~0:05

• C번을 잡았습니다.
• 발상 1(0분): 0베이스를 기준으로 할 때, (4, 4)와의 거리(xy차 중 최댓값)의 천장함숫값을 구하면 답과 비슷합니다.
• 발상 2(1분): 그 값에서, 0 이하인 값은 1을 더 빼주면 답입니다.
• 제출했습니다. B를 맞은 것을 확인했습니다.
• 후기: 브론즈 쌩수학 구현 문제, 마찬가지로 빠른 구현 방법을 고안하는 데 시간을 1분 정도 사용했습니다.

0:05~0:07

• D번을 잡았습니다.
• 발상 1(0분): 그냥 for 돌면서 B가 나올 때마다 거기서부터 $k$칸을 지워주면 됩니다.
• 제출했습니다. C를 맞은 것을 확인했습니다.
• 후기: 이런 것도 그리디겠죠? 코포를 접해보지 않았으면 발상의 유효성에 대해 고민하는 데 시간이 좀 걸릴 것 같은 문제입니다.

0:07~0:11

• E번을 잡았습니다.
• 발상 1(1분): 정렬해서 각 기둥별로 그 앞의 것을 채울 때 물을 다 쓰는지 확인해볼 수 있습니다. 선형적으로 구할 수 있습니다.
• 제출했습니다. D가 아직 채점되지 않았습니다.
• 후기: 히스토그램 생각 나는 실버급 그리디 구현 문제. 이 정도면 웰논 베이스 문제라 생각합니다. 2A와 2B 사이 난이도 정도라고 생각합니다.

0:11~0:20

• F번을 잡았습니다.
• 발상 1(4분): 그냥 큐를 만들어서 투포인터를 하면 됩니다. $h_i$가 약배수 관계가 아니게 될 때마다 큐를 비우고, 그게 아니면 계속해서 $\sum a_i$의 최대를 찾으면 됩니다.
• 제출했습니다. D와 E의 채점 결과를 받았고, E가 틀린 것을 확인했습니다.
• 후기: 투포를 해도 된다는 발상이 실버 상위는 가는 것 같습니다. 그래도 웰논 베이스라서 풀기 어렵지 않다고 생각합니다. 왜 9분이나 걸렸는지는 기억이 나지 않습니다.

0:20~0:22

• E번을 디버깅했습니다.
• 가능한 오류: 물을 다 쓸 수 있을 때 남은 물을 채우는 작업을 두 번 할 수 있는 예외를 확인했습니다.
• 처리했고 제출했습니다. F를 맞은 것을 확인했습니다.

0:22~0:28

• G번을 잡았습니다.
• E AC를 확인했습니다.
• 발상 1(1분): AB를 BC로 줄이는 것은 A…AB를 BC…C로 줄이는 것과 같습니다. BA를 CB로 줄이는 것도 비슷합니다. 따라서, 각 B는 그 B의 왼쪽에 있는 연속한 A를 모두 지우거나 오른쪽의 연속한 모든 A를 지울 수 있습니다.
• 발상 2(3분): 그렇다면, 모든 B에 대해 그 사이사이에 있는 A를 볼 때 그중 하나 빼고 다 선택해 지울 수 있습니다.
• 제출했습니다.
• 후기: 발상이 그리 쉽지는 않은 것 같습니다. 여전히 해는 깔끔하기 때문에 좋은 문제인 것 같습니다.

0:28~1:29

• H번을 잡았습니다.
• 발상 1(1분): 그래프에 사이클이 단 1개 존재합니다. 이러한 사이클을 활용하면 Valerie가 영원히 도망갈 수 있습니다.
• 발상 2(8분): Valerie가 도망갈 수 있는 경로에 대해 잘 생각해 보면, 우선 사이클에 이미 Valerie가 있는 경우 탈출 가능합니다(맞았습니다). 그렇지 않은 경우, Valerie가 사이클로 가는 경로상에 있는 경우 탈출 가능합니다(틀렸습니다).
• 구현했고 예제를 틀렸습니다.
• 발상 3(20분): Valerie가 사이클로 최단경로로 갈 때 도달하는 노드에 대해, Valerie가 그 노드까지 Marcel보다 먼저 갈 수 있는 경우 탈출 가능합니다(맞았습니다).
• 구현했고 테케를 틀렸습니다.
• queue에서 자꾸 front 말고 back을 꺼내오고 있었습니다. 때문에 30분 정도 디버깅했고 5번 틀렸습니다.
• 맞았습니다.

후기

• queue의 back을 가져와서 틀리는 놈이 어디 있습니까? 정말 마음이 아팠습니다.
• 레이티드 기준 퍼포는 오렌지 초반 정도인 것 같습니다. 올솔을 했다는 사실에 의미를 두어야겠습니다.