UCPC 예선 업솔빙 후기
서론
나는 현재 대학생 신분이 아니므로 UCPC, ICPC에 참가할 수 없다. 원래 같으면 다른 친구와 팀을 이뤘을 텐데(대학을 갔더라면 하는 행복한 상상), 이번에는 그럴 수 없게 되어 원래 혼자 UCPC 예선을 업솔빙하려고 했는데… 가만 보니 같이 암호학 스터디를 하는 000wan과 함께 나가면 괜찮을 것 같단 생각이 들어, 함께 2명이서 백준 연습을 켜고 UCPC를 업솔빙하게 되었다. 결과적으로 말하면 6솔, 패널티까지 합하면 본선까진 못 갈 점수지만 2명이서 했다는 점과 내가 PS를 꽤 많이 놓았다는 점을 고려하면 괜찮은 것 같다. 후술하겠지만, 이번 예선은 G, H 중 무엇을 얼마나 빨리 푸느냐에 따라 본선 진출 여부가 결정된 것 같은데, 그래도 하나 풀었다는 데 의의를 두면 좋을 것 같다.
Timeline
00:00 ~ 00:01: A번을 풀고 그냥 제출했다. 영완이는 B를 보기 시작했다.
00:01 ~ 00:10: 영완이가 B를 풀었고, 나는 C가 어렵다고 판단, D를 보기 시작했다.
00:10 ~ 01:34: 나는 D번에 막혀있었고, 영완이는 E를 보고 있었다. 영완이는 E를 segment tree + 구간 합으로 이용해서 풀면 될 것 같다고 했지만, 결과적으로 로그제곱의 풀이였고, 난 그걸 한 번도 짜본 적이 없었다. 중간에 D 코딩을 영완이에게 시킬까 고민하면서 (D 풀이 자체는 10분 정도 걸리고 바로 냈다) 풀이를 설명해주었지만, 좌표 압축을 둘 다 한 번도 안 짜본 이슈와 함께 영완이가 포기함으로써 온전히 내게 몫이 맡겨지게 되었다. 한편, 난 D에서 코딩이 너무 어렵다고 판단(최소 플래급 코딩이라고 생각했다 - 하지만 내 착각이었고, 그냥 오랜만에 PS해서 코딩 실력이 망한 거였다), E를 봤고 $O(N^2)$ 풀이를 생각했다. 근데 고민해보니, E번의 풀이가 amortized $O(N\log 10^9)$이 보장되는 것 같았고, 실제로 증명할 수 있었다! 이 상태에서, D에 대한 코딩 계획을 구체화시켰고, D를 마저 코딩하고 (말 그대로 왔다갔다 정신이 없는 상태였다 - 스코어보드를 보니 점점 불안감은 밀려만 왔다) E를 코딩했고, 90분에 D, 94분에 E를 각각 1 try만에 맞았다.
01:34 ~ 03:00: I는 무조건 풀어야 하는 것 같았고, G/H 중 하나를 골라야 하는 것 같았다. H는 영완이에게 맡겼고, I는 내가 봤는데, 생각보다 발상이 쉬웠고, 증명도 쉬웠다. 하지만 문제는 코딩이었는데, union-find를 써야할 것 같았다. 오랜만에 짜보는 자료구조라, 막힐 뻔 했지만 union-find는 내가 자신있는 자료구조 중 하나였기 때문에 짜는 데 별 문제가 없었다. 근데 union-find 말고도 flood-fill 쪽에서 꽤나 tricky한 구현 문제가 좀 있어 2번 틀리고 겨우 맞았다. 이쯤 돼서 예전 코딩 폼이 좀 올라와서, 꽤나 구현이 자유자재로 되는 듯한 느낌이 들었다. 이제 G, H를 봐야 했는데, 영완이는 gg를 친 상태였고, 내가 둘 다 봐야하는 상태였다. 근데 G가 좀 익숙한 문제였는데, 출처는 기억이 안 나지만 dp + 세그를 박으면 되는 문제였고, TLE를 받았다. 근데 고민을 곰곰히 해 보니, 그냥 dp로도 될 것 같았고, 코딩해서 AC를 받았다. H는 결국 풀지 못했고, 2시간 반만에 그냥 컴퓨터를 껐다.
- H를 업솔빙했다. 생각보다 쉬운 듯.
문제별 풀이
A번: 체육은 수학과목 입니다 2
그냥 input 4개가 1500 이하인지 아닌지 체크하면 된다.
B번: 도미노 게임
관찰 1: 게임을 오래 진행하기 위해서는 인접한 두 칸 중 하나가 0이고, 나머지 하나가 0이 아닌 칸일 때가 최적이다.
처음부터 0인 칸이 있으면 관찰 1에 따라 모든 칸의 수들의 합이 답이 된다.
하지만, 0인 칸이 없으면, 0인 칸을 만들어줘야 한다. 0인 칸을 가장 적은 횟수로 만드는 방법은 최솟값을 포함하는 칸과 인접한 아무 칸을 골라 각각에서 1을 빼는 것을 반복하는 것이므로, 두 경우 모두에서 답은 (전체 칸의 합) - (전체 칸의 최솟값)이 된다.
D번: 연산 추가하기
우선 구간을 전부 수직선 위에 표현하였을 때, “빈 구간”을 찾자. 빈 구간을 찾은 후, 각 구간의 길이를 배열에 담자.
관찰 1: T(소요 사이클 수)가 1부터 증가할 때, i에서 i+1로 증가할 때 감소하는 시나리오의 수를 살펴보자. 이 값들은 최대 $O(N)$번 변한다.
이 관찰을 통해, 감소하는 시나리오의 수들이 변화하는 지점의 index들을 저장한 뒤에 이분 탐색을 하면 문제를 $O((N+Q)\log N)$에 풀 수 있다.
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, H; cin >> N >> H;
map<int, int> events;
events.insert({1, 0});
events.insert({H+1, 0});
for (int i = 0; i < N; i++) {
int a, b; cin >> a >> b;
events[a] += 1;
events[b+1] -= 1;
}
vector<int> gaps;
int active = 0, prev = 1;
for (auto &kv : events) {
int x = kv.first, d = kv.second;
if (prev < x && active == 0) gaps.push_back(x - prev);
active += d;
prev = x;
}
sort(gaps.begin(), gaps.end());
int M = gaps.size();
vector<long long> suf(M+1);
for (int i = M-1; i >= 0; i--) suf[i] = suf[i+1] + gaps[i];
int Q; cin >> Q;
while (Q--) {
int T; cin >> T;
int idx = lower_bound(gaps.begin(), gaps.end(), T) - gaps.begin();
if (idx == M) cout << 0 << "\n";
else {
long long cnt = M - idx;
long long ans = suf[idx] - cnt * (T - 1);
cout << ans << "\n";
}
}
return 0;
}
E번: 콘서트
임의의 위치 $c-1$과 $c$ 사이에서 소음 $x$의 콘서트가 발생했을 때, 소음이 오른쪽으로 퍼지는 상황만 고려하자. c번 방음벽에 대해서, 다음의 두 가지 경우가 존재한다.
- $D_c < x$: 콘서트가 종료된 뒤 $D_c$의 값은 2배가 됨. 나머지 소음은 c+1로 넘어감.
- 모든 소음이 c번 방음벽에 흡수됨.
관찰 1: $x\le 10^9$이므로, 각 방음벽이 두 배씩 커지는 상황이 최대 $\log 10^9$만큼 일어남.
즉, 각 쿼리를 그냥 Naive하게 처리하면 된다. 시간 복잡도는 $O(Q+N\log 10^9)$가 된다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N; cin >> N;
vector<long long> D(N+1);
for (int i = 1; i <= N; i++) cin >> D[i];
int Q; cin >> Q;
while (Q--) {
int t, c; cin >> t >> c;
if (t == 1) {
long long x; cin >> x;
long long rem = x;
for (int i = c; i >= 1 && rem > 0; i--) {
long long a = min(rem, D[i]);
D[i] += a;
rem -= a;
}
rem = x;
for (int i = c+1; i <= N && rem > 0; i++) {
long long a = min(rem, D[i]);
D[i] += a;
rem -= a;
}
} else {
cout << D[c] << "\n";
}
}
return 0;
}
G번: 스마트 창고
어떤 세로 범위를 고정시키자. 이 상태에서, 열별로 lazy 세그먼트 트리를 두어 구간 업데이트를 하는 방식이 다음과 같은 첫 번째 코드이다.
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
const long long INF = -(1LL<<60);
int N, M;
static int A[500][500];
static long long answ[500][500], tag[500][2005];
static long long colSum[500], leftv[500], rightv[500], bestv[500];
void update(int c, int idx, int l, int r, int ql, int qr, long long v) {
if (qr < l || r < ql) return;
if (ql <= l && r <= qr) {
tag[c][idx] = max(tag[c][idx], v);
return;
}
int m = (l + r) >> 1;
update(c, idx<<1, l, m, ql, qr, v);
update(c, idx<<1 | 1, m+1, r, ql, qr, v);
}
void propagate(int c, int idx, int l, int r, long long cur) {
cur = max(cur, tag[c][idx]);
if (l == r) {
answ[l][c] = max(answ[l][c], cur);
} else {
int m = (l + r) >> 1;
propagate(c, idx<<1, l, m, cur);
propagate(c, idx<<1 | 1, m+1, r, cur);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> M;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> A[i][j];
answ[i][j] = A[i][j];
}
}
for (int c = 0; c < M; c++) {
for (int i = 1; i < 4*N; i++) {
tag[c][i] = INF;
}
}
for (int r1 = 0; r1 < N; r1++) {
fill(colSum, colSum + M, 0LL);
for (int r2 = r1; r2 < N; r2++) {
for (int c = 0; c < M; c++) {
colSum[c] += A[r2][c];
}
leftv[0] = colSum[0];
for (int c = 1; c < M; c++) {
leftv[c] = max(colSum[c], leftv[c-1] + colSum[c]);
}
rightv[M-1] = colSum[M-1];
for (int c = M-2; c >= 0; c--) {
rightv[c] = max(colSum[c], rightv[c+1] + colSum[c]);
}
for (int c = 0; c < M; c++) {
bestv[c] = leftv[c] + rightv[c] - colSum[c];
update(c, 1, 0, N-1, r1, r2, bestv[c]);
}
}
}
for (int c = 0; c < M; c++) {
propagate(c, 1, 0, N-1, INF);
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cout << answ[i][j] << (j+1 == M ? '\n' : ' ');
}
}
return 0;
}
하지만 $\log$ 덕분에 시간 초과를 받는다. 더 나은 방법이 필요하다. 생각해보면 위 코드에서 curMax만 유지하여 답을 즉시 갱신하면 됨을 관찰할 수 있고, 그러면 위의 $O(N^2M\log N)$에서 $O(N^2M)$으로 시간복잡도가 줄어든다.
#include<iostream>
#include<vector>
#include<algorithm>
#include<limits>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M; cin >> N >> M;
vector<vector<int>> A(N, vector<int>(M));
vector<vector<long long>> ans(N, vector<long long>(M));
vector<vector<long long>> sumBelow(N + 1, vector<long long>(M, 0));
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> A[i][j];
ans[i][j] = A[i][j];
}
}
for (int i = N - 1; i >= 0; i--) {
for (int j = 0; j < M; j++) {
sumBelow[i][j] = sumBelow[i + 1][j] + A[i][j];
}
}
const long long NEG_INF = numeric_limits<long long>::min();
vector<long long> colSum(M), curMax(M), leftv(M), rightv(M), bestv(M);
for (int r1 = 0; r1 < N; r1++) {
for (int j = 0; j < M; j++) {
colSum[j] = sumBelow[r1][j];
curMax[j] = NEG_INF;
}
for (int r2 = N - 1; r2 >= r1; r2--) {
if (r2 < N - 1) {
for (int j = 0; j < M; j++) colSum[j] -= A[r2 + 1][j];
}
leftv[0] = colSum[0];
for (int j = 1; j < M; j++) leftv[j] = max(colSum[j], leftv[j - 1] + colSum[j]);
rightv[M - 1] = colSum[M - 1];
for (int j = M - 2; j >= 0; j--) rightv[j] = max(colSum[j], rightv[j + 1] + colSum[j]);
for (int j = 0; j < M; j++) {
bestv[j] = leftv[j] + rightv[j] - colSum[j];
if (bestv[j] > curMax[j]) curMax[j] = bestv[j];
if (curMax[j] > ans[r2][j]) ans[r2][j] = curMax[j];
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cout << ans[i][j] << (j + 1 == M ? '\n' : ' ');
}
}
return 0;
}
H번: 해안선
$f$를 두 개의 호로 나누어진 영역의 정점 개수가 $i, j$일 때, 비교차 해밀턴 경로의 수라고 정의하면 점화식은 다음과 같다:
\[f(i,j)=f(i-1,j)=+f(i, j-1), f(0, j)=f(i,0)=1\]해는
\[f(i, j)=\binom{i+j}{i}\]이고,
\[|a-b|=1, |a-b|\neq 1\]인 경우로 나누어 다음과 같은 식을 도출할 수 있다:
\[\displaystyle\text{경로의 수}= \begin{cases} \binom{N-b+a-2}{a-2}\times 2^{b-a-1} & (|a-b|\neq 1) \\ \\ \binom{N-b+a-2}{a-2}\times 2^{N-3} & (|a-b|=1) \end{cases}\]#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1000000007;
ll mod_pow(ll a, ll e = MOD-2) {
ll r = 1;
while (e) {
if (e & 1) r = r * a % MOD;
a = a * a % MOD;
e >>= 1;
}
return r;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, a, b;
cin >> N >> a >> b;
if (a > b) swap(a, b);
vector<ll> fact(N+1), ifact(N+1);
fact[0] = 1;
for (int i = 1; i <= N; i++)
fact[i] = fact[i-1] * i % MOD;
ifact[N] = mod_pow(fact[N]);
for (int i = N; i > 0; i--)
ifact[i-1] = ifact[i] * i % MOD;
auto comb = [&](int n, int k) -> ll {
if (k < 0 || k > n) return 0;
return fact[n] * ifact[k] % MOD * ifact[n-k] % MOD;
};
int gap = b - a - 1;
ll C = comb(N - b + a - 2, a - 2);
ll ans;
if (gap != 0) {
ans = C * mod_pow(2, gap) % MOD;
} else {
ans = (C + mod_pow(2, N-3)) % MOD;
}
cout << ans << "\n";
return 0;
}
I번: 로봇 청소기
우선 최댓값은 $N$임은 자명하다(좌표를 보면 알 수 있다). 최솟값의 경우, 최대한 붙이는 것이 이득이기에 만약 strictly increase하면 x좌표가 같다 하고, 그렇지 않으면 x좌표가 1 차이나도록 설정해주면 된다. 이후 해야할 작업은 DSU + flood-fill로, Union-find 후 전체 영역의 개수를 세주면 된다.
#include <iostream>
#include <vector>
using namespace std;
struct DSU {
vector<int> p, r;
DSU(int n) : p(n), r(n, 0) {
for (int i = 0; i < n; i++) p[i] = i;
}
int find(int x) {
return p[x] == x ? x : p[x] = find(p[x]);
}
void unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return;
if (r[a] < r[b]) swap(a, b);
p[b] = a;
if (r[a] == r[b]) r[a]++;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
vector<long long> y(N);
for (int i = 0; i < N; i++) {
cin >> y[i];
}
vector<int> x(N, 0);
for (int i = 1; i < N; i++) {
if (y[i] > y[i - 1])
x[i] = x[i - 1];
else
x[i] = x[i - 1] + 1;
}
int C = x[N - 1] + 1;
vector<vector<int>> byCol(C);
for (int i = 0; i < N; i++) {
byCol[x[i]].push_back(i);
}
DSU dsu(N);
for (int c = 0; c < C; c++) {
auto &v = byCol[c];
for (int j = 0; j + 1 < (int)v.size(); j++) {
int i1 = v[j], i2 = v[j + 1];
if (y[i2] - y[i1] == 1)
dsu.unite(i1, i2);
}
}
for (int c = 0; c + 1 < C; c++) {
auto &A = byCol[c];
auto &B = byCol[c + 1];
int p1 = 0, p2 = 0;
while (p1 < (int)A.size() && p2 < (int)B.size()) {
long long y1 = y[A[p1]];
long long y2 = y[B[p2]];
if (y1 < y2) p1++;
else if (y1 > y2) p2++;
else {
dsu.unite(A[p1], B[p2]);
p1++;
p2++;
}
}
}
vector<char> seen(N, 0);
int min_regions = 0;
for (int i = 0; i < N; i++) {
int r = dsu.find(i);
if (!seen[r]) {
seen[r] = 1;
min_regions++;
}
}
cout << min_regions << "\n"
<< N << "\n";
return 0;
}