Educational Codeforces Round 154 (Rated for Div. 2)

8월 31일 진행한 에듀케이셔널 코드포스 154번 대회 일지입니다.
이번에도 4문제를 30분만에 풀어내고 E번을 풀지 못했습니다. 레이티드 4솔 중 5등 정도 한 것 같습니다.

0:00~0:02

• A번 Prime Deletion을 잡았습니다.
• 발상 1(1분): 13이나 31 중 하나는 무조건 발견됩니다. 1이 먼저 오는지 3이 먼저 오는지 구분하면 됩니다.
• 빠르게 풀었습니다.

0:02~0:08

• B번 Two Binary Strings를 잡았습니다.
• 각 string이 0으로 시작해 1로 끝난다는 사실(문제 조건)을 2분 후에 발견했습니다.
• 가정 1(3분): 두 string의 같은 위치에서 ‘01’이라는 substring이 나오면 YES, 아니면 NO입니다. YES 쪽이 가능함은 자명하며, substring이 발견되지 않을 때 NO임을 증명해야 합니다.
• 발상 1 (4분): 두 string을 0..01..10..01..1으로 줄일 수 있다고 합시다. 그러면 두 string 모두를 0..01..1으로 줄일 수 있습니다. 따라서, 두 string을 같게 만들 수 있다면 두 string을 모두 0..01..1 꼴의 같은 string으로 줄일 수 있습니다.
• 이제 다음과 같은 증명이 필요합니다: “0..01..1으로 줄일 수 있는 모든 string은 0..01..1으로 한 번에 줄일 수 있다.” 그러나 약간의 직관과 함께 여기까지의 발상이면 이는 거의 사실일 것이라 생각했고, 따라서 증명하지 않고 구현해서 맞았습니다.

0:08~0:18

• C번 Queries for the Array를 잡았습니다.
• 1이 나올 경우 그곳까지의 string과 모든 prefix은 무조건 정렬되어 있습니다. 0이 나올 경우 적어도 그곳까지의 string과 일부의 긴 prefix는 정렬되어 있지 않습니다.
• 따라서, 1이 나올 때마다 그곳까지의 string이 정렬되어 있다는 사실을 표기하고 0이 나올 때마다 그곳과 그 오른쪽의 prefix는 정렬되어 있지 않다는 사실을 표기하면 됩니다.
• 이때, 정렬되어 있지 않은 string의 길이가 2 미만이거나 정렬되어 있는 칸의 수보다 작거나 같은 경우가 유일하게 NO를 출력해야 하는 경우입니다. 이외의 경우 무조건 YES를 출력합니다.
• 발상 자체에는 얼마 걸리지 않았고, 구현 문제였습니다. 10분 정도 걸려 맞았습니다.

0:18~0:29

• D번 Sorting By Multiplication을 잡았습니다.
• 발상 1(2분): 음수가 곱해지지 않는 경우, 그냥 증가하는 수열을 잘 만들면 됩니다. 이때 다음을 가정합니다: $a_i \geq a_{i+1}$인 i의 개수가 최소 동작 횟수이다.
• 증명 1(3분): $a_i \geq a_{i+1}$인 i에 대해, 이를 증가하도록 만드려면 어떠한 수를 $a_i$에는 곱하지 않고 $a_{i+1}$에는 곱해야 합니다.
• 발상 2(5분): 음수가 생기는 경우, 왼쪽의 몇 개의 수에 대해 -1을 곱한 뒤 발상 1을 역순으로 적용하면 됩니다.
• 발상 3(6분): 발상 1의 개수는 prefix/suffix에서 계산하여 부분 합으로 나타낼 수 있습니다. 이를 $O(n)$에 계산해 두면 양/음의 경계가 어디인지에 따라서 각각을 증가하도록 만드는 경우의 수를 $O(1)$에 구할 수 있습니다. 따라서 풀이가 가능합니다.
• 구현했고, 맞았습니다. 당시 순위는 30등 정도였습니다.

0:29~1:40

• E번 Non-Intersecting Subpermutations을 잡았습니다.
• 발상 1: 길이 r, subpermutation이 t개인 문자열의 개수를 길이 r-1, subpermutation이 t개인 문자열의 개수와 그 이전의 값들을 이용해 멋진 DP+포배로 구할 수 있다고 생각했습니다.
• 그 이후로 진전이 없습니다. 못 풀었습니다.

후기

• 쉬운 문제 발상력은 정말 좋은 것 같습니다. 어려운 문제를 1시간 이내에 풀 수 있는 능력이 필요합니다.
• 퍼플에 6번째 왔습니다. 이번에는 좀 안 떨어지면 좋겠습니다.