돈 셋: AGC034 A. Kenken Race C D인 경우로 나누어 풀 수 있다. 전자의 경우에는 A와 D 사이에 연속된 돌이 없는지만 확인해주면 된다. 후자의 경우에는 추가적으로 Snuke와 Fnuke가 순서를 바꿀 수 있는지를 체크해줘야 하는데, B와 D 사이에 연속된 3개의 칸이 모두 비어있을 경우 순서를 바꿀 수 있음을 관찰하면 된다. B. ABC ABC를 BCA로 바꾼다는 걸 약간 다르게 해석해 보면, 'A'와 'BC'가 자리를 바꾼다고 해석할 수 있다. 그러면 문제는 자리 바꾸기 횟수의 최댓값을 구하는 것으로 바뀐다. A의 개수를 누적해주면서 BC가 나올 때마다 그 값을 답에 누적시키고, A도 BC도 아닌 문자가 나오면 A의 개수를 0으로 초기화하는 작업을 반복하면 ..
문제셋: JOI Spring Training Camp/Qualifying Trial 2015/2016 Day 2 Employment 이런 유형의 문제를 예전에 고민해본 경험이 있어서 덕분에 거의 보자마자 풀이가 떠올랐다. 평가치가 높은 사원부터 고용한다고 생각해보면, i번째 사원이 고용될 때 i-1번째 사원과 i+1번째 사원이 이미 고용되어있었는지 아닌지 여부에 따라 그룹의 개수가 어떻게 변화하는지 알 수 있다. i번째 사원마다 그룹의 개수가 어떻게 변화하는지의 값을 C[i]라고 하자. 이제 펜윅 트리와 같은 구간합 자료구조를 통해서 평가치가 가장 높은 사원부터 고용되는 사원들 중 평가치가 가장 낮은 사원까지의 C[i]값을 더하면 그룹의 개수를 알 수 있다. i번째 사원의 평가치가 업데이트될 때 바뀔..
작년 추석 즈음에 BOJ 슬랙에서 jwvg0425님이 같이 대회를 열 분들을 찾고 있다는 말을 들었다. 나도 문제를 출제해보고 싶어서 대회 출제를 하게 되었다! 7문제 중 3문제를 출제했다. 이 글은 그제 대회가 끝나고 후기 겸 작성하는 글이다. (스포일러도 약간 있다!) 대회 URL풀이 K-균등 문자열이 문제는 내가 전부터 생각해 놓았던 문제였고, 어렵지 않게 디스크립션, 데이터와 솔루션을 만들 수 있었다. 커팅 풀이가 통과할 일이 거의 없어서, (O(NM) 다음에 빠른 풀이가 O(NM * 2^N)이었다) 랜덤으로 거의 모든 데이터를 만들었다. 유니언 파인드에서 경로압축을 안 한 풀이가 시간초과가 나는 걸 확인하고 데이터는 더 이상 만들지 않았다. 대회에서 그것 때문에 TLE 난 제출도 있었는데, 뭔가..
요즘 유사코 골드를 돌고 있습니다! Balanced Photo 먼저 소들의 키를 1~N 범위로 압축해줍니다. 그런 뒤 1~N번 소까지 순회하며 BIT를 이용해 키가 $[h_i+1, N]$ 범위에 있는 소들의 합을 $L_i$에 저장합니다. $L_i$를 채운 뒤에는 자신의 키도 BIT에 업데이트해줍니다. $R$ 배열은 순회 순서를 반대로 해서 채워줄 수 있습니다. 이 과정을 모두 마친 뒤 $Min(L_i, R_i) * 2 < Max(L_i, R_i)$를 만족하는 소들의 개수를 세 주면 됩니다. 시간복잡도는 O(NlogN)입니다. 간단한 자료구조 문제였습니다! #include using namespace std; typedef pair pii; pii arr[100009]; int l[100009], tree..
문제 Sparse Table을 통해 문제를 해결할 수 있다. $par_{i, k}$를 $i$번 정점에서 $2^k$번 위로 올라간 정점이라고 정의하면, $par_{i, k} = par_{par_{i, k-1}, k-1}$과 같은 점화식으로 par를 채울 수 있다. 이걸 Sparse Table이라고 하나보다. par 배열을 통해 임의의 정점에서 $K$번 위로 올라간 정점을 $O(logK)$만에 찾을 수 있다. $dist_i$를 루트에서 $i$번 정점까지의 거리라고 정의하면 1번 쿼리의 답은 $dist_u+dist_v-2*dist_{lca(u,v)}$이다. 2번 쿼리는 $K$번째 정점이 어디에 위치하는가만 알면 Sparse Table로 $K$번째 정점을 찾을 수 있다. $K$번째 정점이 $u$와 $LCA(u,..