CodeTON Round 8 (Div. 1+2)

2024년 4월 2일 진행한 코드포스 코드톤 8회 대회 일지입니다. 2300대 퍼포를 내며 안정적으로 오렌지에 안착하고 있습니다.

0:00~0:02

• A번을 잡았습니다.
• 관찰: Cyclic Shift 이후에도 오름차순이려면 모든 원소가 같아야 합니다.
• 따라서 $n=k$나 $k=1$만 각각 구성해주면 나머지는 불가능합니다.
• 구현했고 맞았습니다.

0:02~0:10

• B번을 잡았습니다.
• 기본값은 1으로, 1이 나오면 현재의 mex값을 뱉으면 됩니다.
• 1보다 큰 수가 나오면 mex를 기준으로 그만큼 수를 늘려서 출력하면 됩니다.
• 1보다 작은 수가 나오면 무조건 현재의 mex값을 뱉어도 됩니다. 구성 가능한 경우만 주어지기 때문입니다.
• 해가 구성되는 경우를 생각하므로 예외에 대해 생각하지 않아도 됩니다. 따라서 이것만 구현하면 됩니다.
• 별다른 관찰이나 발상이 필요 없었습니다. 구현했고 맞았습니다.

0:10~0:16

• C1번을 잡았습니다.
• 간단한 수학입니다. 고른 점들을 꼭짓점으로 하는 다각형은 완전히 삼각분할되고, 그 외에 정다각형의 모서리와 고른 점 사이의 모서리로 이루어지는 삼각형을 세면 됩니다.
• 별다른 관찰이나 발상이 필요 없었습니다. 구현했고 맞았습니다.

0:16~0:37

• C2번을 잡았습니다.
• 발상: C1번에서 고른 점으로 이루어진 다각형을 제외하면 정다각형이 몇 개의 볼록다각형으로 쪼개집니다. 이들을 삼각형으로 쪼개는 것이 관건입니다.
• 발상: 다각형에 있는 모든 점을 다 선택하면 완전히 쪼갤 수 있습니다. 완전히 분할하면 삼각형이 조금 더 나오므로, 작은 것부터 하나하나 완성합시다.
• 구현했고 틀렸습니다.
• 관찰: 하나 건너 하나 선택해도 됩니다. 어차피 꼭짓점의 수는 정해져 있으므로, 하나 건너 하나 선택해서 겉을 삼각형으로 처리하고 안쪽을 분할하면 됩니다. 완전히 분할하면 삼각형이 조금 더 나오므로, 작은 것부터 하나하나 완성합시다.
• 구현했고 틀렸습니다.
• 관찰: ‘완전히 분할하면 삼각형이 조금 더 나오므로’ 는 틀린 관찰입니다. 이는 꼭짓점의 수가 짝수인 경우에는 성립하지 않습니다.
• 구현했고 맞았습니다.

0:37~1:41

• D번을 잡았습니다.
• 발상: 시간복잡도는 $O(nk)$일 것으로 보입니다. 따라서, 아마 각 칸까지 누적 최대 경우의 수 $k$개씩을 잘 관리해야 할 것 같습니다.
• 발상: 구간 $(a,b)$를 색칠할 때, $[a-2]$번째 칸 혹은 그 이전까지 색칠하는 가격들에 $(a,b)$를 색칠하는 가격을 더한 것이 $[b]$번 칸까지 색칠하는 가격에 들어갑니다.
• (여기서 40분 정도를 소모합니다.)
• 발상: 이것을 우선순위 큐로 관리할 수 있습니다. 결론적으로 우리는 가장 가격이 높은 $k$개에만 관심이 있으므로, $k$개가 채워질 때까지 가장 비싼 것들만을 고르면 됩니다. 구간 $(i,b)$를 색칠할 때 가능한 가장 높은 가격은 1가지이고, 그 다음 높은 색을 가져오는 것도 쉽습니다. 이러한 원소 $O(n)$개를 우선순위 큐로 관리해주며 가장 높은 원소를 취하고 그 다음 값으로 업데이트해주면 됩니다.
• 구현했고 맞았습니다.

1:41~2:06

• E번을 잡았습니다.
• 관찰: 게임이 종료되는 상태는 한 명이 다른 사람을 끝까지 밀어넣었을 때입니다.
• 일반성을 잃지 않고, 가장 왼쪽의 소가 FJ의 소라고 합시다.
• 관찰: FJ의 첫번째 소와 FN의 첫번째 소가 서로를 향해 가고, FJ의 두번째 소와 FN의 두번째 소가 서로를 향해 가고… 합니다. 이 쌍들을 생각합시다.
• 발상: 플레이어는 각 쌍 사이 거리의 기우성을 결정할 수 있습니다. 우승 상태는 모든 쌍 사이 거리가 짝수인 상태입니다. (이런 상태가 나의 턴이라면 내가 패배합니다)
• 발상: FJ가 항상 모든 가우성이 짝수를 유지하게끔 FN에게 턴을 넘기면 이깁니다.
• 간단한 중복조합으로 구현 가능합니다. 구현했고 맞았습니다.

2:06~3:00

• F번을 잡았습니다.
• 관찰: 앞쪽 수를 건드린다고 뒷쪽 수에 큰 영향을 주지는 못합니다. 아마 100칸 뒤부터는 아무 영향도 주지 못할 것 같습니다(이는 틀렸습니다. +1, 0, -1 세 가지는 가능합니다).
• 못 풀었습니다.

후기

• D보다 E가 쉬웠습니다. 정말 다행히 E까지 풀어서 퍼포는 2300 정도 나왔습니다.
• 요즘 퍼포먼스가 좋습니다. 39기 개쩌는 선배들의 1년 전과 비교했을 때 나쁘지는 않은 정도라서 만족합니다.