$$\newcommand{\Z}{\mathbb{Z}} \newcommand{\R}{\mathbb{R}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\N}{\mathbb{N}}\newcommand{\C}{\mathbb{C}} \newcommand{\oiv}[1]{\left] #1 \right[} \newcommand{\civ}[1]{\left[ #1 \right]} \newcommand{\ad}[1]{\text{ad}(#1)} \newcommand{\acc}[1]{\text{acc}(#1)} \newcommand{\Setcond}[2]{ \left\{\, #1 \mid #2 \, \right\}} \newcommand{\Set}[1]{ \left\{ #1 \right\}} \newcommand{\abs}[1]{ \left\lvert #1 \right\rvert}\newcommand{\norm}[1]{ \left\| #1 \right\|}\newcommand{\prt}{\mathcal{P}}\newcommand{\st}{\text{ such that }}\newcommand{\for}{\text{ for }} \newcommand{\cl}[1]{\text{cl}(#1)}\newcommand{\oiv}[1]{\left] #1 \right[}\newcommand{\interior}[1]{\text{int}(#1)}$$

3월 3, 4주차 PS 정리::::Gratus' Blog

3월 3, 4주차 PS 정리

알고리즘 문제풀이/PS_Weekly 2020. 3. 31. 01:57

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

 

 

'알고리즘 문제풀이 > PS_Weekly' 카테고리의 다른 글

6월 ~ 7월 1주차 PS 정리  (0) 2020.07.04
4월 3, 4주차 PS 정리  (0) 2020.05.01
4월 1, 2주차 PS 정리  (0) 2020.04.17
3월 3, 4주차 PS 정리  (0) 2020.03.31
3월 2주차 PS 정리  (0) 2020.03.09
3월 1주차 PS 정리  (0) 2020.03.07


admin