티스토리 뷰
랜덤 마라톤은 계속 나를 한계로 몰아붙이는 것 같다. 아무래도 랜덤 문제가 뽑히다 보니 실력 향상을 크게 느끼지는 못하고 있고, 그나마 승부욕 때문에 계속 푸는 것 같다. 이제는 재미로 문제를 푼다기보다 압박처럼 느껴지는 부분이 더 많은데, 450km를 달성하면 아마 그만둘 것 같다.
A. Fair and Square (Small)
나이브를 돌려 보면 이 성질을 만족하는 수가 거의 없다. 리스트를 precomputation해 두면 Large1 문제까지도 쉽게 풀 수 있다.
precomputation으로 풀었기 때문에 정답 코드를 첨부하지 않는다.
B. Kind of a Blur
문제를 잘 읽어 보면 단순히 연립방정식을 풀면 되는 문제라는 것을 알 수 있다. 그러나 반올림 이슈 때문에 계속 틀렸고 (실수 출력을 반올림으로 만들어 출제하는 것은 절대로 하면 안 되는 행동이다), 더 이상 이 문제를 생각하기 싫어서 리롤했다.
B. Bad Horse (Small2)
주어진 그래프가 이분 그래프인지 판별하는 문제이다. 이 문제는 너무나도 잘 알려져 있다.
옛날에 Small1 버전을 이 풀이로 푼 적이 있어서 그 코드를 조금만 수정해서 제출했다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t;
int n;
string a[102], b[102];
vector<int> link[202];
int ans;
int chk[202];
void dfs(int x, int c){
chk[x] = c;
for(auto y: link[x]){
if(chk[y] == c){
ans = 0;
return;
}
if(chk[y] == 3-c) continue;
dfs(y, 3-c);
}
}
int main(){
scanf("%d", &t);
for(int tc=1; tc<=t; tc++){
map<string, int> mp;
scanf("%d", &n);
for(int i=0; i<n; i++){
cin >> a[i] >> b[i];
if(!mp[a[i]]) mp[a[i]] = (int)mp.size();
if(!mp[b[i]]) mp[b[i]] = (int)mp.size();
link[mp[a[i]]].push_back(mp[b[i]]);
link[mp[b[i]]].push_back(mp[a[i]]);
}
ans=1;
for(int i=1; i<=(int)mp.size(); i++){
if(!chk[i]){
dfs(i, 1);
}
}
printf("Case #%d: %s\n", tc, ans ? "Yes" : "No");
for(int i=0; i<=200; i++) link[i].clear();
fill(chk, chk+202, 0);
}
}C. Fancy Stack
먼저 입력을 처리한다. 모든 높이들을 renumbering하고, 그 종류의 수를 $k$라고 한 뒤, 높이 $i$가 등장하는 횟수를 $cnt[i]$라고 하자. 또 $cnt[i]$의 누적합을 $sum[i]$라고 하자.
$DP[x][v]$를 위에서 $2x$번째 블록의 크기가 $v$인 경우의 수라고 하자. 이제 $DP[x][v]$와 $DP[x+1][v']$ 사이의 전이를 생각해 보자.
- 전이가 가능하려면 $v < v'$여야 한다.
- 위에서 $2x+1$번째 블록의 크기는 $v$ 미만이여야 한다. 이러한 블록의 수는 $v$ 미만의 크기를 가진 블록의 수 중 지금까지 쓰인 $2x-1$개를 제외한 것이므로, $sum[v-1] - 2x + 1$이다. 이 값을 $DP[x][v]$에 곱한 뒤 $DP[x+1][v']$에 더하면 된다.
위처럼 하면 $O(n^3)$ 풀이가 완성된다. 여기에서 $n$을 하나 떼어야 한다. 위 전이식을 다시 써 보면 $DP[x+1][v']$는 $\sum_{v < v'} DP[x][v] \times (sum[v-1] - 2x + 1)$가 되는데, 이 값은 $v$가 정해지면 고정이므로 누적합을 이용해 해결할 수 있다.
이렇게 하면 풀릴 것 같지만, 여기서 문제는 같은 원판이 여러 번 쓰이는 경우에 생긴다. 어떤 크기 $i$의 원판이 $v$개 있다고 해 보자. 이때 이 원판이 홀수 층에서 쓰이는 경우, 남아있는 원판 수만큼이 곱해진다. 그러나 짝수 층에서 쓰이는 경우 그 값이 곱해지지 않는다. 우리가 원하는 것은 전부 곱해지지 않은 값이다. 따라서, 짝수 층에서도 원판 개수를 곱해준 다음, 그 값을 최종 결과에서 나누어 주어야 한다. 시간 복잡도는 $O(n^2)$이다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 998244353;
const ll mpow(ll x, ll y){
if(!y) return 1;
if(y&1) return mpow(x, y-1) * x % MOD;
ll tmp = mpow(x, y/2);
return tmp * tmp % MOD;
}
int t;
int n, k;
int arr[5002];
ll cnt[5002], sum[5002];
ll DP[2502][5002];
ll val = 1;
int main(){
scanf("%d", &t);
while(t--){
scanf("%d", &n);
for(int i=1; i<=n; i++) scanf("%d", &arr[i]);
vector<int> renum (arr+1, arr+n+1);
sort(renum.begin(), renum.end());
renum.erase(unique(renum.begin(), renum.end()), renum.end());
k = (int)renum.size();
fill(cnt+1, cnt+k+1, 0);
for(int i=1; i<=n; i++){
arr[i] = lower_bound(renum.begin(), renum.end(), arr[i]) - renum.begin() + 1;
cnt[arr[i]]++;
}
val = 1;
for(int i=1; i<=k; i++){
sum[i] = sum[i-1] + cnt[i];
for(int j=1; j<=cnt[i]; j++) val = (val * j) % MOD;
}
val = mpow(val, MOD-2);
n /= 2;
for(int i=0; i<=n; i++) for(int j=0; j<=k; j++) DP[i][j] = 0;
for(int j=1; j<=k; j++) DP[1][j] = sum[j-1];
for(int i=2; i<=n; i++){
ll sumfront = 0;
for(int j=1; j<=k; j++){
DP[i][j] = sumfront;
sumfront = (sumfront + DP[i-1][j] * max(0LL, sum[j-1] - (i*2-3)) % MOD * cnt[j]) % MOD;
// printf("%d %d: %lld\n", i, j, DP[i][j]);
}
}
printf("%lld\n", DP[n][k] * val % MOD);
}
}D. Technobabble (Large)
일단 당연히도 각 단어를 수로 생각해야 한다. 이렇게 하면 최대 $2N = 2000$개의 수 중 하나로 이루어진 순서쌍 $N$개가 존재할 것이다. 또 한 수는 첫 번째나 두 번째 위치 중 한곳에서만 등장할 것이다. 이렇게 되니 좌표평면 모델링을 해 보고 싶어진다.
좌표평면으로 생각하면 다음과 같다. $1 \le x \le N$, $1 \le y \le N$인 $N$개의 정점 $(x_i, y_i)$가 있다. 이 정점들을 적당한 순서로 배치해, 특정한 $i$에 대해 $x_a = x_i$ $(a < i)$, $y_b = y_i$ $(b < i)$인 $a$와 $b$가 모두 존재하는 $i$의 수를 최대화해야 한다.
$x$좌표의 서로 다른 가짓수를 $A$, $y$좌표의 서로 다른 가짓수를 $B$라고 해 보자. $x$의 값과 $y$의 값을 이분 그래프로 생각해 보자. 왼쪽에 $A$개의 점, 오른쪽에 $B$개의 점을 두고, 어떤 점 $(x, y)$가 있다면 왼쪽의 $x$번 점과 오른쪽의 $y$번 점을 연결한다.
우리는 $(x, y)$의 두 성분 이미 모두 존재하는 점의 개수를 최대화하고 싶다. 이 말은, 이러한 점들을 모두 뺐을 때, 기존 점의 $x$와 $y$ 집합이 남은 점들의 $x$와 $y$ 집합을 포함한다는 것이다. 따라서 위 이분그래프에서 최소 개수의 edge를 선택해 모든 정점을 포함하는 minimum edge cover를 찾는 문제가 된다. minimum edge cover는 maximum matching을 찾은 뒤 남은 정점의 개수만큼을 더하면 된다는 사실이 잘 알려져 있다. 따라서 최대 매칭의 크기가 $p$라면 edge cover의 크기는 $p + (A+B-2p) = A+B-p$가 되고, 답은 $n+p-A-B$가 된다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t;
int n;
vector<int> link[1002];
int opp[1002]; bool visited[1002];
int ans;
bool dfs(int x){
visited[x] = 1;
for(int y: link[x]){
if(!opp[y] || (!visited[opp[y]] && dfs(opp[y]))){
opp[y] = x;
return true;
}
}
return false;
}
int main(){
cin >> t;
for(int tc=1; tc<=t; tc++){
map<string, int> mpA, mpB;
int A = 0, B = 0;
vector<pair<int, int> > edge;
cin >> n;
for(int i=1; i<=n; i++){
string s, t;
cin >> s >> t;
int av = mpA.count(s) ? mpA[s] : mpA[s] = ++A;
int bv = mpB.count(t) ? mpB[t] : mpB[t] = ++B;
edge.push_back(make_pair(av, bv));
}
for(int i=1; i<=A || i<=B; i++) link[i].clear(), opp[i] = 0;
for(auto [x, y]: edge) link[x].push_back(y);
ans=0;
for(int i=1; i<=A; i++){
fill(visited+1, visited+A+1, 0);
if(dfs(i)) ans++;
}
printf("Case #%d: %d\n", tc, n+ans-A-B);
}
}E. Longest Lane
짤 게 많고 케이스워크도 많아 보여서 리롤했다.
E. Test Data Analysis
길이가 $N$, $i$번째 수가 $A_i$ 이상 $B_i$ 이하의 정수일 때, 최대 구간 합이 $D$인 수열의 개수를 구하는 문제이다. 이런 문제를 풀 때는 정확히 $D$라는 조건을 $D$ 이하로 바로 바꿀 수 있으면 좋다. ($D$ 이하) - ($D-1$ 이하)로 계산하면 그대로 풀 수 있고, 아무래도 최대 구간 합이다 보니, 모든 구간의 합이 $D$ 이하라는 식으로 쉽게 조건을 환원할 수 있기 때문이다.
그렇다면 모든 구간의 합이 $D$ 이하라는 것은 무슨 뜻인가? 여기서는 누적합을 생각해야 한다. 어떤 구간 $[l, r]$ 의 구간 합은 $S_r - S_{l-1}$로 나타낼 수 있다. 즉 이 말은 $S_r - S_{l-1} \le D$라는 것이고, $0 \le i < j \le N$인 모든 $(i, j)$에 대해 $S_j - S_i \le D$라는 것이다.
기존 배열을 $P$라고 하자. $S_i - S_{i-1} = P_i$인데, 이는 $A_i \le S_i - S_{i-1} \le B_i$라는 것을 나타낸다. 따라서, 문제는 다음 두 조건을 만족하는 배열의 수를 찾는 것으로 정의된다.
- $S_0 = 0$
- $A_i \le S_i - S_{i-1} \le B_i$ (단, $1 \le i \le N$)
- $S_j - S_i \le D$ (단, $0 \le i < j \le N$)
여기서 $S_i$를 새로 정할 때 그 조건을 보자. 일단 $A_i + S_{i-1} \le S_i \le B_i + S_{i-1}$이고, $x < i$인 모든 $x$에 대해 $S_i \le S_x + D$이다. 따라서 $S_i$는 지금까지 나온 $S_x$의 최솟값과 직전 $S_i$의 값에 따라 제한이 결정된다. 여기서 별 생각 없이 다음과 같은 DP를 생각할 수 있다.
- $DP[i][now][min]$: $S_i$까지를 결정했고, $S_i = now$이며 $S_i$의 지금까지 최솟값이 $min$인 경우의 수.
이렇게 하면 $now$와 $min$의 범위가 각각 $NX$ 정도 되므로 $O(N^4 X^2)$ 정도의 (어마어마한) 시간 복잡도에 해결할 수 있다. 이제 이것을 획기적으로 줄일 방법을 찾아야 한다.
일단 $now$와 $min$을 둘 다 저장하는 것은 살짝 번거로워 보인다. 현재 중요한 값은 $now - min$이라는 값 하나뿐이며, 이것 하나만으로도 충분히 전이가 가능하다. 왜 그런지 살펴보자.
- 조건 $A_i \le S_i - S_{i-1} \le B_i$는 이번 $now - min$에서 다음 $now' - min'$으로 넘겨주는 데 전혀 문제가 없다. 만약 $S_i$가 새로운 $min$을 경신하지 않는다면, 그저 저 범위의 모든 $S_i - S_{i-1}$ 값에 대해 $now - min$을 $now' - min$으로 바꿔 주면 된다. 만약 $S_i$가 새로운 min을 경신한다면, $now' - min'$은 무조건 $0$이 될 것이다. 따라서 전이가 가능하다.
- 세 번째 조건은 단순히 $now - min \le D$가 된다! 다만 여기에서 조심해야 할 것이 하나 있는데, 사실 식을 정확히 쓰려면 저 $min$은 바로 직전의 $min$ 값이어야 한다. 만약 $D \ge 0$이라면, $now = min$인 경우 문제가 없으므로 이걸 크게 신경쓰지 않아도 된다. 그러나 만약 $D < 0$이라면, 이 부분이 문제가 된다. 하지만 생각해 보면 $D<0$인 경우의 답이 상당히 자명하다. 모든 수는 음수여야 하고, 이들을 더해봤자 음수이므로 결국 각각의 원소가 $D$ 이하이면 되는 문제이다. 이것을 사전에 처리해 주면, $D \ge 0$인 경우만 생각할 수 있으므로 문제가 없다.
이렇게 $DP[i][now-min]$으로 정의를 한다면, 문제를 $O(N X^2)$ 에 풀 수 있다. 여기서 시간을 더 줄여야 한다.
일단 시간복잡도의 각 성분이 어디서 나오는지를 생각한다면,
- $i$에서 $N$이,
- $now - min$에서 $X$가 ($now - min$은 정의상 $0$보다 작을 수 없고, DP의 전이 조건에 $now - min \le D$가 있기 때문)
- $(i, now - min)$에서 다음 $(i+1, now' - min')$으로 전이하는 경우의 수가 $X$개 ($A_i$와 $B_i$로 bound되기 때문)
임을 알 수 있다. 그런데 사실 이 문제에서 대부분의 전이는 연속한 구간 형태로 일어난다. 즉, 가능한 전이 형태는 두 가지뿐이고, 이들에 대해 매우 많은 수의 전이를 적당한 구간 형태로 묶어서 설명할 수 있다. 따라서, 누적합을 잘 사용하면 $X$항을 하나 떼는 것이 어렵지 않을 것이라고 생각할 수 있다.
다음과 같이 가능한 전이를 두 가지로 나눈다.
- $min$ 값이 갱신되지 않는 경우.
- $min$ 값이 갱신되는 경우.
먼저 $min$ 값이 갱신되지 않는 경우부터 보자. 이 경우 기존의 상태는 $(i, now - min)$이다. 여기서 다음 $P_i$ 값을 $v$로 정한다고 해 보자. 여기서 전이의 첫 번째 조건은 단순히 $A_i \le v \le B_i$이 된다. 또한, 이후의 $now$ 값은 $now + v$가 되고 $min$은 그대로 유지되므로 $now - min$은 $(now + v) - min$이 되어 $v$만큼 증가한다. 여기서 두 번째 조건에 의해 $now + v - min \le D$여야 한다. 마지막으로 이 연산에 의해 $min$이 갱신되면 안 되므로 $now + v \ge min$이어야 한다. 이상의 조건을 조합하면,
- $A_i \le v \le B_i$
- $v \le D - (now - min)$
- $v \ge -(now - min)$
임을 알 수 있다. 이 조건에 맞는 $v$들에 대해 전이를 누적합을 이용해 $(i, now-min)$에서 $(i, (now - min) + v)$로 수행해주면 된다.
다음으로 $min$ 값이 갱신되는 경우를 보자. 이 경우 기존의 상태는 $(i, now - min)$이고, 다음 $P_i$ 값을 마찬가지로 $v$라고 하자. 이때 전이의 첫 조건 $A_i \le v \le B_i$와 두 번째 조건 $v \le D - (now - min)$은 그대로 유지된다. 마지막 조건은 부등호만 바뀌는데, $now + v < min$이 되어야 하므로 $v < -(now - min)$이다. 최종적으로,
- $A_i \le v \le B_i$
- $v < -(now - min)$이다. (원래 있던 두 번째 조건은 이 조건에 의해 덮인다.)
위 조건에 맞는 $v$들에 대해 전이를 누적합을 이용해 $(i, now - min)$에서 $(i, 0)$으로 수행해주면 된다. 최종적으로 시간 복잡도 $O(NX)$에 문제를 해결할 수 있다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1'000'000'007;
int t;
int n, d;
int A[1002], B[1002];
ll DP[1002][1002];
ll calc(int LIM){
if(LIM < 0){ /// 음수인 경우
ll ans = 1;
for(int i=1; i<=n; i++){
ans = (ans * max(0, min(LIM, B[i]) - A[i] + 1)) % MOD;
}
return ans;
}
for(int i=0; i<=n; i++) for(int j=0; j<=LIM; j++) DP[i][j] = 0;
DP[0][0] = 1;
for(int i=1; i<=n; i++){
int a = A[i], b = B[i];
/// 첫 번째 전이
for(int j=0; j<=LIM; j++){
int L = a, R = b;
R = min(R, LIM - j), L = max(L, -j);
if(L <= R){
DP[i][j+L] = (DP[i][j+L] + DP[i-1][j]) % MOD;
DP[i][j+R+1] = (DP[i][j+R+1] + MOD - DP[i-1][j]) % MOD;
}
}
for(int j=1; j<=LIM; j++) DP[i][j] = (DP[i][j-1] + DP[i][j]) % MOD;
/// 두 번째 전이
for(int j=0; j<=LIM; j++){
int L = a, R = b;
R = min(R, -j-1);
if(L <= R) DP[i][0] = (DP[i][0] + DP[i-1][j] * (R - L + 1)) % MOD;
}
// for(int j=0; j<=LIM; j++) printf("(%d, %d): %lld\n", i, j, DP[i][j]);
}
ll ans = 0;
for(int i=0; i<=LIM; i++) ans += DP[n][i];
// printf("LIM %d: %lld\n", LIM, ans%MOD);
return ans % MOD;
}
int main(){
scanf("%d", &t);
while(t--){
scanf("%d %d", &n, &d);
for(int i=1; i<=n; i++) scanf("%d %d", &A[i], &B[i]);
ll ans = (calc(d) - calc(d-1) + MOD) % MOD;
printf("%lld\n", ans);
}
}F. Distance Statistics
트리 위에서 거리가 $K$ 이하인 정점 쌍의 수를 찾는 문제이다. smaller to larger + bst로 풀 수도 있고, centroid decomposition을 통해 풀 수도 있다. 난 centroid를 이용해 풀었다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m; ll LIM;
vector<pair<int, ll> > link[40002];
int sts[40002];
bool used[40002];
vector<int> cchild[40002];
ll ans;
void dfs1(int x, int p = -1){
sts[x] = 1;
for(auto [y, w]: link[x]){
if(p==y || used[y]) continue;
dfs1(y, x);
sts[x] += sts[y];
}
}
int dfs2(int x, int p, int s){
for(auto [y, w]: link[x]){
if(p==y || used[y]) continue;
if(sts[y] >= s) return dfs2(y, x, s);
}
return x;
}
void dfs3(int x, int p, vector<ll> &d, ll dist){
d.push_back(dist);
for(auto [y, w]: link[x]){
if(p==y || used[y] || dist+w > LIM) continue;
dfs3(y, x, d, dist+w);
}
}
void fc(int x){
dfs1(x);
x = dfs2(x, -1, (sts[x] + 1) / 2);
used[x] = 1;
vector<ll> allVec;
ll out = 0, in = 0;
for(auto [y, w]: link[x]){
if(used[y] || w > LIM) continue;
vector<ll> v;
dfs3(y, -1, v, w);
sort(v.begin(), v.end());
/// in 정리
for(ll d: v) in += upper_bound(v.begin(), v.end(), LIM - d) - v.begin();
for(ll d: v) allVec.push_back(d);
}
sort(allVec.begin(), allVec.end());
for(ll d: allVec){
out += upper_bound(allVec.begin(), allVec.end(), LIM - d) - allVec.begin();
if(d <= LIM) ans++;
}
ans += (out - in) / 2;
for(auto [y, w]: link[x]){
if(used[y]) continue;
fc(y);
}
}
int main(){
scanf("%d %d", &n, &m);
for(int i=1; i<=m; i++){
int x, y; ll d; char c;
scanf("%d %d %lld %c", &x, &y, &d, &c);
link[x].push_back(make_pair(y, d));
link[y].push_back(make_pair(x, d));
}
scanf("%lld", &LIM);
fc(1);
printf("%lld", ans);
}G. 비행기 타고 가요
일단 최단경로 문제니 다익스트라를 생각해 보자. 크게 두 가지 파트가 어렵다.
- 아직 방문하지 않은 정점 중 가장 최단거리가 작은 것을 찾기
- 어떤 점에서 이웃한 간선을 이용해 업데이트하기
일단 첫 번째 부분은 간단하다. Lazy propagation RMQ + 활성화/비활성화 세그먼트 트리의 형태로 관리를 해 두면 된다. 두 번째는 조금 더 어려운데, 생각을 해보면 각 티켓은 오직 그 시작점 구간에 해당하는 정점이 처음 방문되었을 때만 이용된다는 것을 고려하면 역시 세그먼트 트리를 이용해 처리할 수 있다. 시간 복잡도는 $O(N \log^2 N)$ 정도이다.
난이도 투표를 보고 알게 된 것인데, 이 문제는 흔히 알려진 "Segment Tree를 이용해 그래프의 간선을 줄이는 기법"으로 아름답게 풀 수 있다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
struct Tree1{ /// 거리 세그
ll tree[1<<19], lazy[1<<19];
int idx[1<<19], cnt[1<<19];
void init(int i, int l, int r){
tree[i] = lazy[i] = INF, idx[i] = l, cnt[i] = r-l+1;
if(l==r) return;
int m = (l+r)>>1;
init(i*2, l, m);
init(i*2+1, m+1, r);
}
void propagate(int i, int l, int r){
if(cnt[i]) tree[i] = min(tree[i], lazy[i]);
if(l!=r){
if(cnt[i*2]) lazy[i*2] = min(lazy[i*2], lazy[i]);
if(cnt[i*2+1]) lazy[i*2+1] = min(lazy[i*2+1], lazy[i]);
}
lazy[i] = INF;
}
void update(int i, int l, int r, int s, int e, ll v){
propagate(i, l, r);
if(r<s || e<l) return;
if(s<=l && r<=e){
lazy[i] = v;
propagate(i, l, r);
return;
}
int m = (l+r)>>1;
update(i*2, l, m, s, e, v);
update(i*2+1, m+1, r, s, e, v);
tree[i] = min(tree[i*2], tree[i*2+1]);
idx[i] = (tree[i*2] < tree[i*2+1] ? idx[i*2] : idx[i*2+1]);
}
void close(int i, int l, int r, int x){
propagate(i, l, r);
if(l==r){
tree[i] = INF*2;
cnt[i] = 0;
return;
}
int m = (l+r)>>1;
if(x<=m) close(i*2, l, m, x), propagate(i*2+1, m+1, r);
else close(i*2+1, m+1, r, x), propagate(i*2, l, m);
tree[i] = min(tree[i*2], tree[i*2+1]);
idx[i] = (tree[i*2] < tree[i*2+1] ? idx[i*2] : idx[i*2+1]);
cnt[i] = cnt[i*2] + cnt[i*2+1];
}
pair<ll, int> query(int i, int l, int r, int s, int e){
propagate(i, l, r);
if(r<s || e<l) return make_pair(INF, l);
if(s<=l && r<=e) return make_pair(tree[i], idx[i]);
int m = (l+r)>>1;
return min(query(i*2, l, m, s, e), query(i*2+1, m+1, r, s, e));
}
} tree1;
struct Tree2{
vector<int> tree[1<<19];
void update(int i, int l, int r, int s, int e, int v){
if(r<s || e<l) return;
if(s<=l && r<=e){
tree[i].push_back(v);
return;
}
int m = (l+r)>>1;
update(i*2, l, m, s, e, v);
update(i*2+1, m+1, r, s, e, v);
}
void query(int i, int l, int r, int x, vector<int> &vec){
for(int v: tree[i]) vec.push_back(v);
tree[i].clear();
if(l==r) return;
int m = (l+r)>>1;
if(x<=m) query(i*2, l, m, x, vec);
else query(i*2+1, m+1, r, x, vec);
}
} tree2;
int n, k, s;
ll cost[250002];
int sl[250002], sr[250002], el[250002], er[250002];
ll ans[250002];
bool used[250002];
int main(){
scanf("%d %d %d", &n, &k, &s);
for(int i=1; i<=k; i++){
scanf("%lld %d %d %d %d", &cost[i], &sl[i], &sr[i], &el[i], &er[i]);
}
tree1.init(1, 1, n);
tree1.update(1, 1, n, s, s, 0);
for(int i=1; i<=k; i++){
tree2.update(1, 1, n, sl[i], sr[i], i);
}
for(int i=1; i<=n; i++) ans[i] = -1;
while(true){
pair<ll, int> pr = tree1.query(1, 1, n, 1, n);
if(pr.first >= INF) break;
int x = pr.second; ll d = pr.first;
ans[x] = d;
tree1.close(1, 1, n, x);
vector<int> v;
tree2.query(1, 1, n, x, v);
for(int p: v){
if(used[p]) continue;
tree1.update(1, 1, n, el[p], er[p], d + cost[p]);
used[p] = 1;
}
}
for(int i=1; i<=n; i++) printf("%lld ", ans[i]);
}H. 목공
어려워서 리롤했다.
H. Maze Reduction
풀이를 생각했다고 믿고 짰는데 문제를 잘못 읽었고, 그 뒤로 진전이 없어서 리롤했다.
H. Rolling Rick
저 셋은 시간을 재고 돌려고 아껴놓은 셋이었어서 리롤했다.
H. Tree of Charge
전형적인 트리와 쿼리 유형의 문제지만, 특수한 컨셉이었기 때문에 접근이 조금 어려웠다.
쿼리를 처리하는 방법을 조금 특이하게 생각해보기로 했다. 보통의 경우라면 적당한 자료구조를 만들어 전체 charge의 변화를 관리하겠지만, 그러지 말고 각각의 전하에 집중한 뒤, 해당 전하가 어떻게 이동하는지를 생각해 보자.
일단 중간에 추가되는 전하는 무시하고 생각해 보자. 그렇다면 초기 노드 $x$에 전하 $q$가 있었을 것이다. 이 전하에 대해서만 집중해 보기로 하자. 다음과 같은 쿼리들이 추가될 것이다.
- 모든 노드의 전하를 위로 올림
- 모든 노드의 전하를 아래로 내림
여기서 전하를 아래로 내린 뒤 위로 올리게 되면 이것은 없는 것이나 마찬가지이다. 리프 밑에는 가상의 정점들이 line 형태로 계속 있다고 가정하였기 때문에, 이런 경우를 생각할 필요가 없다. 쿼리를 UUDUDDDUDDUUD 와 같이 문자열로 써 본다면, DU와 같은 부분은 없는 것과 다름없다고 생각해도 된다. 그렇다면 남은 문자열의 형태는 무조건 UUUUDDDD와 같이 앞에 U가 특정 개수만큼 있고, 그 다음으로 D가 특정 개수만큼 있는 형태가 될 것이다. 이 형태는 해당 전하가 적당한 정점 $p$까지 올라갔다가 (이 $p$를 구하는 것은 LCA를 변형한 kthParent로 가능) 이후 일정 단계를 내려온다고 생각할 수 있다. (UD 형태의 문자열을 압축하지 못하는 이유는 루트가 있기 때문이다.)
여기서 어려운 부분은 각 전하가 자식 노드로 내려올 때 고른 분포로 내려온다는 것이다. 이때 이 비율을 어떻게 계산할 수 있을까? 이것을 빠른 업데이트가 가능한 자료구조로 만들어야 한다. 다음과 같은 방식을 생각해 보자.
$1$만큼의 전하가 루트 노드에 있다고 가정하고, 여기서 $x$의 깊이만큼 D 연산을 수행했을 때 노드 $x$에 도착한 비율을 $r_x$라고 하자. 이때 $r_x$는 단순히 조상 노드들의 자식 수를 모두 곱한 것의 역수일 것이다. 만약 적당한 노드 $p$가 $x$의 조상이었다면, $p$에서 $q$만큼의 전하가 $x$로 이동했을 때 도착한 전하의 양은 $q \times \frac{r_x}{r_p}$임을 알 수 있다.
어떤 노드 $x$에 현재 $q$만큼의 전하가 있고, 이후로 D 연산이 $k$번 이루어진다고 하자. 이것을 업데이트하기 위해 다음과 같은 방식을 취할 것이다. 먼저 모든 노드들에 dfs numbering을 하고, 같은 깊이의 노드들끼리 dfs numbering 순으로 정렬하여 세그먼트 트리를 만들자. 이때 노드 $x$에서 전하가 도착할 정점들의 dfs number는 구간을 이룬다. 업데이트에 대한 사전 정보를 통해 $q$와 $r_p$의 값을 알 수 있으므로, 구간에 $q \times \frac{1}{r_p}$의 값을 더해 준다. 이후 각 노드에 쌓인 양을 계산할 때 $r_x$만큼을 곱해 계산하면 된다.
이제 중간에 추가된 노드가 있을 경우의 상황을 생각해 보자. 위의 UDDUUDU… 와 같이 생긴 문자열을 쿼리 문자열이라고 하자. 이 문자열은 앞으로 해당 노드의 전하가 옮겨져야 할 위치를 나타낸다. 뒤쪽의 전하 추가 업데이트부터 생각한다면, 저 쿼리 문자열은 앞에 계속 특정 문자가 붙는 형태로 생각할 수 있다. 이때 앞에서 언급한 UUUUDDDD 꼴을 지속적으로 관리할 것이다. 앞의 U 개수와 뒤의 D 개수를 쉽게 관리할 수 있다. 이제 위에서 언급한 방법으로 업데이트를 처리할 수 있다.
시간 복잡도는 $O((N+Q) \log^2 N)$이다. 몇 가지 구현 팁을 적어 놓자면, 위의 세그먼트 트리는 펜윅으로 처리할 수 있고, 위의 dfs numbering과 깊이로 세그먼트 트리를 만드는 것은 bfs ordering으로 대체하는 것과 동치이다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1'000'000'007;
ll mpow(ll x, ll y){
if(!y) return 1;
if(y&1) return mpow(x, y-1) * x % MOD;
ll tmp = mpow(x, y/2);
return tmp * tmp % MOD;
}
inline ll modInv(ll x){
return mpow(x, MOD-2);
}
struct Charge{
int t, x; ll q;
Charge(){}
Charge(int t, int x, ll q): t(t), x(x), q(q){}
bool operator<(const Charge &r)const{
return t>r.t;
}
};
struct Fenwick{
int n;
ll tree[500002];
void init(int _n){
n = _n;
}
void update(int x, ll v){
while(x<=n){
tree[x] = (tree[x] + v) % MOD;
x += x&-x;
}
}
ll query(int x){
ll ret = 0;
while(x){
ret += tree[x];
x -= x&-x;
}
return ret % MOD;
}
} tree;
int n, q;
vector<Charge> charges;
vector<int> link[500002];
char qt[500002];
int dist[500002], ord[500002], idx[500002], ordCnt;
int distS[500002], distE[500002];
int par[500002], LCADB[500002][20];
ll rat[500002];
void order(){
queue<int> que;
vector<bool> visited (n+1, 0);
que.push(1);
visited[1] = 1;
rat[1] = 1;
while(!que.empty()){
int x = que.front(); que.pop();
ord[++ordCnt] = x, idx[x] = ordCnt;
ll child_cnt = (int)link[x].size() - (x == 1 ? 0 : 1);
for(int y: link[x]){
if(visited[y]) continue;
que.push(y);
visited[y] = 1;
dist[y] = dist[x] + 1;
par[y] = x;
rat[y] = rat[x] * modInv(child_cnt) % MOD;
}
}
for(int i=0; i<=n; i++) distS[i] = 1e9, distE[i] = 0;
for(int i=1; i<=n; i++){
distS[dist[i]] = min(distS[dist[i]], idx[i]);
distE[dist[i]] = max(distE[dist[i]], idx[i]);
}
par[1] = 1;
for(int i=1; i<=n; i++) LCADB[i][0] = par[i];
for(int d=1; d<20; d++) for(int i=1; i<=n; i++) LCADB[i][d] = LCADB[LCADB[i][d-1]][d-1];
}
int kthParent(int x, int k){
for(int d=0; d<20; d++) if((k>>d)&1) x = LCADB[x][d];
return x;
}
int main(){
scanf("%d", &n);
for(int i=1; i<=n; i++){
ll v;
scanf("%lld", &v);
if(v) charges.push_back(Charge(0, i, v));
}
for(int i=1; i<n; i++){
int x, y;
scanf("%d %d", &x, &y);
link[x].push_back(y);
link[y].push_back(x);
}
scanf("%d", &q);
for(int i=1; i<=q; i++){
scanf(" %c", &qt[i]);
if(qt[i] == '+'){
int x; ll v;
scanf("%d %lld", &x, &v);
if(v) charges.push_back(Charge(i, x, v));
}
}
sort(charges.begin(), charges.end()); /// 뒤의 업데이트 쿼리가 앞에 오도록 정렬
/// 트리 전처리
order();
tree.init(n);
int u = 0, d = 0, pnt = q+1;
for(Charge &p: charges){
while(pnt > p.t){
pnt--;
if(qt[pnt] == '^') u++;
else if(qt[pnt] == 'v'){
if(u) u--;
else d++;
}
}
int x = kthParent(p.x, u);
int depth = dist[x] + d;
if(depth > n || distS[depth] == 1e9) continue; /// 어차피 너무 깊다
ll q = p.q * modInv(rat[x]) % MOD;
/// 구간의 범위를 이분탐색을 통해 찾는다
int L = distS[depth], R = distE[depth];
int S = R+1;
while(L <= R){
int M = (L+R)/2;
if(idx[x] <= idx[kthParent(ord[M], d)]) S = M, R = M-1;
else L = M+1;
}
L = distS[depth], R = distE[depth];
int E = L-1;
while(L <= R){
int M = (L+R)/2;
if(idx[kthParent(ord[M], d)] <= idx[x]) E = M, L = M+1;
else R = M-1;
}
if(S > E) continue;
tree.update(S, q);
tree.update(E+1, (MOD - q) % MOD);
}
for(int i=1; i<=n; i++){
ll v = tree.query(idx[i]) * rat[i] % MOD;
printf("%lld ", v);
}
}'문제풀이 > 랜덤 마라톤' 카테고리의 다른 글
| 랜덤 마라톤 11주차 (최종) (0) | 2024.08.21 |
|---|---|
| 랜덤 마라톤 9주차 (0) | 2024.08.06 |
| 랜덤 마라톤 8주차 (0) | 2024.07.30 |
| 랜덤 마라톤 7주차 (0) | 2024.07.24 |
| 랜덤 마라톤 6주차 (0) | 2024.07.14 |