코드는 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번째 원소의 정렬 후 위치를 pi라고 하면 최소한 max(i−pi)번은 움직여야 함을 알 수 있습니다.
그리고 "왼쪽 이동의 의무"가 있는 원소들 ( pi< 현재 위치 ) 은 코드에 따라 무조건 1번은 왼쪽으로 움직이게 되므로 max(i−pi)는 한 턴마다 1씩은 감소합니다.
따라서 max(i−pi)가 답이 됩니다.
이 증명은 엄밀하지 않습니다. 엄밀한 증명은 대회 풀이 를 참조합시다.
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(n)에 구현할 수도 있고,
Segment tree를 이용해 O(lg2n), 혹은 O(lgn)에 구현할 수도 있고,
OSRank를 이용해 O(lgn)에 구현할 수도 있습니다.
취향껏.