5번 문제를 제외한 모든 문제를 풀었고, 5번 문제에서도 부분점수 42점을 획득해 총점 1092점을 획득했다. 쓸 수 있는 12시간을 모두 쏟아부었고, 지금까지 가장 오랜 시간동안 집중해서 문제를 푼 경험일 것 같다. 노력한 만큼 결과가 잘 따라줘서 다행이라고 생각한다.
이번에도 문제 퀄리티는 전체적으로 좋았다. 적당히 아이디어를 사용해야 하는 문제들도 있었고 웰노운 문제들도 있어서 전체적으로 밸런스가 좋았다고 생각한다. 난이도가 1차 예선에 비해 비약적으로 상승해서 한 문제를 푸는데 꽤 오랜 시간을 썼고, 2, 3번 문제에서는 제출 제한 때문에 문제를 못 풀 뻔 하기도 했다. 그래서 전체적으로 커트라인이 300점 조금 넘는 정도로 낮게 잡힌 것 같다. AI가 밥그릇을 뺏어간 영향으로 상의 개수가 반토막이 나버려서 인원수가 좀 줄지 않을까 생각했는데 100명 조금 넘게 불러주었다.
1번 풀이
1번부터 플래티넘 문제가 나와서 당황했다. 내가 같은 아이디어를 쓰는 문제를 전에 풀어 봤기 때문에 나는 쉽게 풀 수 있었지만, 그러한 경험이 없었다면 훨씬 어려웠을 것이다. 그만큼 이 아이디어는 알고 있으면 그리디 문제를 푸는 데 큰 도움이 될 것이라고 생각한다.
우선 이 문제의 풀이를 이해하기 위해서 구슬 개수가 $N$개인 상황부터 살펴 봐야 한다. 이런 문제에 쓰이는 유명한 아이디어가 있는데 결론부터 말하면 구슬 개수가 $N$일 때의 정답은 $sum_i = \sum_{k=1}^{i}{a_i}$일 때, $\sum_{i = 1}^{N}{abs(sum_i - i)}$이다.
먼저, 구슬 각각의 위치를 배열에 저장한다고 생각하자. 이 배열을 정렬하면 그리디하게 정답을 구할 수 있으며, 이 배열을 $P$라 하면 답은 $\sum_{i=1}^{N}{abs(P_i - i)}$이다. 이 아이디어를 조금 변형해서 현재 칸을 지나는 구슬의 개수로 답을 생각해 보자. 현재 위치를 $i$라고 하자. 위의 아이디어 때문에 $i$이하 칸들의 구슬 중에 남는 구슬들을 오른쪽으로 옮기는 것이 최적임이 자명하다. 따라서 현재 칸에서 오른쪽으로 옮겨야 하는 구슬의 개수는 $sum_i - i$이다. 반대인 상황도 살펴 보자. 왼쪽에서 구슬이 부족하다면 오른쪽에서 부족한 만큼 옮겨와야 하기 때문에 오른쪽에서 현재 칸으로 옮겨야 하는 구슬의 개수는 $i - sum_i$이다. 따라서, 어느 쪽에 구슬이 남는지에 상관 없이 수식이 $abs(sum_i - i)$로 정리된다. 하나의 칸에 대해 정답을 구했으므로 모든 칸에 대해 이 값을 더해주면 정답이 된다. 따라서, 정답은 $\sum_{i = 1}^{N}{abs(sum_i - i)}$이며, 다음과 같이 간편하게 구현할 수 있다.
int ans = 0, sum = 0;
for (int i = 1; i <= n; i++) {
sum += a[i] - 1;
ans += abs(sum);
}
이제, 구슬의 개수가 $N$일 때의 정답을 알게 되었다. 이를 바탕으로 구슬의 개수가 $N+1$개일 때를 살펴 보자. 딱 하나의 지점만 2개의 구슬을 가질 것이다. 2개의 구슬을 가진 지점을 $i$라고 하자. $i$ 미만의 범위에서는 구슬이 $N$개일 때와 답이 같음을 알 수 있다. 마찬가지로 $i$ 이상인 지점에서 생각해 보면, 왼쪽에서 필요한 구슬은 $i+1$개일 것이다. 따라서, 왼쪽에서 남는 구슬이 있는 경우는 $sum_i - (i + 1)$, 구슬이 부족한 경우는 $(i + 1) - sum_i$임을 알 수 있다. 따라서 $i$미만인 경우에는 기존과 같이 처리하고, $i$이상이 경우에만 $1$을 추가로 빼주는 것으로 구현할 수 있다. 어떤 지점이 $i$가 될 것인지는 누적합을 이용하면 선형에 탐색할 수 있다.
마지막으로, 구슬의 개수가 $N+2$개일 때를 살펴 보자. 이 때는 한 칸에 구슬이 3개 있는 경우와, 두 칸에 구슬이 각각 2개씩 있는 경우, 2개로 나뉘어진다. 한 칸에 구슬이 3개 있는 경우는 구슬이 $N+1$개 있는 경우와 마찬가지로 처리할 수 있고, 두 칸에 구슬이 각각 2개 있는 경우는 suffix minimum을 통해 최솟값을 구할 수 있다. 자세한 구현은 하단의 코드를 참고하면 된다. 시간복잡도는 $O(N)$이다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll INF = 1LL << 61;
void init() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
void solution() {
ll n;
cin >> n;
vector<ll> a(n);
ll sum = 0, ans = INF;
for (auto& x : a) {
cin >> x;
sum += x;
}
vector<ll> p0(n + 1), p1(n + 1), p2(n + 1);
for (ll c = 0, i = 1; i <= n; i++) {
c += a[i - 1] - 1;
p0[i] = p0[i - 1] + abs(c);
p1[i] = p1[i - 1] + abs(c - 1);
p2[i] = p2[i - 1] + abs(c - 2);
}
if (sum == n) {
ans = p0[n];
} else if (sum == n + 1) {
ll mn = 0;
for (ll i = 1; i <= n; i++) {
mn = min(mn, p0[i] - p1[i]);
}
ans = p1[n] + mn;
} else {
vector<ll> mn(n + 2, INF);
for (ll i = n; i >= 0; i--) {
mn[i] = min(mn[i + 1], p1[i] - p2[i]);
}
ll b = 0;
for (ll i = 0; i < n; i++) {
b = min(b, p0[i] - p1[i]);
ans = min(ans, p2[n] + mn[i + 1] + b);
}
}
cout << ans;
}
int main() {
init();
ll tc;
cin >> tc;
for (ll t = 1; t <= tc; t++) {
cout << "Case #" << t << '\n';;
solution();
cout << '\n';
}
return 0;
}2번 풀이
전형적인 세그먼트 트리 + 스위핑으로 풀 수 있는 문제였지만, 구현이 꽤 까다로웠던 문제다. 예외 처리할 것도 있어서 5번이나 틀린 끝에 만점을 받을 수 있었다.
우선, 열을 기준으로 탐색할 것이기 때문에 열을 좌표압축하자. 위쪽에서 열을 하나씩 탐색한다고 생각해 보자. 붓들은 왼쪽 끝과 오른쪽 끝을 갖는 쿼리로 생각할 수 있고, 널빤지들은 한 번 나타났다가 사라질 것이다. 널빤지들이 몇 번째 열에서 나타나는지를 관리하고, 몇 번째 열에서 사라지는지를 인접 리스트로 관리하면 널빤지들은 쉽게 관리할 수 있다. 붓질의 경우 조금 더 복잡한데, 우선 겹치는 경우가 있을 수 있기 때문에 같은 열에 있는 붓들 중에서 겹치거나 완전히 포합되는 것들은 set을 이용해서 합쳐 주었다. 이 부분은 각자의 구현 방법이 있을 수 있다.
이제, 현재 열에 존재하는 널빤지들을 알 수 있으므로, 구간에 대한 붓질 쿼리를 주는 것으로 문제를 해결할 수 있다. 따라서, 열을 기준으로 스위핑하면서 세그먼트 트리를 사용하면 칠해진 칸의 개수는 쉽게 구현할 수 있다. 한편, 최소 붓질 횟수를 구하는 것이 꽤 까다롭다. 우선, 현재 한 번의 구간으로 처리할 수 있다면 한 번의 붓질에 가능함은 자명하다. 한편, 같은 열의 이전 구간과 현재 구간 사이에 널빤지가 하나도 없다면 한 번의 붓질로 칠하는 것이 가능하다. 각 구간의 개수를 더해 주되, 이전 구간의 끝점과 현재 구간의 시작점 사이에 널빤지가 없다면 1을 빼주면 된다. 여기서 현재 구간에 널빤지가 하나도 없는 경우를 처리하는 것을 유의하자. 시간복잡도는 $O(NlogN)$이다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using tll = tuple<ll, ll, ll>;
constexpr ll INF = 1LL << 61;
constexpr ll MAX = 1 << 17;
void init() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
array<ll, MAX << 1> tree;
void update(ll idx, ll val) {
tree[idx |= MAX] = val;
while (idx >>= 1) {
tree[idx] = tree[idx << 1] + tree[idx << 1 | 1];
}
}
ll query(ll s, ll e) {
ll r = 0;
for (s |= MAX, e |= MAX; s < e; s >>= 1, e >>= 1) {
if (s & 1) r += tree[s++];
if (e & 1) r += tree[--e];
}
return r;
}
void solution() {
tree.fill(0);
ll n, m;
cin >> n >> m;
vector<ll> rs;
vector<pll> p(n);
for (auto& [l, r] : p) {
cin >> l >> r;
l--;
rs.emplace_back(l);
rs.emplace_back(r);
}
vector<tll> c(m);
for (auto& [i, l, r] : c) {
cin >> i >> l >> r;
i--, l--;
rs.emplace_back(i);
}
ranges::sort(rs);
rs.erase(ranges::unique(rs).begin(), rs.end());
auto index = [&](ll x) {
return ranges::lower_bound(rs, x) - rs.begin();
};
for (auto& [l, r] : p) {
l = index(l), r = index(r);
}
ll sz = ssize(rs);
vector<set<pll>> byr(sz);
for (auto& [i, l, r] : c) {
i = index(i);
byr[i].emplace(l, r);
}
for (auto& st : byr) {
for (auto s = st.begin(); s != st.end();) {
auto e = next(s);
ll nl = s -> first, nr = s -> second;
while (e != st.end() and e -> first <= nr) {
nr = max(nr, e++ -> second);
}
st.erase(s, e);
s = e;
st.emplace(nl, nr);
}
}
vector<vector<ll>> on(sz), off(sz);
for (ll i = 0; i < n; i++) {
auto [l, r] = p[i];
on[l].emplace_back(i);
off[r].emplace_back(i);
}
ll ans = 0, cnt = 0;
for (ll i = 0; i < sz; i++) {
for (auto& x : on[i]) {
update(x, 1);
}
for (auto& x : off[i]) {
update(x, 0);
}
if (byr[i].empty()) continue;
ll pr = -1;
for (auto& [l, r] : byr[i]) {
ll s = query(l, r);
if (s == 0) continue;
ans += s, cnt++;
if (pr != -1) cnt -= !query(pr, l);
pr = r;
}
}
cout << ans << ' ' << cnt;
}
int main() {
init();
ll tc;
cin >> tc;
for (ll t = 1; t <= tc; t++) {
cout << "Case #" << t << '\n';;
solution();
cout << '\n';
}
return 0;
}3번 풀이
이 문제도 구현이 꽤나 까다로웠다. 풀이는 30분만에 나왔지만 구현에서 미친듯이 실수하는 바람에 7번이나 틀렸고, 장장 4시간만에 맞을 수 있었다.
일반성을 잃지 않고 $K_1 < K_2$라 하자. 2번 그룹만 있는 경우에는 투포인터를 이용해서 가장 큰 원소와 가장 작은 원소의 차이가 $K_2$을 넘지 않도록 관리해 주면 정답을 찾을 수 있으며, 1번 그룹까지 모두 포함하는 경우에도 마찬가지로 차이가 $K_1$을 넘지 않도록 관리해 준다면 정답을 찾을 수 있다.
마지막 경우의 수를 나타낸 그림이다. 이러한 경우에는 $r-l > K_1$인 경우에도 두 그룹이 공존하는 것이 가능하다. 즉, 2번 그룹은 $l$이상 $r$이하인 원소들만 세어 주고, 1번 그룹은 $r-K_1$이상, $l+K_1$이하인 원소들만 세어 주면 된다. 이제 최댓값을 찾아야 하는데, $r$을 기준으로 순회하며 어떤 $l$이 최적이 되는지 생각해 보자. 두 그룹의 누적합을 구해 놓는다면 수식을 $l$로 표현된 식과 $r$로 표현된 식으로 분리할 수 있고, 범위에 맞는 $l$로 표현된 식들 중 최댓값을 더해 주면 현재 $r$에 대한 최댓값을 얻을 수 있다. 이는 덱을 이용한 구간 최댓값 트릭을 사용해도 되고, set이나 segment tree를 사용해도 된다. 모든 $r$에 대해 최댓값을 구해서 위의 두 경우와 max연산을 하면 정답을 구할 수 있다. 시간복잡도는 $O(N)$ 또는 $O(NlogN)$이다. 내 구현은 대회 중에 한 것이기 때문에 상당히 난잡한데, 훨씬 깔끔하게 구현할 수 있을 것이다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void init() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
void solution() {
ll n;
cin >> n;
map<ll, vector<ll>> mp;
vector<ll> as(1, -INF);
for (ll v, k, i = 0; i < n; i++) {
cin >> v >> k;
mp[k].emplace_back(v);
as.emplace_back(v);
}
auto [k1, v1] = *mp.begin();
if (ssize(mp) == 1) {
ll ans = 0;
ranges::sort(v1);
for (ll s = 0, e = 0; e < n; e++) {
while (v1[e] - v1[s] > k1) s++;
ans = max(ans, e - s + 1);
}
cout << ans;
return;
}
auto [k2, v2] = *++mp.begin();
ll ans = 0;
ranges::sort(as);
for (ll s = 1, e = 1; e <= n; e++) {
while (as[e] - as[s] > k1) s++;
ans = max(ans, e - s + 1);
}
ranges::sort(v2);
for (ll s = 0, e = 0; e < ssize(v2); e++) {
while (v2[e] - v2[s] > k2) s++;
ans = max(ans, e - s + 1);
}
as.erase(ranges::unique(as).begin(), as.end());
auto left = [&](ll x) {
return ranges::lower_bound(as, x) - as.begin();
};
auto right = [&](ll x) {
return ranges::upper_bound(as, x) - as.begin() - 1;
};
ll sz = ssize(as);
vector<ll> ps1(sz), ps2(sz);
for (auto& x : v1) {
x = left(x);
ps1[x]++;
}
for (auto& x : v2) {
x = left(x);
ps2[x]++;
}
for (ll i = 1; i < sz; i++) {
ps1[i] += ps1[i - 1];
ps2[i] += ps2[i - 1];
}
vector<ll> l1(sz), r1(sz), l2(sz), r2(sz);
for (ll i = 0; i < sz; i++) {
l1[i] = left(as[i] - k1);
r1[i] = right(as[i] + k1);
l2[i] = left(as[i] - k2);
r2[i] = right(as[i] + k2);
}
multiset<ll> st;
for (ll s1 = 1, s2 = 1, e = 1; e < sz; e++) {
while (as[e] - as[s2] >= k1) {
st.emplace(ps1[r1[s2]] - ps2[s2 - 1]);
s2++;
}
while (as[e] - as[s1] > k2) {
st.erase(st.find(ps1[r1[s1]] - ps2[s1 - 1]));
s1++;
}
ll val = ps2[e] - ps1[l1[e] - 1];
if (!st.empty()) {
ans = max(ans, val + *st.rbegin());
}
}
cout << ans;
}
int main() {
init();
ll tc;
cin >> tc;
for (ll t = 1; t <= tc; t++) {
cout << "Case #" << t << '\n';;
solution();
cout << '\n';
}
return 0;
}
4번 풀이
만점자가 12명밖에 없는 만큼 어려운 문제였는데, 부분점수를 받으려고 짠 코드가 여유롭게 통과되어서 당황했다. 생각해 보니 상수가 매우 좋은 편이라 통과하는 것이 이상하지 않기도 한데, 이게 출제자의 의도인지는 잘 모르겠다. 대회가 끝난 후 더 좋은 시간복잡도의 풀이가 존재한다는 얘기를 들었는데, 이게 정해일 것 같다.
먼저, 하나의 관찰이 필요하다. 결론적으로 최댓값을 갖는 정점 쌍이 있다면 이 쌍은 무조건 그래프 상에서 간선 하나로 연결되어 있다. 증명은 위 과정을 참고하자.
이제, 각 트리의 간선에 대해 해당 간선을 대체할 수 있는 간선을 판별하는 방법을 알아보자. 트리를 이루는 한 간선이 $(u, v)$라 하고, 일반성을 잃지 않고 $u$가 $v$의 부모라 하자. 새로 추가될 간선은 한쪽 끝이 $v$의 서브트리에 있고 다른 한쪽 끝이 $v$의 서브트리에 있지 않아야 하며, 이는 ETT를 이용하면 쉽게 할 수 있다.
이때, 모든 쌍을 다 검사해야 할까? 쪼개진 컴포넌트 내부를 잇는 간선은 검사하지 않아도 되므로 미리 구해 놓는다. 따라서 간선들 중 쪼개진 두 컴포넌트를 잇는 간선들만 취사해서 없어진 간선을 대체할 수 있는 간선들과 $O(M^2)$만큼 비교하면 된다. 트리 상의 거리는 $N$이 작으므로 모든 정점 쌍에 대해 전처리하면 된다. 총 시간복잡도는 $O(NM^2)$인데, 여기서 $O(NMlogM)$으로 줄이는 방법이 있다고 한다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;
using tll = tuple<ll, ll, ll>;
constexpr ll INF = 1LL << 61;
void init() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
void solution() {
ll n, m;
cin >> n >> m;
vector<tll> edg(m + 1);
vector<vector<tll>> gr(n + 1);
for (ll i = 1; i <= m; i++) {
auto& [u, v, w] = edg[i];
cin >> u >> v >> w;
gr[u].emplace_back(v, w, i);
gr[v].emplace_back(u, w, i);
}
vector<ll> te(n - 1);
vector<bool> con(m + 1);
for (auto& x : te) {
cin >> x;
con[x] = true;
}
vector<ll> dep(n + 1), in(n + 1), out(n + 1), par(n + 1);
ll cnt = 0;
function<void(ll, ll)> dfs1 = [&](ll cur, ll pre) {
in[cur] = cnt++;
for (auto& [nxt, w, i] : gr[cur]) {
if (nxt == pre or !con[i]) continue;
dep[nxt] = dep[cur] + 1;
par[nxt] = cur;
dfs1(nxt, cur);
}
out[cur] = cnt;
};
dfs1(1, 0);
vector td(n + 1, vector<ll>(n + 1));
vector<ll> tmp(n + 1);
function<void(ll, ll)> dfs2 = [&](ll cur, ll pre) {
for (auto& [nxt, w, i] : gr[cur]) {
if (nxt == pre or !con[i]) continue;
tmp[nxt] = tmp[cur] + w;
dfs2(nxt, cur);
}
};
for (ll i = 1; i <= n; i++) {
tmp[i] = 0;
dfs2(i, 0);
td[i] = tmp;
}
auto sub = [&](ll u, ll v) {
return in[u] <= in[v] and in[v] < out[u];
};
for (auto& i : te) {
if (!con[i]) continue;
auto [u, v, w] = edg[i];
if (dep[u] > dep[v]) swap(u, v);
ld ans = 1e100, b = 0;
vector<tll> cross, pos;
for (ll j = 1; j <= m; j++) {
auto [x, y, nw] = edg[j];
if (sub(v, x) xor sub(v, y)) {
if (sub(v, x)) swap(x, y);
cross.emplace_back(x, y, nw);
if (!con[j]) pos.emplace_back(x, y, nw);
} else {
b = max(b, ld(td[x][y]) / ld(nw));
}
}
for (auto& [u, v, w] : pos) {
ld cur = b;
for (auto& [x, y, nw] : cross) {
cur = max(cur, ld(td[u][x] + w + td[y][v]) / ld(nw));
}
ans = min(ans, cur);
}
if (pos.empty()) {
cout << "-1 ";
} else {
cout << ans << ' ';
}
}
}
int main() {
init();
ll tc;
cin >> tc;
for (ll t = 1; t <= tc; t++) {
cout << "Case #" << t << '\n';;
solution();
cout << endl;
}
return 0;
}5번 부분점수 풀이는 따로 업로드하지 않겠다.
'대회 후기' 카테고리의 다른 글
| 2025 ICPC Seoul Regional 본선 후기 (2) | 2025.11.26 |
|---|---|
| 2025 숭고한 연합 알고리즘 경진대회 후기 (2) | 2025.09.02 |
| SCPC 2025 본선 후기 (0) | 2025.09.02 |
| SCPC 2025 1차 예선 후기 (0) | 2025.09.01 |
| 2025 KAIST RUN Spring Contest 후기 (0) | 2025.05.31 |
