By DaiRuichen007
라운드 #65 - 20250326
A. [AT-CF17-F] 숫자 분배
문제 링크
문제 요약
\(\text{정수 } n \in [1000, 2000], k \text{를 선택하여},\) 크기가 \(k\)인 \([1,n]\)의 부분집합을 \(n\)개 만들되, 임의의 두 집합 간 교집합 크기는 \(1\)이 되고, 각 원소는 정확히 \(k\)번 등장하도록 한다.
해법 분석
모든 집합 쌍이 공통 원소를 가지도록 하기 위해, 집합들을 정점으로 보고 교집합이 존재하는 경우 간선을 연결하면, 전체 구조는 \(K_n\) 그래프가 \(n\)개의 \(K_k\)로 분해되는 형태가 된다. 간선 수를 비교하면,
\[\dfrac{n(n-1)}{2} = n \cdot \dfrac{k(k-1)}{2}\]
에서 \(n = k(k-1) + 1\) 이 성립한다.
이제 \(n\)번째 원소가 포함된 집합을 중심으로 고려하면, 나머지 \(n-1\)개 원소가 \(k\)개 그룹으로 나뉘게 된다. 각 그룹 내에서는 다른 집합들이 각각 하나씩 선택해야 하며, 모든 원소는 \(k-1\)번 선택된다.
두 그룹의 원소 조합에 대해, \((i,j)\) 쌍은 특정한 위치에서 한 번만 출현하게 된다. 따라서 다음과 같은 구성이 가능하다: \((i,j)\)에 대해, 세 번째 그룹의 \((j+i) \bmod (k-1)\)번째 원소와 네 번째 그룹의 \((j+2i) \bmod (k-1)\)번째 원소를 선택한다.
두 그룹의 교차점은 \(j_1 + x i_1 \equiv j_2 + x i_2 \pmod{k-1}\)의 해로 결정되며, \(k-1\)이 소수일 경우 유일한 해가 존재한다. 따라서 \(k=38\)을 선택하면 충분하다.
코드 예시
#include <bits/stdc++.h>
using namespace std;
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int k = 38, n = k * (k - 1) + 1;
cout << n << " " << k << "\n";
for (int i = 0; i < k; ++i) {
for (int j = 1; j < k; ++j)
cout << i * (k - 1) + j << " ";
cout << n << "\n";
}
for (int i = 0; i < k - 1; ++i)
for (int j = 0; j < k - 1; ++j) {
cout << i + 1 << " ";
for (int t = 1, u = j; t < k; ++t, u = (u + i) % (k - 1))
cout << t * (k - 1) + u + 1 << " \n"[t == k - 1];
}
return 0;
}
B. [AT-CF16-E] 물 공급
문제 링크
문제 요약
평면 상에 \(n\)개의 점 \(p_1 \sim p_n\)이 주어지고, 각 점에는 물량 \(w_i\)가 있다. 점 \(p_i\)에서 \(v\)의 용량을 가져와 \(p_j\)로 운반하면, \(w_j\)는 \(\max(0, v - \mathrm{dis}(p_i, p_j))\)만큼 증가한다. 여기서 \(\mathrm{dis}\)는 유클리드 거리이다. 최종적으로 \(\min w_i\)의 값을 최대화하라. 제약조건: \(n \leq 16\).
해법 분석
모든 가능한 이동 경로 \((i,j)\)를 간선으로 표현한다. 연결된 컴포넌트 내부에서는 물량을 임의로 재배치할 수 있다. 이유는, 최소 스패닝 트리를 구성하고 각 간선에 대해 유량을 계산하면, 항상 합법적인 순서로 처리 가능하기 때문이다.
연결된 컴포넌트 \(S\)에 대해, 총 물량 \(W\)에서 \(S\)의 최소 스패닝 트리 길이 \(T\)를 빼면, 최적의 분배는 각 점이 \((W-T)/|S|\)만큼 받는 것이다.
다른 컴포넌트들에 대해 부분집합 병합을 시도하면, 시간 복잡도는 \(\mathcal{O}(3^n + n^2 2^n)\)이 된다.
코드 예시
#include <bits/stdc++.h>
#define ld long double
#define pc __builtin_popcount
using namespace std;
const ld inf = 1e18;
int n, x[16], y[16], z[16];
ld d[16][16], c[1 << 16], f[1 << 16];
signed main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i)
scanf("%d%d%d", &x[i], &y[i], &z[i]);
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
d[i][j] = sqrt(1ll * (x[i] - x[j]) * (x[i] - x[j]) +
1ll * (y[i] - y[j]) * (y[i] - y[j]));
for (int s = 0; s < (1 << n); ++s)
c[s] = inf;
for (int i = 0; i < n; ++i)
c[1 << i] = 0;
for (int s = 1; s < (1 << n); ++s)
for (int i = 0; i < n; ++i)
if (s >> i & 1)
for (int j = 0; j < n; ++j)
if (!(s >> j & 1))
c[s | (1 << j)] = min(c[s | (1 << j)], c[s] + d[i][j]);
for (int s = 1; s < (1 << n); ++s) {
ld w = 0;
for (int i = 0; i < n; ++i)
if (s >> i & 1)
w += z[i];
if (w > c[s])
f[s] = (w - c[s]) / pc(s);
for (int t = s & (s - 1); t; t = (t - 1) & s)
f[s] = max(f[s], min(f[t], f[s ^ t]));
}
printf("%.20Lf\n", f[(1 << n) - 1]);
return 0;
}
C. [CF983D] 아카디와 사각형
문제 링크
문제 요약
무한 평면 위에 \(n\)개의 직사각형이 주어졌을 때, 각 점의 색상은 해당 점을 덮는 직사각형 중 가장 큰 인덱스를 의미한다. 사용된 색상의 수를 구하라. 제약조건: \(n \leq 10^5\).
해법 분석
스캔라인 알고리즘과 세그먼트 트리 + 우선순위 큐를 활용한다. 세그먼트 트리의 각 노드는 해당 구간에서 덮여 있는 직사각형의 인덱스를 유지한다. 매번 새로운 컬러가 보이는지를 확인한다.
각 노드 \([l,r]\)에 대해, 서브트리에서 새로 보이는 최대 색상 \(f\)를 저장하고, 현재 노드의 최대 색상 \(c\)와 비교한다. 만약 \(c\)가 이미 본 적이 없으면 \(f\)를 업데이트하고, 그렇지 않다면 \(f < c\)이면 \(f = 0\)으로 설정한다.
하지만 이 방식은 잘못된 경우가 발생할 수 있다. 예를 들어 왼쪽 자식에 색상 2, 오른쪽 자식에 색상 3이 있고, 둘 다 이미 보았다면, \(c = 1\)일 때에도 \(f = 0\)이 되어야 한다.
따라서 \(g_i\)를 \(i\)를 덮는 이미 본 색상의 최댓값으로 정의하고, \(c > \min g[l,r]\)일 때만 \(f\)를 업데이트한다. 이를 동시에 관리하면 정확한 결과를 얻을 수 있다.
시간 복잡도: \(\mathcal{O}(n \log n)\).
코드 예시
#include <bits/stdc++.h>
using namespace std;
struct Heap {
priority_queue<int> qi, qo;
void ins(int x) { qi.push(x); }
void ers(int x) { qo.push(x); }
bool any() { return qi.size() > qo.size(); }
int top() {
while (qi.size() && qo.size() && qi.top() == qo.top())
qi.pop(), qo.pop();
return qi.top();
}
};
const int MAXN = 1e5 + 5, MAXS = 1 << 19;
int n, m, L[MAXN], R[MAXN], st[MAXN * 2];
bool vis[MAXN];
Heap tr[MAXS];
int mx[MAXS], mn[MAXS];
void psu(int p, bool o = 1) {
mx[p] = o ? max(mx[p << 1], mx[p << 1 | 1]) : 0;
mn[p] = o ? min(mn[p << 1], mn[p << 1 | 1]) : 0;
if (tr[p].any()) {
int c = tr[p].top();
if (!vis[c]) mx[p] = max(mx[p], c);
else mn[p] = max(mn[p], c);
}
if (mx[p] < mn[p]) mx[p] = 0;
}
void upd(int ul, int ur, int k, int o, int l = 1, int r = m, int p = 1) {
if (ul <= l && r <= ur) {
if (o > 0) tr[p].ins(k);
if (o < 0) tr[p].ers(k);
psu(p, l < r);
return;
}
int mid = (l + r) >> 1;
if (ul <= mid) upd(ul, ur, k, o, l, mid, p << 1);
if (mid < ur) upd(ul, ur, k, o, mid + 1, r, p << 1 | 1);
psu(p);
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n;
vector<array<int, 2>> op;
for (int i = 1, l, r; i <= n; ++i) {
cin >> l >> L[i] >> r >> R[i];
st[++m] = L[i], st[++m] = R[i];
op.push_back({l, i}), op.push_back({r, -i});
}
sort(st + 1, st + m + 1), m = unique(st + 1, st + m + 1) - st - 1;
for (int i = 1; i <= n; ++i) {
L[i] = lower_bound(st + 1, st + m + 1, L[i]) - st;
R[i] = lower_bound(st + 1, st + m + 1, R[i]) - st;
}
int ans = 0;
sort(op.begin(), op.end());
for (int i = 0; i < 2 * n; ++i) {
int x = abs(op[i][1]);
upd(L[x], R[x] - 1, x, op[i][1] > 0 ? 1 : -1);
if (i == 2 * n - 1 || op[i][0] < op[i + 1][0]) {
while (mx[1]) {
int x = mx[1];
++ans, vis[x] = 1;
upd(L[x], R[x] - 1, x, 0);
}
}
}
cout << ans + 1 << "\n";
return 0;
}
D. [AT-MJPC17-D] 방향 트리
문제 링크
문제 요약
\(n\)개의 정점으로 이루어진 트리에 각 간선을 방향으로 지정하여, 모든 경로 \(u \to v\)에서 방향과 반대인 간선 수의 최댓값을 최소화하고, 그 경우의 수를 구하라. 제약조건: \(n \le 1000\).
해법 분석
최장 경로(지름)의 길이를 \(d\)라고 하면, 답의 하한은 \(\lceil d/2 \rceil\)이다. 구현은 깊이에 따라 레이어링하여 홀수 레이어는 위로, 짝수 레이어는 아래로 방향을 지정하면 된다.
경로 \(u \to v\)의 비용을 \(h_u\)를 루트에서 \(u\)까지의 방향 간선 수로 정의하면, 비용은 \(\frac{1}{2}(|h_u - h_v| + \mathrm{dis}(u, v))\)이다. 이때 \(h\) 배열이 만족해야 할 조건은 \(h\) 값의 범위가 \(D - \mathrm{dep}_u\) 이내이고, 인접한 정점 사이의 차이는 \(1\)이어야 한다.
지름의 길이가 홀수이면, 중간을 기준으로 두 개의 서브트리로 나누고, 각 서브트리에서 \(h\) 값의 짝수/홀수 여부가 달라지므로, 각 서브트리의 루트에서 시작하는 경우를 따로 계산하고, 겹치는 경우를 제외한다.
동적 프로그래밍으로 \(f_{u,i}\)를 정점 \(u\)에서 \(h_u = i\)인 경우의 수로 정의하면, 시간 복잡도는 \(\mathcal{O}(n^2)\)이다.
코드 예시
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1025, MOD = 1e9 + 7, W = 505;
vector <int> G[MAXN];
int n, dep[MAXN], fa[MAXN];
void dfs1(int u) {
for (int v : G[u])
if (v ^ fa[u]) fa[v] = u, dep[v] = dep[u] + 1, dfs1(v);
}
ll f[MAXN][MAXN];
void dfs2(int u, int D, int o) {
for (int v : G[u])
if (v ^ fa[u]) fa[v] = u, dep[v] = dep[u] + 1, dfs2(v, D, o);
int L = dep[u] - D + W + o, R = D - dep[u] + W + o;
for (int i = L; i <= R; ++i) {
f[u][i] = 1;
for (int v : G[u])
if (v ^ fa[u])
f[u][i] = f[u][i] * (f[v][i - 1] + f[v][i + 1]) % MOD;
}
}
ll sol(int s, int t, int D, bool op) {
memset(f, 0, sizeof(f));
fa[s] = t, fa[t] = s, dep[s] = dep[t] = 0;
if (!op) dfs2(s, D + 1, 0), dfs2(t, D, 0);
else dfs2(s, D, 0), dfs2(t, D, 1);
ll ans = 0;
for (int i = 1; i < 2 * W; ++i)
ans = (ans + f[s][i] * (f[t][i - 1] + f[t][i + 1])) % MOD;
return ans;
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1, u, v; i < n; ++i)
cin >> u >> v, G[u].push_back(v), G[v].push_back(u);
int s, t;
dfs1(1), s = max_element(dep + 1, dep + n + 1) - dep;
dep[s] = fa[s] = 0, dfs1(s), t = max_element(dep + 1, dep + n + 1) - dep;
if (dep[t] % 2 == 0) {
int rt = t, D = dep[t] / 2;
for (int i = 0; i < D; ++i) rt = fa[rt];
dep[rt] = fa[rt] = 0, dfs2(rt, D, 0);
ll ans = 0;
for (int i = 1; i < 2 * W; ++i)
ans = (ans + f[rt][i]) % MOD;
cout << ans << "\n";
} else {
int D = dep[t] / 2;
for (int i = 0; i < D; ++i) t = fa[t];
s = fa[t];
ll ans = (sol(s, t, D, 0) + sol(t, s, D, 0) -
sol(s, t, D, 1) - sol(t, s, D, 1)) % MOD;
cout << (ans + MOD) % MOD << "\n";
}
return 0;
}