Codeforces Round 884 (Div. 1 + Div. 2)
7월 11일에 진행한 코드포스 884번 대회 일지입니다. 레이팅이 50 떨어져서 다시 블루로 똑떨했습니다.
0:00~0:03
- A번 Subtraction Game를 잡았습니다.
- 배스킨라빈스 게임에서 반드시 돌을 정확히 a개 혹은 b개 가져올 때, 후공이 이길 수 있는 돌의 수를 구하는 문제였습니다.
- 약간의 예외를 제외하면, 1을 출력하면 됩니다.
- 예외를 잘못 생각해서 1번 틀렸습니다.
0:03~0:15
- B번 Permutations & Primes를 잡았습니다.
- MEX가 소수가 되는 부분수열의 수가 최대가 되도록 주어진 길이의 퍼뮤테이션을 잡으면 되는 문제였습니다.
- 1을 포함하지 않는 부분수열의 수를 최소화하기 위해 1을 가운데에 두고, 아무 소수(2와 3)을 맨 왼쪽과 오른쪽에 두면 됩니다.
- 1의 위치가 상관 없다고 생각해서 12분에 1회 틀렸습니다.
0:15~0:47
- C번 Particles을 잡았습니다.
- 그리디하게 공을 빼내면 되는 문제였습니다.
- 연속되지 않은 수를 고르는 최대 부분합 문제라 생각했고, DP를 구현한 뒤 27분, 28분, 31분에 총 3회 틀렸습니다.
- 홀수 자리와 짝수 자리로 나누어 각각에서 원소 몇 개를 골랐을 때 최대합 중 더 큰 것이 답이라는 것을 알아냈고, 45분에 1회 틀린 뒤 47분에 맞았습니다.
- 틀린 관찰에서 너무 오래 있었는데, 이게 이번 대화 똑떨의 가장 큰 이유라고 생각합니다.
0:47~1:00
- D번 Row Major을 잡았습니다.
- 8의 답이 3, 6의 답이 4, 3 이상 소수의 답이 2라는 것을 알아냈습니다.
- 이를 통해 주어진 수의 약수가 아닌 최소의 수가 답이라고 생각했습니다.
- Proof by AC를 받았습니다.
1:00~1:30?
- E번 Great Grids을 잡았습니다.
- 30분동안 관찰 및 아이디어 발상을 했습니다.
- 첫 번째 발상: 모든 2x2 부분배열에 대해서, 각 부분배열은 대각선으로 같은 원소를 포함하고 있습니다. 이 대각선의 방향을 0과 1으로 두면, 크기 $(n-1)*(m-1)$의 새로운 bool-배열을 만들 수 있습니다.
1:30?~2:00?
- 두 번째 발상: 이 bool-배열에서 다시 2x2 부분배열을 잡으면, 그 원소의 합이 짝수여야 합니다.
- 세 번째 발상: 중간에 원소 몇 개가 비어 있어도 이는 동일하게 성립합니다. 더 엄밀히 말해서, (a,b), (a,d), (c,b), (c,d) 네 원소는 a+2<c이고 b+2<d인 모든 a, b, c, d에 대해 그 원소의 합이 짝수여야 합니다.
2:00?~2:40
- 네 번째 발상: 이것이 가능한 모든 정사각형을 탐색한다면, (주어지는 pair n개에 대해) $O(n^2)$에 이를 확인할 수 있는 자명한 방법을 알아냈습니다.
- 다섯 번째 발상: 그런데 이것만 확인한다고 배열이 가능하다고 이야기할 수 없습니다. 전체 도형 내에서 각 부분사각형은 완전히 독립적이지 못하므로, 이것 외에도 더 많은 처리가 필요합니다.
- 여섯 번째 발상: 위의 ‘처리’를 처리할 수 있는 증명되지 않았고 불확실한 방법으로, 모서리가 x축 혹은 y축에 평행한 폐곡선? 형태를 가질 때 각 꼭지점에 해당하는 원소의 합의 기우성이 짝수인지 확인하는 것이 있습니다. 그런데 이것이 가능한지, 시간복잡도가 적절히 작은지, 어떻게 구현할 지에 대한 아이디어를 찾지 못했습니다.
2:40~3:00
- 친구들에게 B~D번 문제의 풀이를 설명했습니다. D를 엄청 어렵게 푼 친구들이 있었습니다.
- windva 선배님과 chaeyihwan 선배님에게 E번 문제의 해설을 들었습니다. windva 형은 대각선의 방향이 같은 걍우를 두 가지로 나누어 4가지 경우로 나눈 뒤 이를 기반으로 풀이했고, chaeyihwan 형은 폐곡선 아이디어에서 조금 더 나가서 DFS로 그게 성립하는 지 무언가 탐색을 했다고 했습니다. (에디토리얼 1번 풀이를 비슷하게 구현하신 것 같습니다.)
후기
시험 이후 첫 코포인데 그래도 D까지 풀어내기는 했고 E도 절반 정도의 아이디어를 냈으니 실질적인 퍼포먼스는 나쁘지 않았다고 생각합니다. 다만 C에서 잘못된 발상에 갇혀 있었던 것은 좀 아쉬웠던 것 같습니다.
This post is licensed under CC BY 4.0 by the author.