Codeforces Round 933 (Div. 1)

코드포스 933번 대회 일지입니다. 내가 누구? Codeforces Master

0:00~0:05

• A번을 잡았습니다.
• 발상 1: 정렬해서 작은 수부터 보면 좋습니다.
• 발상 2: 0부터 T까지 모든 수가 나타나면서, 1개인 수가 1개 이하로 있으면 MEX를 T+1으로 유지할 수 있습니다.
• 구현했고 맞았습니다.

0:05~0:38

• B번을 잡았습니다.
• 발상 1: 팰린드롬이 아닌 것이 하나라도 있으면 됩니다. 아마도, 모든 문자가 같은 문자가 아니면 2 이상의 모든 길이에서 팰린드롬을 찾을 수 있을 것입니다.
• 발상 2: 이때, 전체 길이의 문자열이 팰린드롬인지는 따로 확인해야 합니다. 매내처를 이용하면 빠르게 볼 수 있습니다.
• 구현하고 틀렸습니다.
• 발상 3: ababab..꼴의 문자열인 경우 홀수 길이의 비팰린드롬 문자열이 없습니다. 이러한 경우 예외를 해줘야 합니다.
• 구현하고 맞았습니다.

0:38~1:50

• C번을 잡았습니다.
• 발상 1: 트리의 두 정점 간 거리가 가장 긴 것은 지름입니다. 즉 지름을 잡으면 도움이 됩니다.
• 발상 2: 트리의 지름을 떼와서, 그 line graph에서 해법을 생각해 봅시다. 한 번에 칠할 수 있는 정점이 2개 이하이므로, 길이 $N$에 대해 적어도 $[(N+1)/2]$번 지워야 합니다.
• 발상 3: 이것을 시행할 수 있는 일반적인 해를 생각합시다. $N$이 홀수인 경우, 지름의 중심에서 반지름 0, 1, …, $(N-1)/2$를 모두 칠하면 됩니다. 일반적인 트리에서 모든 정점이 칠해진다는 사실을 쉽게 확인할 수 있습니다.
• 발상 4: 짝수인 경우, 중심과 가장 가까운 점이 2개입니다. 둘 중 하나에서 반지름 0, 1, …, $N/2$를 모두 칠하면 됩니다만, 이는 $[(N+1)/2]+1$입니다. $N=6$인 line graph를 생각하면, $[(N+1)/2]$번 칠하는 것은 불가능해 보입니다.
• 구현했고 틀렸습니다.
• 발상 5: 근데, $N=4$인 line은 2번으로 처리가 됩니다. 잘 생각해보면, $N$이 4의 배수인 경우 항상 처리가 가능합니다. 이에 대한 일반적인 방법을 생각해 봅시다.
• 발상 6: 중심과 가장 가까운 점이 2개에서, 홀수 반지름만 골라 칠하는 방법이 있습니다. 이렇게 하면 최대 채색이 가능합니다.
• 구현했고 맞았습니다.

1:50~2:25

• D를 봤습니다.
• 15분 정도 생각하여 대략의 풀이를 생각해냈는데, 10분 내에 구현할 수 없을 것이라 판단했습니다. 어차피 안 풀어도 오렌지일 것 같아 가만히 있었습니다.
• 대회가 10분 연장되었습니다. 이럴 줄 알았으면 구현해볼 걸 그랬습니다. 오렌지 컷에 아슬아슬하게 걸쳤습니다.

후기

• 정말 악착같이 각 문제를 풀어낸 것 같습니다. 저는 제가 C를 못 풀 것이라 생각했습니다.
• 오렌지에 왔습니다. 내가 누구? “Master”