Educational Codeforces Round 155 (Rated for Div. 2)

9월 24일 진행한 에듀케이셔널 코드포스 155번 대회 일지입니다. 새로울 것을 배워가는 의미?있는? 대회였습니다.

0:00~0:02

• A번을 잡았습니다.
• 발상 1(1분): 0번보다 힘도 세고 지구력도 강한 사람(같은 경우도 포함)이 존재하면 불가능하고, 아니면 정확히 0번의 지구력만큼 하면 됩니다.
• 구현했고 맞았습니다.

0:02~0:07

• B번을 잡았습니다.
• 발상 1(4분): 모든 행을 칠하거나 모든 열을 칠해야 합니다. 이를 최소로 하는 경우는 a의 합과 b의 최소 혹은 b의 합과 a의 최소이며, 둘 중 더 작은 것을 출력합니다.
• 구현했고 맞았습니다.

0:07~0:15

• C번을 잡았습니다.
• 발상 1(2분): 각 연속한 수에 대해, 모든 연속한 수를 길이 1로 압출하는 경우가 최적입니다. 이에 도달하기 위해서는 연속한 모든 수에 대해 그 길이가 a라면 a!개의 경우씩이 나옵니다(틀렸습니다).
• 구현했고 틀렸습니다.
• 발상 2(5분): 그런데 지우는 순서는 전체 수열을 통틀어서도 상관이 없습니다. 즉, 연속한 수의 길이를 배열로 만든 것이 $a_1, a_2, …, a_n$이라면 $a_1a_2…*a_n$에 $((a_1-1)(a_2-1)…(a_n-1))!$를 곱한 것이 답입니다.
• 구현했고 맞았습니다.

0:15~1:26

• D번을 잡았습니다.
• 발상 1(?): 누적 xor합을 한 배열에서 임의의 두 값을 xor하면 그 사이 원소의 전체 xor값을 알 수 있습니다.
• 발상 2(?): 이때 출력값은 누적 xor 배열의 모든 pair의 xor 각각에 대해 일정한 가중치를 곱해 출력하는 것입니다.
• 학습: xor 연산의 합에 대한 분배 법칙이 항상 성립하는 연산이 있으면 이를 빠르게 풀 수 있습니다. 이러한 연산이 있는지 찾아보았습니다.
  • 이러한 것은 존재하지 않기 때문에, 사용할 수 없습니다. 이 글에서 설명을 볼 수 있습니다.
• 학습: 임의의 배열의 모든 원소쌍의 xor의 합을 빠르게 구할 수 있는 방법이 있을 지 궁금해졌습니다.
  • 구글에 sum of xor of all pairs in an array를 검색해 이 글을 찾았습니다. 길이 n의 배열에서 쌍-xor-합을 $O(nlogn)$에 구할 수 있다는 사실을 알아냈고, 우선 증명은 확인하지 않았습니다.
• 그러나 이는 일정한 가중치를 곱하는 과정을 수행하는 데 사용할 수 없습니다. 구하고자 하는 답을 카운팅할 수 있는 다른 방법을 찾아보고자 했습니다.
• 발상 3(?): 임의의 원소에 대해 그 원소를 포함하는 모든 구간의 xor합을 구해주면 됩니다.
• 발상 4(?): 이를 누적 xor 배열에서 설명하면, 임의의 원소에 대해서, 그 왼쪽 값들의 원소들과 오른쪽 값들의 원소 사이의 모든 xor값의 합을 구하면 됩니다.
• 발상 5(?): 그런데 이를 생각해보면, 이는 전체 배열의 쌍-xor-합에서 왼쪽 값들의 쌍-xor-합과 오른쪽 원소들의 쌍-xor-합을 빼주면 구할 수 있는 값입니다.
• 발상 6(?): 위 글의 증명을 읽어 보았습니다. 알고리즘의 순서를 잘 바꾸면, 저 알고리즘을 이용해 맨 앞 길이 1까지의 쌍-xor-합, 길이 2까지의 쌍-xor-합, …, 길이 n까지의 쌍-xor-합을 모두 구하는 데에도 상수가 약간 더 큰 $O(nlogn)$에 구할 수 있는 사실을 알아냈습니다.
• 이를 이용해면, 앞쪽 누적-쌍-xor-합, 뒤쪽 누적-쌍-xor-합을 모두 구한 다음에 전체 배열 쌍-xor-합의 n배에서 위에서 구한 양쪽의 누적-쌍-xor-합의 총합을 빼주면 답을 구할 수 있습니다!
• 구현했고 맞았습니다.

1:26~2:00

• E번을 잡았습니다.
• 발상 1(5분): 색 3개를 사용하면 무조건 칠할 수 있습니다.
• 발상 2(12분): 색 2개를 사용할 수 있는 특수한 경우가 몇 가지 있습니다.
  • 문제가 될 수 있는 것이, 트리의 루트와 리프 노드 제외 모든 노드의 간선 수가 3 이상인 경우입니다. 이때는 색 2개로 번갈아 칠한 뒤 하나 있는 쪽으로 계속 올라갈 수 있습니다.
• 발상 2-1(25분): 두 가지 색으로 칠할 수 있는 경우가 하나 더 있는데, 루트와 리프 노드 제외 모든 간선 수가 2인 정점에 대해 이러한 정점에서 무조건 한 색으로 올라가게 할 때 종결이 되는 경우입니다.
  • 이러한 경우는 모든 루트와 리프 노드 제외 모든 간선 수가 2인 정점이 같은 깊이에 있는 경우로 reduction할 수 있습니다(틀렸습니다).
• 구현했고 틀렸습니다.

2:00~2:15

• E에 대해 windva, iccodly님과 좀 더 생각했습니다.
• 위 발상 2-1의 reduction이 틀리는 반례를 생각해냈습니다.
• windva님은 같은 경우를 생각하지 못해 틀린 것 같았고, iccodlt는 구현 이슈로 틀렸다는 것 같았습니다.

후기

• E번은 참 잘 낸 문제인 것 같습니다.
• XOR에 대한 새로운 것을 또 배워갑니다. 참 신기한 연산자인 것 같습니다.
  • 어쨌든 각 비트의 수를 잘 보는 것이 중요하구나 싶었습니다.
• D를 푸는 데 시간을 좀 너무 많이 쓴 것 같습니다.