2020 UCPC 예선 대비 개인 연습 (1)

요 근래 UCPC 예선 대비로 개인연습을 진행중이다. 참고로 대회에는 Juney 님과 minfe 님과 함께 나갈 예정이다. 휴학한 나 이외에는 기말고사를 쳐야 하는지라, 일단 개인연습을 돌고 있다.

solved.ac의 기능을 이용하여 난이도가 플래티넘 V ~ 플래티넘 I 범위에 속하는 문제 12개를 골라 셋을 만들고, 한 1주일 정도의 기간 동안 그 중 6개 이상 해결하는걸 목표로 하고 있다. 요지는 대회 시간 안에 풀이를 생각해낼 수 있을만한 문제들을 풀되, 특정 성향의 문제에 편중되지 않게 풀어보자는 것이다.

solved.ac 플래티넘 연습 #01

문제 목록

• A - Counting Friends
• B - 고속도로
• C - 인재야 머쉬맘 잡았어?
• D - Random Number Generator
• E - Kill the Werewolf
• F - #15164번_제보
• G - Vacation Planning
• H - 가장 작은 K
• I - 달콤새콤
• J - Fruit Slicer
• K - A=S
• L - 가로수 (Large)

해결한 문제

A. Counting Friends

어떤 sequence $D = (d_1, d_2, \dots, d_n)$ 이 주어질 때, 실제로 graph의 degree sequence가 될 수 있는지를 판별할 수 있으면 해결할 수 있는 문제이다. 이와 관련해 다음과 같은 (직관적으로 당연히 성립할 것 같은) 수학적인 결과가 있다.

Theorem. $D = (d_1, d_2, \dots, d_n)$, $d_{i-1} \le d_i$가 실제로 graph의 degree sequence가 될 수 있음은 $D' = (d_1', \dots, d_{n-1}')$, $d_i' = \begin{cases} d_i & i < n - d_n \\ d_i - 1 & i \ge n - d_n \end{cases}$ 이 graph의 degree sequence가 될 수 있음과 동치이다.

이 정리를 코드로 $O(n^2)$에 구현하면 문제를 해결할 수 있다. 단, 같은 complexity라도 cost가 비싼 연산을 활용하면 시간 초과를 받을 수 있으므로 (내 경우에는 몇 번 받았다) 효율적으로 구현해야한다.

E. Kill the Werewolf

Werewolf가 이길 수 있을 필요-충분조건은 다른 참가자들의 전략에 관계 없이 자신과 같은 득표를 받는 player를 만들 수 있는 것이다. 반대로 Werewolf가 아닌 참가자들이 이길 필요-충분조건은 다음과 같게 된다:

• Werewolf에 투표할 수 있는 (Werewolf가 아닌) 참가자들이 모두 Werewolf에 투표하고,
• 남은 Werewolf가 아닌 참가자들이 적당히 잘 투표하여
  • Werewolf가 "투표할 수 있는" 참가자들의 득표는 (Werewolf의 득표) - 2 이하로,
  • 나머지 참가자들의 득표는 (Werewolf의 득표) - 1 이하로 할 수 있다.

이를 판별하기 위해서는 최대 유량 알고리즘을 사용하면 된다. 구체적으로는, 참가자 $i$에 대해 자신이 투표하는 것을 나타내는 노드 $u_i$와 투표 받는 것을 나타내는 노드 $v_i$를 정의하고, 다음과 같이 그래프를 만들어 주면 된다.

• Werewolf가 아닌 각 참가자 $i$에 대해 source와 $u_i$를 용량 1인 간선으로 잇는다
• Werewolf에 투표할 수 없고, Werewolf가 아닌 각 참가자 $i$에 대해 $u_i$와 $v_{a_i}$, $v_{b_i}$ 각각을 용량 1인 간선으로 잇는다
• Werewolf에 의해 투표 받을 수 있는 각 참가자 $i$에 대해 $v_i$와 sink를 용량이 (Werewolf의 득표) - 2인 간선으로 잇는다
• 나머지 Werewolf가 아닌 각 참가자 $i$에 대해 $v_i$와 sink를 (Werewolf의 득표) - 1인 간선으로 잇는다

이러한 그래프에서 최대 유량이 (참가자의 수) - (Werewolf의 득표)가 되면 Werewolf가 아닌 참가자들이 이기고, 아니면 Werewolf가 이긴다.

F. #15164번_제보

문제에서 요구하는 대로 Manacher 알고리즘을 구현하면 된다. 원래 문자열에서 각 문자 사이에 #이나 .과 같이 사용되지 않는 문자를 삽입해서 새로운 문자열을 만들고 Manacher 알고리즘을 적용하면 더 편하게 해결할 수 있다. 자세한 구현은 이 블로그에 잘 나와있다.

G. Vacation Planning

문제가 다소 복잡해서 요약하도록 하겠다.

$n$개의 도시가 있고, 그 중 $k$개의 허브 도시가 있다. 두 도시를 잇는 항공편 $m$개와 그에 대한 cost가 주어지는데, 하나의 항공편이 잇는 두 도시 중 최소 하나는 허브 도시이다. 두 도시를 이동하는데 드는 최소 cost를 묻는 질의가 $Q$개 주어질 때 질의에 효율적으로 답하는 문제이다. ($n, m \le 20,000$, $k \le 200$, $q \le 50,000$)

먼저, 각 쌍의 허브 도시 사이를 이동하는데 필요한 최소 cost를 전처리하자. 이는 그래프를 만들고, 다음 두 종류에 대응되는 간선을 추가한 후, 플로이드-워셜 알고리즘을 사용하면 $O(k^3)$ 시간에 계산할 수 있다.

• (허브 도시) - (허브 도시)를 잇는 항공편
• (허브 도시) - (허브 도시가 아닌 도시) - (허브 도시) 형태의 2개의 항공편을 사용하는 경로

이후, 각 도시에 대해

• 각 허브 도시로 가는데 필요한 최소 cost와
• 각 허브 도시에서 오는데 필요한 최소 cost를

전처리하자. 이는 앞에서 전처리 한 정보와 각 도시에 인접한 허브 도시들을 고려해주면 되며, $O((n+m)k)$ 시간에 해결할 수 있다.

마지막으로, 각 질의가 주어지면 두 도시 사이의 최단 경로는 무조건 허브 도시를 거친다는 점을 이용하여 $O(k)$ 시간에 각 질의를 해결해줄 수 있다. 결국 총 시간 복잡도 $O(k^3 + (n+m+q)k)$ 로 문제를 해결할 수 있다.

H. 가장 작은 K

아직 문제를 어떻게 해결하는지는 모르겠고, OEIS를 사용하면 된다. 개꿀

I. 달콤새콤

기댓값의 선형성에 의해 각 선수가 낼 승점의 기댓값을 구해 더해주면 된다. 그리고 각 선수가 낼 승점의 기댓값은 달콤 경기에서의 승점의 기댓값과 새콤 경기에서의 승점의 기댓값을 평균내주면 된다.

초콜릿 나라와 쿠키 나라 각각에 대해 달콤함 값과 새콤함 값에 대해 prefix sum을 전처리 해놓으면, 각 선수가 낼 승점의 기댓값을 $O(1)$에 계산할 수 있다.

비슷하게 앞에서 전처리한 것을 활용하면 물약이 낼 승점의 기댓값을 $O(R - L)$에 전처리 할 수 있다. 어느 선수의 승점의 기댓값이 물약이 낼 승점의 기댓값보다 작으면, 그 선수에게 물약을 먹여주는 단순한 전략을 활용하면 문제를 해결할 수 있다. 이 과정에서 대소 비교를 위해 답을 출력하기 전에는 각 수를 분수 형태로 관리해야 한다.

Python과 같이 좋은 내장 분수 라이브러리가 있는 언어를 사용하면 좋다.

J. Fruit Slicer

가장 많은 원을 지나가는 직선은 최소 두 개의 원에 접한다는 사실을 이용하면 된다. 두 개의 원에 모두 접하는 직선은 공통 내접선과 공통 외접선을 포함해 최대 4종류가 있는데, 각 쌍의 원을 살펴보며 접선의 직선의 방정식을 계산하고, 이 직선이 몇 개의 원과 만나는지 점과 직선 사이의 거리 공식 을 이용하여 계산해주면 된다.

이 과정에서 실수 오차에 유의해야 하며, 모든 원이 한 점에 있는 경우 또한 주의해야 한다. 총 시간 복잡도는 $O(n^3)$이다.

해결하지 못한 문제

B. 고속도로

$O(n^2)$ dp는 알거 같은데 정해는 잘 모르겠다.

solved.ac 플래티넘 연습 #02

문제 목록

• A - 즉흥 여행
• B - 집으로 가는 길
• C - Parentheses
• D - 메뚜기
• E - Job Postings
• F - Mosaic Mansion
• G - 두더지가 정보섬에 올라온 이유
• H - The League of Sequence Designers
• I - 돌림판 (Large)
• J - Jewel heist
• K - 굿점원
• L - Stoichiometry

해결한 문제

A. 즉흥 여행

$A_i = \sum_j adj _{i,j}$로 정의하고, $D_{i, k}$를 $k$번의 여행 이후 공항 $i$에서 끝날 최대 확률로 정의하자. 다음과 같은 점화식을 얻을 수 있다:
$$
D_{i, k+1} = \max_j D_{j, k} {adj_{j, i} \over A_j}.
$$
이 식을 활용하면 총 $O(N^2K)$ 시간 복잡도에 문제를 해결할 수 있다.

다만, 주의해야 할 점이 있는데, 확률이 굉장히 작아질 수 있으므로 실수 자료형을 그냥 사용하면 안되고, $\log D_{i, k}$ 값을 저장하여 관리해주어야 한다. 이 경우, $\log (0)$ 을 계산하게 되는 경우 문제가 생길 수 있는데, $\log(0)$ 값 대신 실수 자료형의 최소값 (C의 경우 -DBL_MAX) 을 사용해주면 된다.

B. 집으로 가는 길

어린이 노드와 집 노드, 그리고 source와 sink가 있는 플로우 그래프를 생각하자. source와 어린이 노드, 그리고 집 노드와 sink는 용량 1, cost 0인 간선으로 잇고, 어린이 노드와 집 노드를 잇는 간선은 용량은 1, cost는 어린이의 위치와 집의 위치 사이의 거리로 하여 정의하자. 이 그래프에서 Min cost max flow를 구해주면 쉽게 문제를 해결할 수 있다.

D. 메뚜기

$D_{i, j}$를 $(i, j)$ 칸에서 이동해서 방문할 수 있는 칸의 수로 정의하고, 꽃들을 꽃잎의 수 순서로 정렬하여 꽃잎의 수가 많은 칸 부터 먼저 DP 값을 계산해주자.

어느 칸에서 인접한 행/열에 있는 칸 중 문제의 조건에 의해 바로 방문할 수 없는 칸은 최대 3개임을 확인할 수 있다. 따라서, 각 행/열 별로 DP값이 가장 큰 4개의 칸에 대한 정보를 관리해주면 $O(N^2 \log N)$ 시간 복잡도에 문제를 해결할 수 있다. ($\log N$은 처음에 정렬하는 것 때문에 붙는다.)

나는 다음과 같은 구조체를 만들어서 썼다.

bool cmp(const pair<int, int> &p, const pair<int, int> &q){
    auto [x, y] = p;
    auto [a, b] = q;
    if (a != -1 && b != -1){
        if (x == -1 && y == -1) return true;
        if (D[x][y] < D[a][b]) return true;
    }
    return false;
}

struct Four{
    vector<pair<int, int>> I;
    Four(){
        for (int i=0; i<4; i++) I.push_back({-1, -1});
    }
    void update(int i, int j){
        I.push_back({i, j});
        sort(I.begin(), I.end(), cmp);
        reverse(I.begin(), I.end());
        while (I.size() > 4) I.pop_back();
    }
} X[1505], Y[1505];

E. Job Postings

학생들을 valid 하게 assign 하는 방법이 반드시 존재한다고 했으므로, 이 문제 또한 min cost max flow를 통해 모델링 하여 해결할 수 있다.

문제에서는 만족도의 합을 최대화 하라고 했으므로, 반대로 학생들의 12 - (만족도) 값의 합을 최소화 하는 문제로 생각해줄 수 있고, 그러면 모델링은 자명하게 가능하다.

G. 두더지가 정보섬에 올라온 이유

간선을 가중치 역순으로 정렬하고, 간선을 하나 씩 union-find tree 자료 구조에 추가해나가자. $u - v$ 간선을 추가할 때 문제의 답에 ($u$가 속한 포레스트의 정점의 수) × ($v$가 속한 포레스트의 정점의 수) 를 추가해주면 된다.

이 문제와 굉장히 비슷한 아이디어를 사용하는 것 같다.