티스토리 뷰
1. 비트문자열
특정 규칙으로 만들어지는 길이 $2^i$인 이진문자열 $S_i$가 있다. 구간 $[s, e]$가 있을 때, $S_i$의 $s$ 번째 문자부터 $e$ 번째 문자까지 문자 중에서 1의 개수를 구하는 문제다. 단, 하나의 입력 파일에 최대 20만 개의 테스트 케이스가 들어올 수 있어서 상당히 빠른 시간 안에 문제를 해결해야 한다.
문제 설명에 적힌 규칙과 다른 방식으로 $S_i$를 설명할 수 있다. $S_0$는 "0"이며, $1$ 이상인 $i$에 대해 $S_i$는 $S_{i-1}$에서 0/1을 뒤집은 것과 $S_{i-1}$을 이어 붙인 문자열이 된다. 즉, $S_1$은 "10"이며, $S_2$는 "10"에서 0/1을 뒤집은 "01"에 "10"을 이어 붙인 "0110"이 된다. $S_3$은 "0110"에서 0/1을 뒤집은 "1001"에 "0110"을 이어붙인 "10010110"이 된다.
$S_i$는 여러 특징이 있는데, 이 문제를 풀면서 필요한 특징은 두 가지이다. 하나는 $k > 0$인 정수 $k$에 대해 문자열 $S_i$의 $2k$ 번째 문자와 $2k-1$ 번째 문자는 항상 다르다는 특징이다. 이 특징을 이용하면 $s$ 번째 문자와 $e$ 번째 문자만 알면, 구간 $[s, e]$에 있는 1의 개수를 알 수 있다.
그러면 어떤 $x$에 대해, $S_i$에서 $x$ 번째 문자를 빠른 시간 안에 구하면 이 문제를 해결할 수 있다. 어떤 $x$에 대해 $S_i$의 $x$ 번째 문자와 $S_{i+1}$의 $x$ 번째 문자는 항상 다르다는 점을 이용하면 된다. 그러면 $i > 60$인 경우, $S_{60}$의 $x$ 번째 문자를 구하고, $i$의 홀짝성을 이용해서 $S_i$의 $x$ 번째 문자도 구할 수 있다.
말로 설명해보니 방법이 좀 복잡해 보이는데, 실제로는 간단하다. 아래 코드를 참고하자.
2. 정수 놀이
쿼리가 $Q$ 개 주어진다. 각 쿼리에 대해 양의 정수 $A$에 최소 몇 번의 연산을 적용하여 양의 정수 $B$를 만들 수 있는지를 구해야 한다. 적용할 수 있는 연산은 1) 정수에 1을 더한다, 2) 정수에 1을 뺀다, 3) 정수를 제곱한다, 4) 정수가 제곱 수라면 제곱근을 한다. 단, 연산 이후에도 양의 정수가 되는 경우에만 연산을 할 수 있다.
문제에서 주어진 네 종류의 연산은 서로 대칭이다. 따라서 문제를 양의 정수 $A$와 $B$가 주어졌을 때, 두 정수에 최소 횟수의 연산을 적용하여 같은 값으로 만드는 문제로 바꿀 수 있다.
$A$와 $B$ 중 큰 값의 수준을 하나씩 줄여가면서 답을 갱신해줄 것이다. 여기서 어떤 수의 수준을 줄인다는 것은 그 수를 가까운 제곱수로 만든 뒤, 제곱근 연산을 한다는 말이다. 일반성을 잃지 않고 $A \ge B$라고 하자. 현재 단계에서 가능한 답의 후보는 $|A-B|$이다. $A$를 가까운 제곱수로 만든 뒤, 제곱근을 구하면 $C$가 된다고 하자. 이때, 필요한 연산 횟수는 $|C^2-A|+1$이다. 그 이후 단계에서 가능한 답의 후보는 $|C^2-A|+1+|C-B|$가 된다. 이런 식으로 한 단계마다 큰 수의 수준을 하나씩 줄여가면서 답의 후보를 구하면, 그 후보들 중에 문제의 정답이 있다.
3. 물풍선 애널리스트
무한한 2차원 격자판의 일부 칸에 물풍선이 놓여있다. 물풍선 $i$의 위치는 $(x_i, y_i)$이며 세기는 $p_i$이다. 물풍선은 십자 모양으로 터진다. $t_i$는 물풍선 $i$를 터트렸을 때, 연쇄 작용을 통해 모든 물풍선이 터지는지 여부를 나타낸다. $p_i$에 대한 정보를 잃어버린 상황에서 $t_i$의 정보를 가지고 $p_i$ 값들을 복원하는 문제다. 만약 가능한 답이 여러 가지인 경우, 그중 아무거나 출력한다.
만약 $t_i = 1$이라면, 즉, 물풍선 $i$를 터트렸을 때, 연쇄 작용을 통해 모든 물풍선이 터진다면, $p_i$ 값은 크면 클수록 좋다. 만약 $t_i = 0$이라면, 물풍선 $i$를 터트렸을 때 $t_j = 1$인 물풍선 $j$를 터트리면 안 된다. 그런 물풍선을 터트리지 않는 조건에서 $p_i$가 크면 클수록 좋다. 이렇게 $p_i$들 중 가장 큰 값들을 구하면 답이 된다. $t_i$ 값을 만족하는 $p_i$ 조합이 항상 존재하도록 입력이 주어지기 때문에, 이렇게 구한 $p_i$가 $t_i$ 조건을 만족하는지 따로 체크하지 않아도 된다. 한 가지 예외 처리가 필요하다. 만약 모든 $t_i$가 $0$이라면, $p_i$는 모두 1이 되어야 한다.
4. 멘토링 시스템
$N$ 명의 멘토가 있고, $N$ 명의 멘티가 있다. 멘토링이 가능한 멘토와 멘티 쌍들이 주어졌을 때, 1:1 매칭을 해줄 수 있으며, 그 방법이 유일한지 구하는 문제다.
이 문제는 이분그래프에서 완벽 매칭의 유일성을 묻는 문제다. 만약, Hopcroft-Karp 등의 방법을 통해서 최대 매칭을 구했다고 하자. 만약 최대 매칭이 완전 매칭이 아니라면, 즉, 매칭 수가 $N$이 아니라면 답은 "NO"다. 임의의 완전 매칭을 구했을 때, 이 완전 매칭이 유일한지 검사가 추가적으로 필요하다.
우선, 가장 먼저 떠오를 수 있는 방법으로는 간선의 순서를 랜덤하게 섞어서 여러 번 매칭을 구해서 구한 매칭이 모두 같은지 확인하는 방법이다. 매칭 알고리즘을 여러 번 돌리기 때문에 시간 초과가 날 수 있으며, 확률적으로 올바르지 않은 답을 구하게 된다. 이 방법으로는 꽤 낮은 확률로 이 문제를 풀 수 있다.
다른 방법으로, 이분그래프를 방향성 그래프로 만든 뒤, 임의로 구한 완전 매칭에 속한 간선의 방향을 뒤집는다. 이렇게 만들어진 방향성 그래프에서 사이클이 있는지 확인한다. 만약, 사이클이 있다면 다른 매칭도 존재할 수 있다. 싸이클이 존재하지 않는다면, 완전 매칭은 유일하다. 사이클의 존재 여부 확인은 위상 정렬을 통해 $O(V+E)$ 시간복잡도로 해결할 수 있다.
위의 방법은 이분 매칭으로 완전 매칭을 구해야 하므로, 이분 매칭 구현이 아주 빠르지 않은 이상 시간초과가 나올 수 있다. Hopcroft-Karp 알고리즘이 꽤나 빠른 이분매칭 알고리즘인데, $O(E \sqrt{V})$ 시간복잡도를 가진다. Hopcroft-Karp 알고리즘이 최악의 시간을 가지도록 하는 입력 데이터가 잘 알려져 있지 않아, 이 문제에서는 Hopcroft-Karp 알고리즘 1번 돌리는 것으로 시간초과가 나오지 않는다.
사실 이 문제는 완전 매칭이 가능한지 확인하고, 가능하다면 그 방법이 유일한지만 구하는 문제이므로 일반적인 이분매칭 알고리즘 없이 $O(V+E)$ 시간에 해결할 수 있다. 증명을 생략하고 방법만 설명하겠다. 주어진 이분그래프에서 차수가 1인 정점을 살펴보자. 차수가 1인 정점에 대해서 유일한 간선으로 연결된 정점과 매칭 해주는 과정을 반복한다. 만약, 원래 그래프에서 유일한 완전 매칭이 존재한다면 이 방법으로 유일한 완전 매칭을 찾을 수 있다.
'해법' 카테고리의 다른 글
Nexon Youth Programming Challenge(NYPC) 2022 본선 풀이 (0) | 2022.10.31 |
---|---|
Nexon Youth Programming Challenge(NYPC) 2022 Round 2-A 풀이 (0) | 2022.08.29 |
Google Code Jam 2022 Round 2 풀이 및 후기 (0) | 2022.05.16 |
Nexon Youth Programming Challenge(NYPC) 2021 예선 풀이 (3) | 2021.08.28 |
Nexon Youth Programming Challenge(NYPC) 2020 예선 풀이 (9) | 2020.09.06 |
- Total
- Today
- Yesterday
- IOI2011
- IOI2014
- IOI2013
- TRIE
- HackerRank
- z-trening
- BOI 2001
- Algorithm
- Splay Tree
- BOI 2009
- Parametric Search
- Knuth Optimization
- BOI
- IOI2012
- Segment tree
- Dijkstra
- idea
- Divide & Conquer
- moore
- optimization
- USACO
- majority
- Tree
- Boyer-Moore Majority Vote Algorithm
- Dynamic Pramming
- Greedy Method
- ioi
- vote
- Boyer
- dynamic programming
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |