A번: 역순 배열
직접 패턴을 분석해보면 규칙을 발견할 수 있다. 인덱스가 홀수번째끼리, 짝수번째끼리 서로 인접하며, 전체 배열은 홀수/짝수 인덱스 그룹이 번아 등장하는 형태가 된다.
구체적으로 다음과 같이 구성된다:
- n이 홀수: aₙ, aₙ₋₂, ... , a₁ 뒤에 a₂, a₄, ... , aₙ₋₁
- n이 짝수: aₙ, aₙ₋₂, ... , a₂ 뒤에 a₁, a₃, ... , aₙ₋₁
시간 복잡도는 O(n)이다.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 5;
int n, arr[MAXN];
int main() {
freopen("reverse.in", "r", stdin);
freopen("reverse.ans", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> arr[i];
if (n % 2 == 1) {
for (int p = n; p >= 1; p -= 2) cout << arr[p] << ' ';
for (int p = 2; p <= n; p += 2) cout << arr[p] << ' ';
} else {
for (int p = n; p >= 2; p -= 2) cout << arr[p] << ' ';
for (int p = 1; p < n; p += 2) cout << arr[p] << ' ';
}
return 0;
}B번: 물류 네트워크
핵심 관찰: 어떤 간선이 원래 그래프의 어떤 MST에도 포함되지 않는다면, 새로운 간선을 추가한 후에도 해당 간선은 여전히 불필요하다. 이는 Kruskal 알고리즘의 정렬 기반 처리 과정에서 자연스럽게 이해할 수 있다.
따라서 다음과 같은 전략을 사용한다:
- Prim 알고리즘으로 원래 그래프의 MST를 구성하는 n-1개의 핵심 간선을 추출
- 새로 추가될 q개의 간선과 함께 정렬
- 각 단계별로 Kruskal을 q+1회 수행
전체 복잡도는 O(n² + nq log n)이다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e4 + 5;
int n, q, xs[MAXN], ys[MAXN], ecnt, par[MAXN];
int trace[MAXN], vis[MAXN];
ll dist[MAXN];
ll total;
struct Line {
int from, to, phase;
ll weight;
bool operator<(const Line& o) const { return weight < o.weight; }
} edges[MAXN];
ll cube_abs(ll v) {
return v < 0 ? -v * v * v : v * v * v;
}
ll euclidean(int u, int v) {
return cube_abs(xs[u] - xs[v]) + cube_abs(ys[u] - ys[v]);
}
void insert_edge(int u, int v, ll w, int t) {
edges[++ecnt] = {u, v, t, w};
}
void build_mst() {
memset(dist, 0x3f, sizeof(dist));
dist[1] = 0;
for (int round = 1; round <= n; ++round) {
int cur = 0;
for (int i = 1; i <= n; ++i)
if (!vis[i] && (cur == 0 || dist[cur] > dist[i]))
cur = i;
vis[cur] = 1;
if (trace[cur]) insert_edge(cur, trace[cur], dist[cur], 0);
for (int i = 1; i <= n; ++i) {
if (vis[i]) continue;
ll d = euclidean(cur, i);
if (dist[i] > d) {
dist[i] = d;
trace[i] = cur;
}
}
}
}
int get_root(int x) {
return par[x] == x ? x : par[x] = get_root(par[x]);
}
void kruskal_process(int limit) {
for (int i = 1; i <= n; ++i) par[i] = i;
total = 0;
for (int i = 1; i <= ecnt; ++i) {
if (edges[i].phase > limit) continue;
int u = get_root(edges[i].from);
int v = get_root(edges[i].to);
if (u != v) {
total += edges[i].weight;
par[u] = v;
}
}
cout << total << '\n';
}
int main() {
freopen("logistics.in", "r", stdin);
freopen("logistics.ans", "w", stdout);
cin >> n >> q;
for (int i = 1; i <= n; ++i) cin >> xs[i] >> ys[i];
build_mst();
for (int i = 1; i <= q; ++i) {
int u, v; ll w;
cin >> u >> v >> w;
insert_edge(u, v, w, i);
}
sort(edges + 1, edges + ecnt + 1);
for (int i = 0; i <= q; ++i) kruskal_process(i);
return 0;
}C번: 수열 변환
정렬된 상태가 최적임은 자명하다. 목표 수열과 현재 수열을 각각 정렬한 후, 대응하는 위치끼리 매칭시키면 최소 비용을 얻는다.
또한 이 문제는 순열 사이클 분해 관점에서도 접근 가능하다. n - (사이클 개수)가 필요한 교환 횟수가 된다.
#include <bits/stdc++.h>
#define val first
#define pos second
using namespace std;
typedef long long LL;
typedef pair<int, int> Node;
const int MAXN = 300005, MOD = 998244353;
int n, flag;
int order[MAXN];
Node src[MAXN], dst[MAXN];
int main() {
freopen("sequence.in", "r", stdin);
freopen("sequence.ans", "w", stdout);
cin >> n >> flag;
for (int i = 1; i <= n; ++i) {
cin >> src[i].val;
src[i].pos = i;
}
for (int i = 1; i <= n; ++i) {
cin >> dst[i].val;
dst[i].pos = i;
}
sort(src + 1, src + n + 1);
sort(dst + 1, dst + n + 1);
// src[i].pos 위치의 원소가 i번째로 작아야 함
for (int i = 1; i <= n; ++i) order[src[i].pos] = i;
LL cost = 0, swaps = 0;
for (int i = 1; i <= n; ++i) {
int target = dst[i].pos;
if (src[i].pos != target) {
int j = order[target];
swap(order[src[i].pos], order[target]);
swap(src[i].pos, src[j].pos);
++swaps;
}
LL diff = (LL)dst[i].val - src[i].val;
cost = (cost + diff * diff) % MOD;
}
cout << cost;
if (flag) cout << " " << swaps << endl;
return 0;
}D번: 마법 사각형
k×k 사각형을 고려할 때, 행 기준 가중치 xᵢ와 열 기준 가중치 yⱼ를 부여하면 aᵢ,ⱼ = xᵢ + yⱼ 형태로 모든 합법적인 사각형을 표현할 수 있다.
임의의 합법 사각형은 (xᵢ = aᵢ,₁, yⱼ = a₁,ⱼ - a₁,₁)으로 표현되며, (xᵢ+c, yⱼ-c)와 동치이다. min(xᵢ)=0으로 고정하면 사각형과 수열이 일대일 대응하게 된다.
이때 aᵢ,ⱼ ≥ m 조건은 min(yⱼ) ≥ m과 동치이므로, yⱼ에서 m을 빼면: 최대 n-k·m개의 돌을 2k개 칸에 배분하되, 처음 k개 중 하나는 비어있어야 하는 경우의 수가 된다.
포함-배제를 적용하면:
Σₖ [C(n-k·m+2k, 2k) - C(n-k·m+k, 2k)]
#include <bits/stdc++.h>
using namespace std;
const int LIM = 2e5 + 5, MOD = 998244353;
int n, m;
int fact[LIM], ifact[LIM];
int mod_pow(int base, int exp, int res = 1) {
for (; exp; exp >>= 1, base = 1LL * base * base % MOD)
if (exp & 1) res = 1LL * res * base % MOD;
return res;
}
void init_comb(int up_to) {
fact[0] = 1;
for (int i = 1; i <= up_to; ++i)
fact[i] = 1LL * fact[i-1] * i % MOD;
ifact[up_to] = mod_pow(fact[up_to], MOD - 2);
for (int i = up_to; i >= 1; --i)
ifact[i-1] = 1LL * ifact[i] * i % MOD;
}
int nCr(int nn, int rr) {
if (nn < rr || rr < 0) return 0;
return 1LL * fact[nn] * ifact[rr] % MOD * ifact[nn-rr] % MOD;
}
void solve_case() {
int result = 0;
for (int k = 1; 1LL * k * m <= n; ++k) {
int remain = n - k * m;
result = (result + nCr(remain + 2*k, 2*k)) % MOD;
result = (result - nCr(remain + k, 2*k)) % MOD;
}
result = (result % MOD + MOD) % MOD;
cout << result << '\n';
}
int main() {
freopen("magic.in", "r", stdin);
freopen("magic.ans", "w", stdout);
init_comb(2e5);
int tc;
cin >> tc;
while (tc--) {
cin >> n >> m;
solve_case();
}
return 0;
}