Refact.ai Match 1 (Codeforces Round 985, Div. 1 + Div. 2)

2024년 11월 9일에 참가한 코드포스 985번 대회 일지입니다. 오렌지로 3번째로 복구했습니다. 망하지 않을 때의 표준 퍼포먼스를 냈다고 생각합니다.

0:00~0:02

• A번을 잡았습니다.
• 수학스러운 전형적인 A번 문제였습니다. 구현했고 맞았습니다.

0:02~0:10

• B번을 잡았습니다.
• 대략 5분동안 이런저런 발상을 했던 것 같습니다.
• 그러다가 $s$의 01이나 10이 $r$이 0이면 0으로, 1이면 1으로 환원해준다는 것에서, 0과 1의 개수만 가지고 풀 수 있겠다는 생각을 했습니다.
• 이게 가능하면 항상 가능한가? 라는 생각을 했고 맞다는 것을 바로 알 수 있었습니다.
• 그래서 구현했고 맞았습니다.

0:10~0:28

• C번을 잡았습니다.
• 가운데 구간이 스킵되므로, 왼쪽과 오른쪽에서 일정 부분씩을 적용하면 됩니다.
• 왼쪽은 시작값이 정해져 있으므로 단순 DP로 밀면 인덱스까지의 계산값을 알 수 있습니다.
• 오른쪽은 종점만 정해져 있기 때문에 그게 불가능합니다. 여기까지의 발상은 trivial했던 것 같습니다.
• 예제를 가지고 생각해봅시다. 값은 최대 1밖에 변화하지 않으므로, 최댓값이 확확 바뀌는 일이 없습니다. 따라서, 일정 인덱스까지 왼쪽 구간의 최댓값으로 오른쪽 구간을 시작하는 경우를 생각하면 됩니다.
• 따라서 그리디입니다.
• 구현했고 맞았습니다.

0:28~1:24

• D번을 잡았습니다.
• 발상: 크기 N의 사이클이 있으면 O(N)번의 동작으로 그 사이클의 모든 간선을 삭제할 수 있습니다.
• 이걸 잘 하면 모든 사이클을 없앨 수 있습니다. 그러면 트리 내지는 포레스트가 만들어지므로 그 뒤로 O(N)번 정도의 동작으로 트리를 구성할 수 있을 것 같습니다.
  • 문제: 어떤 사이클 하나를 삭제하면 다른 사이클이 같이 없어질 수 있습니다. 즉, cycle detection과 cycle deletion을 동시에 동적으로 하면서 그 복잡도는 O(N+M) 안쪽을 유지해야 합니다.
• 발상: 아주 적절한 DFS 오더링과 재귀함수를 이용하면 가능할 것 같습니다. 약간 선인장이 생각나는 느낌입니다.
• 발상: 그래프에서 차수가 2 이상인 정점을 아무거나 잡아서, 그 정점이랑 정점과 연결된 두 정점을 선택해 연산합니다. 그러면 무조건 간선의 수가 1 줄어듭니다. 이 연산을 더 가할 수 없다면 트리나 포레스트이므로, 잘 하면 될 것 같습니다.
  • 문제: 근데 이것도, 연산을 통해 다른 정점의 차수가 늘어날 수 있습니다. 따라서 ordering을 잘 해야 합니다.
  • 발상: 그렇지 않습니다. 그냥 무지성으로 짜면 됩니다.
• 구현했고 맞았습니다.

1:24~2:00

• E번을 잡았습니다.
• 발견: 일단 소수가 두 개 있으면 불가능함이 자명합니다.
• 발상: 2가 있다면, 소수를 제외한 모든 수를 표현할 수 있습니다. 즉, 소수가 없다면 2를 출력하면 됩니다.
• 그럼 해야 하는 것은, 어떤 소수를 가지고 어떤 수를 표현할 수 있는지 - 더 정확히는, 어떤 수를 표현할 수 없는지 알아야 합니다.
• 발상: 어떤 소수 $p$에서 어떤 짝수 $2a$로 가는 것은, $a \geq p$인 경우 항상 가능합니다.
• 가정: 어떤 소수 $p$에서 어떤 홀수인 합성수 $b$로 갈 때, $b$의 가장 작은 소인수보다 $p$가 작거나 같으면 가능하고, 아니면 불가능합니다.
  • 사실이 아닙니다. 3에서 8로 갈 수 있습니다.
  • 비슷한 느낌의 무언가를 냈고 틀렸습니다.
• 가정: $b$가 $1.5(2p+2)$ 이상이면 가능합니다.
• 구현했고 맞았습니다.

2:00~3:00

• F번을 잡았습니다.
• 발견: 만약 BB와 RR이 둘 다 있다면, 각각의 중간을 시/종점으로 잡으면 불가능합니다. 따라서 R이랑 B 중 하나는 연속하지 않습니다.
  • 대충 RRR..RRBRR..RRBRR..RRBRR.. 형태로 나타납니다. B가 몇개 있고 그 사이에 들은 R의 개수가 몇개씩인지로 문자열을 구성할 수 있습니다.
• 발견: B가 1개라면, 항상 가능합니다.
• 발견: B가 2개일 때, 두 R들의 길이의 홀짝성이 달라야 합니다. 같으면 불가능합니다.
• 발견: B가 3개 이상이면 불가능한 것으로 보입니다.
• 제출했고 틀렸습니다.
• B가 3개 이상일 떄 가능한 케이스가 있음을 확인했습니다. (대회가 약 10분 정도 남아있었습니다.)
• 조건을 구체화하지 못했고 결국 못 풀었습니다.

후기

• 나름 느낀 것이 많은 대회였습니다. 이번 대회에서 저는,
  • 말리지도 않았고, 그렇다고 D나 E를 빠르게 풀어내지도 못했습니다.
  • 고로 오늘의 퍼포먼스가, 풀어야 하는 문제에서 말리지도 않고, 딱히 운이 좋아서 문제가 술술 풀리지도 않은, 표준적인 퍼포먼스라 생각했습니다.
  • 그런 정도의 속도로 문제를 풀었을 때, F를 푸는 데 20~30분 정도가 부족했다는 생각입니다.
  • 이를 개선하기 위해서는, D~E정도의 문제를 조금 더 빠르게 해결할 수 있어야 한다고 생각했습니다.
  • 따라서 지금 필요한 것은, 난이도 1800~2100 정도의 문제를 푸는 데 걸리는 시간을 줄이는 것이라는 결론을 냈습니다.
  • 원래 저에게 1800~2100대 문제는 ‘어떻게든 풀면 좋은 문제’였는데, 이제는 ‘푸는 데 시간이 오래 걸리거나 못 풀면 나쁜 퍼포먼스인 문제’가 된 것 같습니다.
  • 이번 대회의 ‘말리지도 운이 좋지도 않은’ 상황에서 퍼포가 2200 중반 정도 나왔으므로, 실력의 현재 상한은 2100~2300 정도로 보입니다.
  • 그런데 이 상한을 돌파하기 위해서는 1800~2100 문제를 연습하면 됩니다.
  • 고로, 제 앞의 벽이 적당히 멀리 있는 동시에 그리 높지 않은 벽이라는 생각을 했습니다. 매우 긍정적입니다.
• 오렌지에 3개월만에 복구했습니다. 반년대회 개최를 전후로 해서 CP 실력이 많이 떨어졌다고 생각했는데, 슬슬 복구가 끝나지 않았나 싶습니다.
• 여담으로, 다음날 있던 딥2를 그 다음날에 버추얼로 돌았습니다. 퍼포는 약 2600입니다. 운 좋으면 상한이 300 이상 늘어나나 봅니다.