Educational Codeforces Round 113 (Rated for Div. 2)

요즘 컨디션이 좋다. 실력이 늘은건지 웰노운이 나온건지 잘 모르겠지만 암튼 계속 올라서 좋긴 하다.

 

A. Balanced Substring

a의 개수와 b의 개수가 같은 substring을 찾는 문제이다. 문자열 "ab" 또는 "ba"는 항상 조건에 맞기 때문에, 그냥 주어진 문자열에서 "ab" 또는 "ba"가 있는지만 판별하면 된다.

놀랍게도 완탐을 돌리다 TLE 맞고 틀렸다. n이 작길래 무지성으로 냈는데 다시 찬찬히 계산해보니 1e9가 넘더라

 

B. Chess Tournament

참여자들을 정점으로 하는 그래프로 모델링하면 완전 그래프가 만들어진다. 1번 타입의 참가자는 절대 지면 안된다. 따라서 1번 타입 참가자에 연결된 간선들을 모두 지운다. 이제 남은 간선들을 가지고 2번 타입 참가자들을 연결해보자. 2번 타입 참가자들은 최소 1번만 이기면 된다. 즉, outdegree가 1 이상이 되도록 만들어야 한다. 완전 그래프기 때문에, 항상 2번 타입 참가자들을 잇는 단순 사이클이 만들어 질 수 있다. 아래 그림은 세 번째 테스트케이스의 풀이이다.

단순 사이클이 만들어지지 않는 경우는, 2번 타입 참가자가 2명 이하인 경우이다. 한편 2번 타입 참가자가 0명이라면 모든 참가자들이 서로 비기기만 하면 된다.(첫 번째 테스트케이스) 따라서 2번 타입 참가자가 1명이나 2명인 경우만 NO이고 나머지 모든 경우는 YES이다. YES라면, 앞에서 설명한 대로 단순 사이클을 만들고 그 사이클에 포함되는 간선을 제외한 모든 간선을 비기는 경우로 지정하면 된다.

 

C. Jury Meeting

nice하지 않은 경우를 생각해보자. 문제에 제시된 예시들을 잘 관찰해보면 다음과 같은 규칙을 찾을 수 있다.

• 수열 $a$에서 가장 큰 원소를 $a_k$라고 하자. $a_k$와 값이 같은 원소가 더 있다면, 항상 nice하다.
• 값이 $a_k - 1$인 원소가 하나도 없다면 항상 nice하지 않다.
• $a_k$ 이후에 값이 $a_k - 1$인 원소가 하나도 없다면 항상 nice하지 않다. 즉, $p$에 따라 $a$를 재배열했을 때, 구간 (k, n] 안의 모든 $i$에 대하여 $a_i < a_k - 1$이면 항상 nice하지 않다.

첫 번째 경우는 항상 nice하므로 $n!$이 답이다. 두 번째 경우는 항상 nice하지 않으므로 0이 답이다. 세 번째 경우를 잘 계산해야 하는데, 값이 $a_k - 2$보다 작은 원소가 $l$개라고 하면 다음과 같이 계산할 수 있다. $$ n! - \sum_{i=0}^l (n-i-1)! {k \choose i} i! $$ 팩토리얼은 오프라인으로 미리 계산해 둘 수 있고, combination은 페르마의 소정리와 분할정복을 통해 O(log n)에 계산할 수 있다.

역시 조합론 문제는 어렵다. 예제가 굉장히 잘 나와있어서 겨우 규칙을 관찰해 낼 수 있었다.

 

D. Inconvenient Pairs

불편한 쌍이 만들어지는 조건은 다음과 같다.

• 교차로 위에 있는 사람은 항상 불편한 쌍을 만들 수 없다.
• 같은 열에 있는 가로 도로에 있으면서 서로 다른 도로에 있는 두 사람은 항상 불편한 쌍이다.
• 같은 행에 있는 세로 도로에 있으면서 서로 다른 도로에 있는 두 사람은 항상 불편한 쌍이다.

먼저, 세로 도로와 사람들을 x좌표에 대하여 정렬한다. 이를 스위핑하면 같은 열에 있는 사람들을 골라낼 수 있다. 예를 들어 두 번째 테스트 케이스에서 1, 6, 7번 사람이 한 그룹, 8번 사람이 다른 한 그룹으로 분류된다. 이 골라낸 그룹을 이번엔 y좌표로 정렬한다. 그러면 한 그룹 내에서 같은 가로 도로에 있는 사람의 수를 찾아낼 수 있다. 현재 그룹의 크기를 $n$이고 같은 도로에 있는 사람이 $k$명이면 $\frac{\sum k(n-k)}{2}$이 불편한 쌍의 개수다.

같은 방식으로 y좌표에 대하여 한 번 더 하면 된다.