2023년 NYPC의 2라운드 첫 번째 대회의 풀이이다. 2023년 8월 13일 14시부터 17시까지 진행되었고, 네 문제가 출제되었다. 네 문제는 난이도순이다.
1. 오솔길
N개의 점이 주어지고, 점들의 $x$좌표와 $y$좌표는 모두 다르다. 두 점 $(x_1, y_1)$과 $(x_2, y_2)$가 있을 때, 두 점을 $(x_1, y_2)$, $(x_2, y_1)$으로 바꾸는 연산을 할 수 있다. 모든 점 쌍에 대해서 x좌표가 더 큰 점이 y좌표도 더 크도록 하기 위해 최소 몇 번의 연산이 필요한지를 계산하는 문제이다.
$N \le 200000$
풀이
우선 점들을 $x$좌표 오름차순으로 정렬하자. 여기서 두 점에 대한 연산을 하는 것은 두 점의 $y$좌표를 맞바꾸는 것과 같다. 따라서 문제를 최소 교환을 통해 $y$좌표를 정렬하는 문제로 바꿀 수 있다.
우선 $y$좌표가 모두 다르므로, 좌표 압축을 해서 1이상 $N$이하 범위의 숫자로 바꿔주자. 그러면 $Y$ 배열은 순열이 되는데, 순열 사이클 분할을 통해 순열을 여러 사이클로 분할하면, 각 사이클마다 (사이클 크기)-1이 그 사이클을 정렬하는데 필요한 교환 횟수가 된다. 따라서 순열 사이클 분할을 하고, 각 사이클의 크기를 구하면 $O(N)$에 풀 수 있다.
코드
#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 201010
#define MAXS 20
#define INF 1000000000
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define MOD 1000000007
pii arr[MAX];
int Y[MAX];
int vis[MAX];
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
int N;
cin >> N;
int i;
for (i = 1; i <= N; i++) cin >> arr[i].first >> arr[i].second;
sort(arr + 1, arr + N + 1);
vector<int> v;
for (i = 1; i <= N; i++) v.push_back(arr[i].second);
sort(v.begin(), v.end());
for (i = 1; i <= N; i++) Y[i] = lower_bound(v.begin(), v.end(), arr[i].second) - v.begin() + 1;
int cnt = 0;
for (i = 1; i <= N; i++) cnt += Y[i] != i;
for (i = 1; i <= N; i++) {
if (vis[i]) continue;
if (Y[i] != i) {
cnt--;
int v = i;
while (!vis[v]) {
vis[v] = 1;
v = Y[v];
}
}
}
cout << cnt << ln;
}2. 주사위 대체
$m$개의 수가 균등하게 나오는 주사위가 있고, 이 주사위를 적당한 횟수로 던져서 나오는 결과들을 분류하여 $n$개의 숫자가 나오는 주사위처럼 사용할 수 있는지 판별하는 문제이다. 아래는 문제에 나와 있는 $m=6, n=4$일 경우의 예시이다.
- 1, , 3, 4가 나오면, 그대로 1, 2, 3, 4
- 5가 나오면, 다시 굴려서 , , 이면 로, , 5, 이면
- 이 나오면, 다시 굴려서 , , 이면 으로, , , 이면 4
$m, n \le 10^{18}$
풀이
관찰 : 어떤 정수 $k$가 있어서 $m^k$가 $n$의 배수라면 답은 YES이고, 그렇지 않으면 NO이다.
위와 같은 관찰을 사용하면 풀 수 있다. $n, m$의 제한에 의해 두 수에는 소인수가 최대 60번 곱해져 있다. ($2^60>10^{18}$이므로) 따라서, $m^k$가 $n$의 배수가 되는 $k$가 존재한다면, $k<=60$을 가정해도 좋다. 따라서, $m^60$이 $n$의 배수인지만 확인하면 된다. 큰 수 연산을 활용해도 통과는 할 것 같지만, 중요한 것은 $n$으로 나눈 나머지이므로, $m$의 거듭제곱을 구할 때 계속 $n$으로 나눠주면서 구해도 된다. 나의 경우 long long 범위를 초과할 것 같아서 파이썬으로 풀었다.
코드
T = int(input())
for t in range(T):
m, n = input().split()
m = int(m)
n = int(n)
mul = m
for c in range(100) :
mul = mul % n
if n == 0:
break
mul = mul * m
if mul == 0:
print("YES")
else:
print("NO")
3. 창수의 고민
길이 $N$의 배열이 주어지고, $1 \le i < j \le N$인 $i, j$에 대해 배열의 $i$번째 원소가 $j$번째 원소보다 크거나 같은 쌍의 갯수를 만족 점수라 한다. $S, E$를 잘 정해서 배열의 $S$번 원소부터 $E$번 원소까지 $K$를 더했을 때 구해지는 만족 점수를 최대화해야 한다.
풀이
문제에서 주어진 배열을 $A_i$라 하자.
우선 $K$를 더하지 않았을 경우의 답은 수열에서 inversion을 세는 문제이므로 세그먼트 트리를 사용해서 풀 수 있다.(값의 범위가 커서 값 압축이 필요하다)
일단 $K$가 양수임을 가정하자. 그러면 $S=1$인 최적해가 반드시 존재한다. $S>1$인 해가 있을 때, 이 배열의 $S-1$번 이전 원소에 전부 $K$를 더해 $S=1$인 해를 만들었다고 생각해 보자. 이렇게 하면 원래 배열에서 조건을 만족하는 쌍은 반드시 조건을 만족한다. 원래 배열에서 조건을 만족했던 $(i, j)$ 쌍에 대하여, $j$에 $K$가 더해지면 반드시 $i$에도 $K$가 더해지기 때문이다.
따라서 각 $E$에 대해 $E$번 이전 원소에 $K$가 더해졌을 때 inversion이 어떻게 변하는지만 확인하면 된다. 여러 가지 방법이 있겠지만, 가장 간단한 것은 $E$를 하나씩 늘려가면서 보는 것이다.
현재 배열에 $E-1$번 원소까지는 전부 $K$가 더해졌고, 이제 $E$번 원소에 $K$가 더해질 때 inversion이 어떻게 되는지를 구해야 한다고 하자. $E-1$의 경우의 답을 알고 있으니, 답이 어떻게 변하는지만 확인하면 된다. $(i, E)$ ($i<E$)와 같은 쌍의 경우, $A_i$가 $A_E$이상 $A_E + K$ 미만일 때 값에 영향을 준다. $E$번 원소에 $K$가 더해지기 이전에는 조건을 만족하다가, 더해진 이후에는 더 이상 조건을 만족하지 않기 때문이다. $(E, j)$ ($E<j$)와 같은 쌍의 경우, $A_j$가 $A_E$초과 $A_E + K$이하일 경우 답에 영향을 준다. 이 쌍들은 더해지기 이전에는 조건을 만족하지 않다가, 이후에 조건을 만족하게 된다.
다음으로 $K$가 음수인 경우, 마찬가지로 $E=N$이라는 관찰을 할 수 있다. 이때 $[S, N]$에 $K$를 더하나 $[1, S-1]$에 $-K$를 더하나 답은 같으므로, $K$가 양수일 때와 정확히 같은 방식으로 풀 수 있다.
위 과정은 세그먼트 트리를 사용해서 빠르게 할 수 있다. 시간 복잡도는 $O(NlgN)$.
내 코드의 경우, 배열을 뒤집은 후 풀었다. 풀이 자체는 크게 다르지 않다.
코드
#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 301010
#define MAXS 20
#define INF 1000000000
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define MOD 1000000007
struct fenwick {
int N;
vector<int> tree;
fenwick(int N = 0) :N(N) { tree.resize(N + 1); }
void upd(int i, int x) { while (i <= N) { tree[i] += x, i += i & -i; } }
int get(int i) { int ans = 0; while (i) { ans += tree[i], i -= i & -i; } return ans; }
};
ll arr[MAX];
inline int getind(vector<ll>& v, ll x) { return lower_bound(v.begin(), v.end(), x) - v.begin() + 1; }
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
int N;
ll K;
cin >> N >> K;
int c = 0;
if (K < 0) c = 1, K *= -1;
int i;
vector<ll> v;
for (i = 1; i <= N; i++) cin >> arr[i], v.push_back(arr[i]), v.push_back(arr[i] - 1), v.push_back(arr[i] + K), v.push_back(arr[i] + K - 1);
reverse(arr + 1, arr + N + 1);
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
fenwick pfen(v.size()), sfen(v.size());
ll sum = 0;
for (i = 1; i <= N; i++) {
int ind = getind(v, arr[i] - 1);
sum += pfen.get(ind);
pfen.upd(getind(v, arr[i]), 1);
}
ll ans = sum;
int mv = 0;
for (i = N; i >= 1; i--) {
pfen.upd(getind(v, arr[i]), -1);
sum += pfen.get(getind(v, arr[i] + K)) - pfen.get(getind(v, arr[i]));
sum -= sfen.get(getind(v, arr[i] + K - 1)) - sfen.get(getind(v, arr[i] - 1));
sfen.upd(getind(v, arr[i] + K), 1);
if (sum > ans) {
ans = sum;
mv = i;
}
ans = max(ans, sum);
}
if (!mv) cout << 1 << bb << N << ln;
else {
if (c) {
if (mv == 1) cout << 1 << bb << N << ln;
else cout << N + 2 - mv << bb << N << ln;
}
else cout << 1 << bb << N + 1 - mv << ln;
}
}4. 편지
풀이
여러 가지 관찰이 필요한 문제이다.
관찰 1. 깊이(정점 1부터의 거리)가 같은 정점들을 전부 합쳐도 답은 유지된다.
깊이가 같은 정점들을 모두 합치면 트리는 직선이 되므로, 이후의 풀이에서는 주어지는 트리는 직선으로 가정하겠다.
관찰 2. $v$번 정점에 $k$개의 편지가 있다면, $v$번 정점에 단 하나만의 편지를 남기고 그 외의 모든 편지를 $v+1$번 정점으로 주어도 답은 유지된다.
예를 들어, 직선에 편지가 각각 3, 0, 2, 0, 0, 0개 있었다고 할 때, 이의 답은 각 정점에 편지가 1, 1, 1, 1, 1, 0개 있었을 경우와 같다.
관찰 2처럼 편지를 뒤쪽 정점으로 넘겼다면, 모든 시점에 대해서 각 정점은 최대 하나 이하만의 편지를 가지고 있게 된다.(맨 뒤쪽 정점 제외) 따라서, 이 경우의 답은 (편지 개수의 합)+(편지를 하나도 들고 있지 않은 정점의 개수)이 된다. (편지를 가지고 있는 가장 마지막 정점 뒤쪽에 있는 정점들은 계산에서 제외해야 한다)
따라서, 다음과 같은 값을 저장하는 세그먼트 트리를 사용해서 풀 수 있다. $l, r$은 세그먼트 트리의 노드가 관리하는 구간이다.
$sum$ : $[l, r]$ 정점들을 앞에서부터 보면서, 하나의 편지만을 남기고 모든 편지를 뒤쪽으로 넘겼을 때 $r$번 정점에 남게 되는 편지
$mx$ : 위 과정에서 편지를 뒤쪽으로 넘길 때, 단 하나의 편지도 가져가지 못 하게 되는 정점의 수
초기 상태에서 하나 이상의 편지를 가진 정점 중 가장 큰 인덱스를 가진 정점을 $v$라 하면, 세그먼트 트리에 $[1, v]$ 구간 쿼리를 날려서 편지를 하나도 들고 있지 않은 정점의 개수를 구할 수 있고, 모든 편지의 갯수의 합은 쿼리마다 선형에 관리할 수 있으므로, 총 시간 복잡도 $O(QlgN)$에 풀 수 있다.
내 코드의 세그먼트 트리 정의는 약간 다른데, sum을 마지막 정점이 다음 구간의 정점으로 넘기게 되는 편지의 수를 저장했다. 즉, 풀이의 정의보다 하나 작은 값을 저장했다.
코드
#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 201010
#define MAXS 20
#define INF 1000000000
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define MOD 1000000007
struct node {
ll sum;
ll cnt;
node(ll x = -1) :sum(max(x - 1, 0ll)), cnt(x ? 0 : 1) {}
};
node operator+(node n1, node n2) {
node ret;
ll mn = min(n2.cnt, n1.sum);
n2.cnt -= mn;
n1.sum -= mn;
ret.cnt = n1.cnt + n2.cnt;
ret.sum = n2.sum + n1.sum;
return ret;
}
int N, Q;
ll S[MAX];
namespace segtree {
node tree[MAX * 4];
void init(int s, int e, int loc = 1) {
if (s == e) {
tree[loc] = node(S[s]);
return;
}
int m = s + e >> 1;
init(s, m, loc * 2);
init(m + 1, e, loc * 2 + 1);
tree[loc] = tree[loc * 2] + tree[loc * 2 + 1];
}
void upd(int s, int e, int i, int loc = 1) {
if (e < i || i < s) return;
if (s == e) {
tree[loc] = node(S[i]);
return;
}
int m = s + e >> 1;
upd(s, m, i, loc * 2);
upd(m + 1, e, i, loc * 2 + 1);
tree[loc] = tree[loc * 2] + tree[loc * 2 + 1];
}
node query(int s, int e, int l, int r, int loc = 1) {
if (e < l || r < s) return node();
if (l <= s && e <= r) return tree[loc];
int m = s + e >> 1;
return query(s, m, l, r, loc * 2) + query(m + 1, e, l, r, loc * 2 + 1);
}
}
ll sum = 0;
ll cpy[MAX];
ll A[MAX];
int dep[MAX];
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> N >> Q;
int i, p, a, b;
dep[1] = 1;
for (i = 2; i <= N; i++) {
cin >> p;
dep[i] = dep[p] + 1;
}
for (i = 1; i <= N; i++) {
cin >> A[i];
S[dep[i]] += A[i];
sum += A[i];
}
set<int> st;
for (i = 1; i <= N; i++) if (S[i]) st.insert(i);
segtree::init(1, N);
if (st.size()) cout << segtree::query(1, N, 1, *st.rbegin()).cnt + sum << ln;
else cout << 0 << ln;
while (Q--) {
cin >> a >> b;
sum += b - A[a];
S[dep[a]] -= A[a];
A[a] = b;
S[dep[a]] += A[a];
if (S[dep[a]]) st.insert(dep[a]);
else st.erase(dep[a]);
segtree::upd(1, N, dep[a]);
if (st.size()) cout << segtree::query(1, N, 1, *st.rbegin()).cnt + sum << ln;
else cout << 0 << ln;
}
}