Educational Codeforces Round 153 (Rated for Div. 2)

2023년 8월 17일에 진행한 에듀케이셔널 코드포스 153번 대회 일지입니다.

0:00~0:05

• A번을 잡았습니다.
• 괄호 문제열을 가지고 노는 문제였습니다.
• 주어지는 문자열이 ‘()’이면 불가능하다는 것은 자명히 생각했습니다.
• ((..()..))나 ()()..()() 둘 중 하나로 채우면 될 것 같았고, 구분 기준을 찾으려고 했습니다.
• ’((‘으로 구분해보려고 했는데, 반례를 찾았습니다.
• ’)(‘라는 substring을 가지고 있으면 ((((((…()…))))))로 채우고, 아니면 ()()(…)()()으로 채웠습니다. 맞았습니다.

0:05~0:17

• B번을 잡았습니다.
• 그냥 수학 + 약간 더러운 구현 문제였습니다.
• 각 동전을 최대한 사용하는 것과, 가능하다면 k불의 동전 1개를 사용해 작은 금액의 새 동전 사용을 적게 하는 것 중 더 작은 것을 계산해 출력하면 됩니다.

0:17~0:51

• C번을 잡았습니다.
• 재미있는 퍼뮤테이션 문제였습니다.
• 각 칸을 Alice Win과 Bob Win으로 두어 봅시다.
• 어떠한 Alice-win 칸에 대해, 그보다 뒤에 있고 더 큰 모든 값은 Bob-Win입니다.
• 먼저 이동할 수 없는 Bob-win 칸을 모두 셉니다. 이동 가능한 칸 중 Alice-win 칸이 없는 모든 칸은 Alice-win입니다. 나머지 칸은 모두 Bob-win입니다.
• 이를 구현하면 됩니다.

0:51~2:00

• D번을 잡았습니다.
• ‘01’은 +1, ‘10’은 -1으로 두고 그 전체 합(을 S라 둡시다)이 0이 되는 것을 찾는다고 생각했습니다.
• 어떤 두 칸을 잡고 두 수를 바꾸면, 두 수의 가운데에 있는 수의 개수가 S의 변화량의 2배가 된다는 사실을 관찰했습니다.
• DP로 잘 할려고 했지만 망했습니다. 마음이 아팠습니다.

후기

잘하면 D를 잡을 수 있었을 것 같습니다. DP 공부가 더 필요합니다. 난이도는 높으면 2000, 낮으면 1750 정도일 것 같습니다. 1800-2000대 문제를 고정적으로 풀어내야 되는데, 어렵습니다. 퍼플 복구에 실패했습니다. 마음이 너무 아픕니다.