3월 3, 4주차 PS 정리

7문제, 난이도 순. 온라인 개강이라 시간이 널널할줄 알았는데 생각보다 과제가 많아서 PS를 못 돌고 있다.

 

BOJ 11405 책 구매하기

난이도 : Platinum 4

MCMF가 무엇이고 어떻게 구하는지 공부할 때 푸는 기본 구현 문제. 플로우 같은 고급 알고리즘을 너무 모르는 것 같아서 MCMF를 공부하고 구현을 (적당히 팀노트를 베껴 가며) 해봤다. 아직 응용해서 MCMF 문제를 모델링해서 풀기에는 갈길이 먼것 같다.

팀노트에 넣어놓은 MCMF가 잘 도는지 확인하는 문제라고 할 수 있겠다.

 

 

Atcoder Beginner Contest 160F, Distributing Integers

Atcoder 난이도 1962

대략적으로 문제를 설명하자면, 정점 1부터 $N$까지로 구성된 트리에서, $x$ 번을 트리의 루트로 잡고 트리를 펼쳤을 때, '트리의 위상적 정렬성' 을 해치지 않는 채로 ($a$ 가 $b$ 의 조상일 때 $a$에 더 작은 수를 쓴다) $1$ 부터 $N$ 까지 숫자를 써넣을 수 있는 경우의 수를 찾는 문제. 

크게 두 가지 스텝으로 나누어 풀 수 있다. 첫번째는 1번을 루트로 잡았을 때 값을 계산하는 방법이고, 두번째는 이를 이용하여 Re-rooting을 하는 방법을 알아야 한다.

1. 첫 번째 문제는, 다음과 같이 해결할 수 있다. 트리에서 어떤 노드 $a$ 가 $b, c, d$ 를 서브트리에 가지고 있다고 하자. 즉, $a, b, c, d$로 구성된 서브트리의 루트가 $a$인 것이다. 이때, 이러한 sequence의 개수를 세는 대신, '확률' 처럼 생각해 보기로 하자.

임의로 아무렇게나 Permutation을 하나 만들었을 때, "이 서브트리의 루트" 를 맞춰주기 위해서는 $a$ 가 $\{a, b, c, d\}$ 중 가장 작은 수를 가져야 한다. 이것을 만족할 확률은 $\frac{1}{4}$ 임은 쉽게 생각할 수 있다. 그런데, 이 서브트리 안으로 들어가 다시 서브트리를 생각해 보면, $a, b, c, d$ 에 부여된 숫자들이 이미 정해져 있고, $a$ 가 가장 먼저 나온다는 사실이 정해져 있더라도 $b, c, d$의 서로간의 선후관계는 독립적임을 알 수 있다. 따라서, 답은 

$$\frac{n!}{s_1 s_2 \dots s_n}$$

$s_1, s_2 \dots$ 는 $i$를 루트로 하는 서브트리의 크기.

2. Re-rooting을 하는 과정은 설명하기 까다롭지만 이렇게 생각해 보자. 모든 간선의 '방향성' 을 동시에 바꾸려면 10만개의 간선을 업데이트 해야 할 수도 있지만, 사실 간선의 '방향' 이 바뀌는 것은 몇개 없다.

'지금의 루트 노드' 와 인접한 노드를 새로운 루트로 한다고 하면, 즉 루트 $r$ 의 인접 노드 $k$ 를 새 루트로 한다면, $(r, k)$ 간선만 방향을 바꿔 주면 된다. 설명은 뭔가 약간 이상한데 코드는 간단한 편.

https://atcoder.jp/contests/abc160/submissions/11298787

 

 

BOJ 18086, ICPC NWERC 2019 G, Gnoll Hypothesis

난이도 : Platinum 4

침착하게 확률 계산을 잘 하면 된다. 500개밖에 없어서 $O(n^2)$ 도 넉넉하게 통과할 수 있다. 

구체적으로는, 다음과 같은 확률을 계산한다.

$P[i]$ = $i$개의 연속한 자리가 골라지지 않을 확률. 즉, 나를 기준으로 내 이전 $i$ 개 만큼이 내 자리에 빨려들어갈 확률.

이 값이 있으면, 이전 몇개의 기존 확률값들을 곱해서 기댓값을 계산하는 방식으로 쉽게 구할 수 있다.

 

 

BOJ 17634, Asia-Pacific Informatics Olympiad 2019 1(APIO) - Strange Device

난이도 : Platinum 3

생각보다 쉬운 문제. 기본적으로, 우리가 원하는 문제는 $t = uB + v$ 로 잡으면 $(x, y) = (u(B+1)+v \mod A, v)$ 가 된다는 점에 착안해 보자. 이제, 이 식이 어떤 주기를 갖는지 생각해 보면 된다. 앞부분은 주기가 $\frac{A}{\gcd(A, B+1)}$ 임을 증명하는 것이 어렵지 않고, 뒷부분의 주기가 $B$임을 이용하여, 가능한 모든 $t \in [l_i, r_i]$ 에 대해 모듈러 $\frac{AB}{\gcd(A, B+1)}$ 의 값이 서로 다른 것이 몇 개 있는지 세는 문제이다.

사소한 구현 실수 외에는 딱히 걱정할 부분이 없고, Union of interval 은 정렬해놓고 앞으로 나가면서 찾으면 $O(n \log n)$ 에 찾을 수 있음이 잘 알려져 있으므로 이대로 하면 된다. 64-bit integer 범위를 넘어설 수도 있겠다는 우려가 드는 계산이 있는데, 이 문제에서 처음으로 Codeforces에 128 bit integer를 지원하지 않는다는 사실을 알게 되었다.

수정 : 이 부분을 처음 썼던 3월 20일경에는 지원하지 않았으나 그새 64비트 머신으로 채점기 일부가 업데이트되고 64비트 컴파일러를 깔아서 이제 코드포스도 128비트를 지원한다. 2020년에서야 64비트 컴파일러를 갖다 놨다니;;;

 

 

BOJ 10167, KOI 2014 중등부 4번, 금광

난이도 : Diamond 5

유명한 '금광' 문제를 이제서야 풀어봤다. 언젠가 따로 포스팅할 문제니까 간단하게만 적기로 하자.

문제 요점 : 2D 좌표에 +와 -값들이 적당히 마구 주어져 있을 때, 빠르게 '최대 직사각형' 을 찾을 수 있는가.

좌표압축 + '구간 최댓값 세그 트리' + 스위핑.

좌표압축이야 간단하니까 넘어가고, '구간 최대 부분합 세그 트리' 라는 것은 분할 정복을 이용하여 구간 $(a, b)$ 의 최대 부분합을 계산하는 세그먼트 트리를 만드는 과정이다. 대략적으로는 $(a, b)$ 의 중간값을 $c$ 라고 할 때, $(a, c)$ 와 $(c+1, b)$ 로 나눈 다음 다음 네가지 값을 계산해야 한다.

- '왼쪽 끝' 에서부터 시작해서 최대 부분합

- '오른쪽 끝' 에서부터 시작해서 최대 부분합

- 그 구간의 최대 부분합 (반을 잘라서 분할정복으로 업데이트)

- 그 구간의 합

이 네가지를 이용해서 parent node (나보다 두배 길이를 갖는) 의 최대 부분합을 또 업데이트 하는 방식으로 간다.

구간 최댓값 세그트리를 이용한 다음에는, 이를 어떤 순서로 업데이트하냐가 중요하다. 스위핑을 이용해서 복잡도 $n^2 \log n$ 에 전체 문제를 풀도록 업데이트할 수 있다.

 

 

BOJ 17975, ICPC Seoul Regional 2019 H, Strike Zone

난이도 : Diamond 5

위 문제의 약화 버전. 문제 상황을 잘 해석하면, $+c$ 와 $-d$ 만 있는 금광이다. 

 

 

BOJ 10846, Asia-Pacific Informatics Olympiad 2015 2 (APIO) - Jakarta Skyscraper

BOJ 번역명 "자카르타의 마천루"

난이도 : Diamond 3

https://gratus907.com/100