SCPC 2021 Round 1

대회 후기

• 일단 시작하고 나서 코딩하지 않고 이 글부터 썼다.
• 이 후 이 글을 따라서 코딩했는데 2번, 4번, 5번을 틀렸다.
  • 2번은 큰 자릿수가 앞에 있다는 걸 몰랐다. 순서를 바꿔서 맞았다.
  • 4번은 88점이 나오기에 풀이가 틀렸나 했다.
  • 5번은 그냥 코딩 실수가 좀 있었고 고쳐서 맞았다.
• 698/800점을 받고 잤다.
• R2를 어쨌든 갈 거 같아서 고칠까 말까 하다가, 만점자가 꽤 많아서 무섭기도 하고, 블로그에 "이런 풀이를 짰는데 틀렸더라 ㅎㅎㅋㅋㅈㅅ" 라고 글을 쓰기는 뭐해서 4번을 생각해봤다. 설마 싶은 반례가 있었는데 머릿속으로는 이게 반례인지 아닌지 긴가민가했다. 짜 보다 보니까 반례인게 확실해 보였다.
• 고쳐서 오후 1시 반쯤 만점

1. 친구들

말이 복잡하지만 이런 뜻입니다. $N$ 개의 정점을 가진 그래프가 있고, 모든 $(i, i + D_i)$ 간에 간선을 이어 줍시다. "친구 관계" 는 두 사람이 연결되어 있다는 뜻잇고, "친구 관계인 극대 그룹" 은 컴포넌트를 뜻합니다. 왜 이 말이 저 말인지 모르겠으면 대학교 이산수학 교과서에서 "transitive closure" 이런 걸 찾아서 공부해 보시면 될 것 같습니다.

그래서 DFS나 Union-find 등으로 컴포넌트 개수를 세어주면 됩니다.

사실 그래프가 forest의 형태이기 때문에, $i + D_i > N$ 인 $i$ 의 개수를 세어줘도 됩니다. $i + D_i > N$ 인 것과, 각 트리의 루트인 것이 동치이기 때문입니다.

2. 이진수

$2t$ 간격으로 $a$ 라는 이진 수열을 끊어서 풀어줍시다. $b_{i + t}$ 가 0이면 $a_{i}, a_{i + 2t}$ 모두 0이어야 합니다. 아니면 둘 중 하나는 1이어야 합니다. 꼭 0이어야 하지 않는 수 중 하나를 골라 1로 만들어 주면 됩니다. 여기서 답을 최소화해야 하니

• 두 개 이상이면 오른쪽 것을 고르고 (지문에 별 말이 없는데 큰 자릿수가 앞에 있습니다.)
• $i$ 가 감소하는 순으로 고려해서, 값이 큰 쪽에서 최적의 선택이 된 후에만 낮은 쪽의 선택을 하도록

해 줍시다.

3. No Cycle

방향성 있는 간선들이 사이클을 만들지 않는다면 항상 답은 존재합니다. 방향성이 있는 간선들만 가지고 위상 정렬을 한 후, 방향성이 없는 간선들을 위상 정렬 순서에 맞게 매겨주면 되기 때문입니다. 아무 답이나 찾는 것은 이렇게 하면 됩니다 (=그룹 2).

사전순 최소를 찾기 위해서는 방향성이 없는 간선들을 인덱스 순서대로 처리합니다. 만약 간선을 정방향으로 넣어도 사이클이 없다면, 그대로 넣어줍니다. 아니면, 반대로 넣어줍니다. 이걸 $K$ 번 반복해 주면, 사전순 최소가 나옵니다.

사이클 판별을 $K$ 번 해 줘야 하니 시간 복잡도는 $O((N+M+K)K)$ 입니다.

여담으로, 제 블로그에 Incremental Topological Ordering and Strong Component Maintenance 라는 글이 있는데... 사이클이 한번 생기면 amortization이 끊겨서, 아마 이걸 써도 복잡도가 줄어들지는 않을 것입니다.

4. 예약 시스템

짝수밖에 없을 때

같은 행의 두 방씩을 항상 묶어서 같은 그룹에 전달해 주는 게 최적입니다. 이 전략을 사용하면, 중간에 있는 그룹은 4명이 불편하고, 끝에 있는 그룹은 2명이 불편합니다. 모두 4명이 불편하다고 하고 답을 계산한 후, 2명이 불편했을 때 스트레스를 가장 크게 줄이는 top 2를 뽑아서 끝에 배치하면 됩니다.

홀수밖에 없을때

비슷하게 하는데, 홀수니까 한 행에서는 한 방만 남게 됩니다. 여기서부터 남은 방을 다른 그룹에 배정해 주면, 홀수 두개가 서로 맞물리는 식으로 배치됩니다. 이 전략을 사용하면, 중간에 있는 그룹은 4명이 불편하고, 끝에 있는 그룹은 2명이 불편합니다. 추가로, 각 그룹에서 두 집과 맞닿는 사람은 2배로 더 불편합니다. 모든 그룹에서 두 집과 맞닿는 사람이 정확히 한 명 존재하니, 가장 스트레스가 낮은 사람들을 골라 거기에 배정합니다. 그러면 그 사람들의 스트레스 합 + (짝수일 때의 최솟값) 이 답이 됩니다.

일반 케이스

대부분의 경우 모든 홀수 그룹을 홀수끼리 맞물리게 하는 것이 최적입니다.

이 경우, 어쨌든 홀수 그룹에서 가장 스트레스가 낮은 사람들은 두배로 불편하게 됩니다. 이 합을 미리 구해두면, 홀수 그룹이랑 짝수 그룹은 "거의" 똑같지만, 한 가지 차이점은 홀수 그룹은 서로 붙어 있어야 한다는 것입니다. 그래서 양 끝에 있는 방에 홀수 그룹을 배정하면, 그 옆에도 홀수 그룹이 와 줘야 합니다. 이건 세 가지 케이스가 있습니다.

• 홀수 그룹이 4개 이상: 양 끝에 홀수 그룹이 들어가도 그 옆에 홀수 그룹을 항상 붙여 줄 수 있습니다. 그러니까 다 짝수 그룹이라고 생각하고 풀어도 됩니다.
• 홀수 그룹이 0개: 애초에 다 짝수 그룹입니다.
• 홀수 그룹이 2개: 위 가정 하에 양 끝에 홀수 그룹이 둘 다 들어갈 수는 없습니다. 만약 스트레스를 가장 크게 줄이는 top 2가 둘다 홀수인데 $n > 2$ 라면, 그 케이스는 실현이 불가능하니, 예외적으로 최소 홀수 그룹과 최소 짝수 그룹을 골라서 배정해 주도록 합시다.

이를 구현하게 되면 WA를 받습니다. 여기서 위 가정이 깨지는 특수한 경우 가 발견되는데, 홀수 그룹이 2개일 때 양 끝에 홀수 그룹을 억지로라도 끼워넣고 싶은 경우입니다. 이 케이스에서는 짝수 그룹을 모두 서로 맞물리게 하는 한이 있어도 홀수 그룹을 양 끝에 배정할 수 있습니다. $2$명을 위해 $2n-4$ 명의 스트레스를 늘리는 꼴이지만, 짝수 그룹에서는 모두 스트레스가 1인데, 홀수 그룹에서는 모두 스트레스가 $10^7$ 이라고 생각하면 충분히 가능한 경우임을 알 수 있습니다.

사실 알고리즘의 증명은 해 보지 않았지만, 아마 어떤 전략에서도 이것보다 잘 할 수 없음을 보이면 될 것 같습니다.

5. 차이

두 변수의 차이를 유추할 수 있지만 정하는 것이 불가능하다면, 지금까지 들어온 입력에 모순이 있다는 것입니다. 예를 들어, $X_1 - X_2 = 1, X_2 - X_3 = 1, X_3 - X_1 = 1$ 이면, 연립했을 때 $0 = 3$ 이라는 결과가 나옵니다. 이런 경우가 없다고 가정합시다.

$X_i - X_j = d$ 라는 정보가 들어오면, $X_i = X_j + d$, $X_j = X_i - d$ 입니다. 이는 $j$ 에서 $i$ 로 가중치 $d$ 의 간선, $i$ 에서 $j$ 로 가중치 $-d$ 의 간선이 추가되었다고 볼 수 있습니다. 두 정점 간에 경로가 있으면 차이가 정해지고, 아니면 NC입니다. 고로 Union-find 등으로 NC의 케이스를 처리할 수 있습니다.

아니면 차이를 구해야 합니다. Union-find의 루트 정점 $r$ 을 기준으로 하여, 각 정점 $v$ 에 대해서 $X_v - X_r$ 값을 추가적으로 관리하여 주면, $X_r$ 을 기준으로 해서 같은 컴포넌트에 있는 모든 정점 쌍의 차이를 계산할 수 있습니다. 이 값은, Small-to-large 등을 사용하여 explicit하게 관리하거나, $X_v - X_{parent_v}$ 값을 UF에서 관리한 후 Path compression마다 잘 처리하는 식으로 관리할 수도 있습니다. 후자로 하면 코드 두 세줄만 더 넣으면 되는데 대신 좀 헷갈립니다. 둘 다 복잡도는 $O(n \log n)$ 정도입니다.

차이를 정할 수 있으면 모순이 있는지는 쉽게 판별할 수 있습니다. 모순이 있다면, 어떠한 컴포넌트 $C$ 에서 $i$ 에서 $i$ 로 가며 가중치 합이 0이 아닌 사이클이 있다는 뜻입니다. $C$ 에 있는 모든 원소에서는 이러한 사이클에 도달할 수 있고, 고로 $C$ 의 모든 원소에 대해서 모순이 있습니다. 이는 앞으로 $C$ 에 합쳐질 원소에 대해서도 동일하게 적용됩니다. 이는 UF에서 "해당 컴포넌트에 모순이 있는지" 를 저장하는 식으로 관리할 수 있습니다.