코드는 Team github에서 압축파일로 받을 수 있습니다.
압축 해제 비밀번호는 imeimi2000입니다.
A. 소가 길을 건너간 이유 5
b[i]를 i번 신호등이 망가졌는가? 를 묻는 boolean 변수,
S[i]를 ([i-K+1, i]의 신호등 중 망가진 것의 개수) = (b[i-K+1] + ... + b[i]) 라고 하면,
문제는 min(S[K-1], ... , S[N-1]) 을 구하는 문제로 바뀝니다.
S[i+1] = S[i] + b[i] - b[i-K]임을 이용하면 O(N)만에 문제를 해결할 수 있습니다.
B. Binary Roads
BFS를 정직하게 개조하면 해결할 수 있는 문제입니다.
정점 v를 (v,0)과 (v,1)의 독립된 2개의 정점으로 보고,
에지 u-v의 값이
0이면 (u,0) -> (v,1) + (v,0) -> (u,1)로,
1이면 (u,1) -> (v,0) + (v,1) -> (u,0)과 같이 2개의 독립된 방향 edge로 해석해서 그래프를 구성합니다.
BFS용 Queue에 정점 (0,0)과 (0,1)을 넣고 BFS를 실행한 뒤 (n-1,0), (n-1,1)의 level 중 작은 것이 답이 됩니다.
C. 369 게임
코딩 실력을 점검할 수 있는 좋은 구현 문제였습니다.
제가 본 가장 직관적인 구현은 다음과 같습니다.
입력 N을 string으로 받은 뒤, 입력 값 이하의 모든 수를 다음과 같은 방법으로 count합니다.
f(int idx, int mod3, bool has369, bool isSmall) 는 다음을 만족하는 N 이하의 정수 개수를 리턴합니다.
- 앞에서부터 idx번째 문자를 본다. 즉, 자유롭게 결정할 수 있는 수가 len(N) - idx 개이다.
- 자릿수 합으로 구한 입력의 modular 3 값이 현재 mod3이다.
- 현재 내가 만들어준 prefix string이 3, 6, 9를 포함하는가? (has369)
- 현재 내가 만들어준 prefix string의 값이 N보다 작은가(strictly less)? (isSmall)
설명이 어렵네요. 예시를 듭시다.
N = 152226이라고 합시다.
152??? 형태의 '369 수' 개수는 다음의 함수로 알 수 있다는 겁니다.
f(3,2,false,false)
3개까지 보았으니 idx = 3
(1+5+2)%3 = 2, mod3 = 2
현재 3, 6, 9는 포함하지 않으므로 has369 = false
아직 N보다 작음이 보장되지 않았으므로 isSmall = false
반면
57???(057???) 형태의 '369 수'는 다음을 호출하면 됩니다.
f(3,0,false,true)
base case의 구현과 재귀함수 호출 구현은 예제로 넘기겠습니다.
이와 같이 top-down DP를 쓰는 경우, 아래와 같이 Memoization을 이용하면
시간 복잡도가 O(탐색 공간의 크기 * dp값 하나 구하는 데 걸리는 시간) 정도로 줄어듭니다.
//맨 처음에 memo[][][][]의 값은 모두 -1로 설정
int &V = memo[idx][mod3][has369][isSmall];
if(V != -1) return V;
//V = ....
D. Out of Sorts
적절한 관찰이 필요한 문제였습니다.
예제를 가지고 놀다 보면 숫자들이 오른쪽으로 이동하는 속도는 엄청 빠르지만, 왼쪽으로 이동하는 속도가 매우 느리다는 것을 알 수 있습니다.
실제로 문제의 pseudocode를 따라가면 원소들이 왼쪽으로 움직일 수 있는 건 한 턴에 최대 1칸입니다. 따라서 \(i\)번째 원소의 정렬 후 위치를 \(p_i\)라고 하면 최소한 \(\max (i - p_{i})\)번은 움직여야 함을 알 수 있습니다.
그리고 "왼쪽 이동의 의무"가 있는 원소들 ( \(p_i < \) 현재 위치 ) 은 코드에 따라 무조건 1번은 왼쪽으로 움직이게 되므로 \(\max (i - p_{i})\)는 한 턴마다 1씩은 감소합니다.
따라서 \(\max (i - p_{i})\)가 답이 됩니다.
이 증명은 엄밀하지 않습니다. 엄밀한 증명은 대회 풀이 를 참조합시다.
E. 초고속철도
의외로 이 문제는 DP로 풀립니다.
사실 DP 말고는 아무것도 답이 안 나오니까 당연하다 싶기도 하지만... 그래도 이 문제를 DP로 맞는 건 쉬운 일이 아닙니다.
식을 써놓고 해설하는 편이 좋겠습니다.
N개의 (1차원 구간으로 표현되는) 로봇의 탐지 영역을 endpoint(오른쪽 끝점) 순으로 정렬합니다.
D[i]를 구간 1에서 i까지 조건을 만족하게 장치를 설치하는 경우의 수라고 두면
D[i] = D[i-1] + D[k].
여기서 k는 구간 i와 disjoint한 (=겹치지 않는) 구간의 index 중 k < i를 만족하는 최댓값입니다.
증명을 쓰자면
1. 구간 i가 아싸라서 자기보다 왼쪽에 겹치는 구간이 없는 경우
이 경우는 i에 장치가 설치되건 말건 상관이 없습니다. 따라서 D[i] = 2D[i-1]이고, k = i-1일 테니 성립.
2. 구간 i와 겹치는 구간이 있는 경우
구간 i와 k+1, k+2, ... , i-1을 한 덩어리로 놓고 생각합시다. 그럼 이 덩어리를 책임질 장치 하나가 필요하겠죠.
- 장치가 구간 i에 설치된 경우
D[i-1]입니다. i에 장치가 있으니까 [k+1, i-1] 번 구간들은 i와의 겹침은 생각할 필요가 없고, 자기들끼리의 겹침만 잘 해소하면 되니까요.
- 장치가 구간 i에 설치되지 않은 경우
이 때 답은 D[k]입니다.
임의의 겹치는 두 구간 사이에는 장치가 하나 있어야 하므로 [k+1 ... i-1]번 구간은 무조건 장치를 부착하는 것으로 자동결정되기 때문입니다.
그리고 k번 이하의 구간들은
- i와는 겹치지 않고
- [k+1, i-1]번에는 장치가 있으니 신경 끄고 자기끼리 장치 붙이면 됩니다.
k를 찾아주는 과정은 각 i에 대해 upper_bound등을 사용하면 O(lg n)만에 수행할 수 있으므로 전체 복잡도는 O(nlgn)입니다.
아 이거 왜 볼드가 안 풀리지
F. Closing the Farm (Gold)
이 문제는 Disjoint - set을 모른다면 쉽게 풀 수 없습니다.
문제는 그래프에서 정점이 하나씩 제거될 때 남은 그래프의 연결성 여부를 묻고 있는데,
이를 거꾸로 생각하면 빈 그래프에서 정점을 하나씩 추가할 때 그래프의 연결성을 따지는 문제로 바꿀 수 있습니다.
정점의 번호를 추가되는(생성되는) 순서대로 renumbering한 뒤,
(1번 정점의 component 크기) == (그래프 전체 크기) ? "YES" : "NO"를 출력하면 됩니다.
Disjoint Set만 안다면 USACO Gold 치고는 쉬운 문제입니다.
G. Coding of Permutations
이 문제 n^2으로 풀면 아주 칭찬해드리겠습니다.
이 문제는 다음의 연산을 빠르게 지원하는 자료구조를 만들면 해결할 수 있습니다.
- pop(x) : 원소 x를 제거한다.
- kth(k) : 현재 남아있는 원소 중 k번째로 큰 원소를 반환한다.
1) 자료구조 D에 1..n을 모두 때려박습니다.
2) 수열 B를 n..1까지 돌면서, D에서 B[i]번째로 큰 원소가 A[i]의 값이 됩니다.
2-1) 이 때 B[i]가 size(D)보다 크다면 NIE가 되고, NIE가 나오는 경우는 이것뿐입니다.
3) D에서 A[i]를 제거합니다.
작성 시간이 새벽 4시를 넘기고 있는 관계로 Correctness proof는 생략합니다.
해당 자료구조는
SQRT decomposition으로 \(O(\sqrt{n})\)에 구현할 수도 있고,
Segment tree를 이용해 \(O(\lg^2 n)\), 혹은 \(O(\lg n)\)에 구현할 수도 있고,
OSRank를 이용해 \(O(\lg n)\)에 구현할 수도 있습니다.
취향껏.