USACO 2020 January (Gold) 풀이
Intro
원래 USACO 참여할 생각이 없었는데 브론즈만 밀어야지 실버만 밀어야지 하다가 결국 골드를 키게 되었다. 중간에 뇌절파티를 많이 해서 예상보다 시간이 매우매우 많이 걸렸다. 개인적인 난이도는 2->1->3이라고 생각하나, 증명 없이 뇌를 비우고 푼다면 1번이 2번보다 더 쉬울수도 있다는 생각을 해본다. 세 문제 모두 플5에서 플3 정도의 수준이라고 생각한다.
1. Time is Mooney (time)
문제 요약
정점 1000개, 간선 2000개인 그래프가 있다. 각 정점은 1000 이하의 가중치를 가지고 있는데, 정점을 방문할 때 마다 그만큼의 점수를 얻는다(여러 번 방문해서 점수를 얻을 수 있다). 단, 사용한 간선 개수를 $t$라고 하면 주어지는 1000 이하의 정수 $c$에 대해 $ct^2$의 점수를 잃게 된다. 이때 1번 정점에서 시작해서 1번 정점으로 돌아오는 경로 중 얻을 수 있는 최대 점수를 구해야 한다.
문제 풀이
가장 먼저 생각할 수 있는 것은 간선을 하나 더 사용할 때마다 현재 사용한 간선이 $k$개라면 $c(k+1)^2-ck^2=c(2k+1)$만큼의 점수를 잃는다고 보아도 무방하다는 것이다. 따라서 최악의 경우에도 경로의 길이는 약 500을 넘지 않는다. 정점과 간선의 개수가 그렇게 많지 않기 때문에, 증명 없이 뇌를 비우고 BFS를 시도해볼 수 있다. 그래프를 다음과 같이 모델링하자.
$cache[Vertex][Time]$ : $Time$개의 간선을 이동해서 $Vertex$까지 왔을 때 얻을 수 있는 최대 수익
다익스트라와 유사한 느낌으로, (1,0)부터 시작해서 $cache$를 더 큰 값으로 갱신할 수 있을 때만 큐에 넣어 BFS를 수행하는 것을 반복해 주자. $Time$이 많아봤자 500이라는 것을 알기 때문에, 수행 시간이 그렇게 길지 않다는 것을 추측할 수 있다. 정확한 시간복잡도를 따지자면 안 돌 수도 있을 것 같으나(...) USACO 데이터가 약하다는 것은 모두가 아는 사실이기 때문에, 믿고 제출하면 AC를 받을 수 있다. 증명을 아시거나 반례 데이터를 아시는 분은 댓글로 남겨 주길 바란다.
Edit) 생각해보니까 그냥 DP를 돌리면 된다. 멍청했다.
코드
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int, int> pii;
vector<int> adj[1005];
int score[1005];
int best[1005][1005];
int main() {
freopen("time.in", "r", stdin);
freopen("time.out", "w", stdout);
int n, m, c;
scanf("%d %d %d", &n, &m, &c);
for (int i = 1; i <= n; i++) scanf("%d", &score[i]);
while (m--) {
int t1, t2;
scanf("%d %d", &t1, &t2);
adj[t1].push_back(t2);
}
queue<pii> Q;
Q.emplace(1, 0);
while (!Q.empty()) {
pii hr = Q.front(); Q.pop();
for (int th : adj[hr.x]) {
int tmp = best[hr.x][hr.y] + score[th] - c * (2 * hr.y + 1);
if (tmp <= best[th][hr.y + 1]) continue;
best[th][hr.y + 1] = tmp;
Q.emplace(th, hr.y + 1);
//printf("#%d %d %d\n", th, hr.y + 1, tmp);
}
}
int ma = 0;
for (int i = 0; i <= 1000; i++)
ma = max(ma, best[1][i]);
printf("%d", ma);
return 0;
}2. Farmer John Solves 3SUM (threesum)
문제 요약
길이가 5000 이하고 절댓값이 100만 이하인 정수 수열이 있다. 구간 쿼리가 10만개 주어지는데, 쿼리 당 구간의 수들 중 3개를 더해 0을 만들 수 있는 경우의 수를 출력하면 된다.
문제 풀이
쿼리가 상당히 많으니, 전처리를 해 두면 좋겠다. 구간에 대한 쿼리를 구해야 하니, 다음과 같은 테이블을 정의할 수 있다.
$cnt[a][b]$ : $a$를 가장 왼쪽 수로 사용하고 $b$를 가장 오른쪽 수로 사용했을 때 $a+1$번부터 $b-1$번까지의 수를 추가해서 0을 만들 수 있는 가능한 경우의 수
다른 말로 하면 범위 내에 $-a-b$가 몇 개 있는지를 세 둔 테이블이 된다. 물론 자료구조를 써서 해결할 수도 있겠지만, N이 5000으로 상당히 크고 유사코 서버는 매우 느리기 때문에 다른 관찰이 필요하다. 주목할만한 점은 수의 범위가 절댓값 100만 이하로, 상당히 작다. 따라서 어떤 수가 몇번 등장했는지를 기록해두는 배열을 둘 수 있다. 이 배열을 사용하면 $a$를 고정시켰을 때 $b$를 하나씩 늘려가면서 등장한 숫자의 등장 횟수를 기록할 수 있고 $cnt$를 총 $O(n^2)$에 채울 수 있다. 지울 때도 비슷한 방식으로 지워주면 빠르게 배열을 원상복구 할 수 있다.
이제 쿼리를 해결해 보자. 쿼리가 $(st,en)$ 형태로 들어오면, 이는 $ \sum_{i=st}^{en} \sum_{j=st}^{en} cnt[i][j] $으로 구할 수 있다. 따라서 구해놓은 $cnt$ 테이블을 2차원 부분합 배열로 변경한 다음에, 쿼리가 들어올때마다 출력해주면 된다. 복잡도는 쿼리당 $O(1)$로, 문제 전체에서 $O(n^2+q)$가 된다.
코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int X = 1000000;
ll chk[2000005];
ll cnt[5005][5005];
ll a[5005];
int main() {
freopen("threesum.in", "r", stdin);
freopen("threesum.out", "w", stdout);
int n, q;
scanf("%d %d", &n, &q);
for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
for (int i = 1; i <= n - 2; i++) {
chk[a[i + 1] + X]++;
for (int j = i + 2; j <= n; j++) {
ll l = -(a[i] + a[j]);
cnt[i][j] = chk[l + X];
chk[a[j] + X]++;
}
for (int j = i + 1; j <= n; j++) chk[a[j] + X] = 0;
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cnt[i][j] = cnt[i][j - 1] + cnt[i - 1][j] + cnt[i][j] - cnt[i - 1][j - 1];
while (q--) {
int t1, t2;
scanf("%d %d", &t1, &t2);
printf("%lld", cnt[t2][t2]-cnt[t1-1][t2]-cnt[t2][t1-1]+cnt[t1-1][t1-1]);
if (q != 1) printf("\n");
}
return 0;
}3. Springboards (boards)
문제 요약
$10^9$ 이하의 음이 아닌 정수를 좌표로 삼는 2차원 그리드가 있다. 또 시작 지점과 도착 지점이 있는 스프링이 10만개 주어지는데, 시작 지점에서 스프링을 밟으면 x좌표와 y좌표가 둘다 증가하는 도착 지점으로 날아간다. (0,0)에서 시작해서 (n,n)까지 이동하는데, 날아가지 않고 걸어가는 거리를 최대한 줄이는 것이 목표이다. 단, 걸을 때는 x좌표가 증가하거나 y좌표가 증가하면서 축에 평행하게만 이동할 수 있다.
문제 풀이
가장 먼저 해야 하는 관찰은 어차피 이동할 수 있는 경우가 스프링을 타거나 걷는 것 두 가지밖에 없고, x좌표와 y좌표 또한 각각 $n$만큼만 이동할 수 있다는 점이다. 다른 말로, 걷는 거리를 최대한 줄인다고 생각하지 말고 기본적으로 $2n$ 거리를 걷는 도중에 스프링을 통해 절약할 수 있는 거리를 최대한 늘린다고 볼 수 있다. 어떤 스프링을 탔을 때 절약할 수 있는 거리는 자명히 시작 지점과 도착 지점의 택시 거리이다. 따라서 다음과 같은 dp를 정의할 수 있다.
$dp[x]$ : $x$번째 스프링의 시작 지점에 있을 때 앞으로 도착점까지 절약할 수 있는 최대 거리
이 dp값을 효율적으로 계산하기 위해서 다음과 같은 관찰을 할 수 있다. 어떤 점에서 이동해서 탈 수 있는 스프링은, 그 점보다 시작 지점의 x좌표와 y좌표가 둘 다 큰 스프링이다. (이를 지배 스프링이라고 하자) 따라서 어떤 점이 있을 때 그 점에서의 지배 스프링을 빠르게 찾아줄 수 있어야 dp값을 효율적으로 찾을 수 있다. 다행히도, x좌표는 내림차순으로 정렬해주면 x좌표가 자신보다 더 큰 스프링만 처리했을 것이므로 상관이 없다. 그럼 y좌표가 남는데, 결국 찾아야 하는것은 자신보다 y좌표가 더 큰 스프링, 즉 지배 스프링 중 dp값이 최대인 스프링이다. 따라서 이를 y좌표에 대한 세그먼트 트리로 관리해줄 수 있다.
정리하자면, 모든 점들을 x좌표를 기준으로 정렬하고 플레인 스위핑을 하면서 점들을 볼 것이다. 만약 도착 지점이 나온다면 그 도착 지점으로부터 스프링을 타서 절약할 수 있는 최대 dp값을 찾아야 하므로, dp값을 저장하는 세그먼트 트리에 자신의 y좌표부터 $n$까지 max 쿼리를 날리고 저장해둘 수 있다. 시작 지점이 나온다면, 연결된 도착 지점에서 미리 계산해 둔 값에 이 스프링을 탐으로서 절약할 수 있는 거리를 더해서 세그먼트 트리의 자신의 y좌표에 업데이트 해줄 수 있다(이것이 이 스프링의 dp값이다). 최종적인 정답은 $2n$에서 모든 좌표에 대해 max 쿼리를 날린 결과를 뺀 것이 된다.
시간복잡도는 정렬에 $O(p \log p)$, 스위핑에 $O(p \log n)$ 이 되므로 $O(p(\log p + \log n))$이 된다. 세그먼트 트리는 동적 세그먼트 트리를 사용하였다.
코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<ll, ll> pll;
int cnt = 0;
int alloc()
{
return cnt++;
}
typedef struct node
{
ll val;
int left, right;
node() : left(-1), right(-1), val(0) {}
}Node;
Node N[10000000];
typedef struct SegmentTree
{
int n;
int root = alloc();
SegmentTree(int _n) : n(_n + 1) {}
void update(int nd, int st, int en, int idx, ll diff)
{
if (idx < st || en < idx) return;
if (st == en && st == idx)
{
N[nd].val = max(N[nd].val,diff);
return;
}
int mid = (st + en) >> 1;
ll ma = 0;
if (idx <= mid)
{
if (N[nd].left == -1)
N[nd].left = alloc();
update(N[nd].left, st, mid, idx, diff);
ma = max(ma, N[N[nd].left].val);
if (N[nd].right != -1)
ma = max(ma, N[N[nd].right].val);
}
else
{
if (N[nd].right == -1)
N[nd].right = alloc();
update(N[nd].right, mid + 1, en, idx, diff);
ma = max(ma, N[N[nd].right].val);
if (N[nd].left != -1)
ma = max(ma, N[N[nd].left].val);
}
N[nd].val = ma;
}
void update(int idx, ll diff)
{
update(root, 0, n - 1, idx, diff);
}
ll query(int nd, int st, int en, int le, int ri)
{
if (en < le || ri < st) return 0;
if (le <= st && en <= ri) return N[nd].val;
int mid = (st + en) >> 1;
ll ma = 0;
if (N[nd].left != -1) ma = max(ma, query(N[nd].left, st, mid, le, ri));
if (N[nd].right != -1) ma = max(ma, query(N[nd].right, mid + 1, en, le, ri));
return ma;
}
ll query(int le, int ri)
{
return query(root, 0, n - 1, le, ri);
}
}ST;
struct point {
ll x, y, k;
point(ll _x, ll _y, ll _k) : x(_x), y(_y), k(_k) {}
};
ll value[100005];
ll dist[100005];
int main() {
freopen("boards.in", "r", stdin);
freopen("boards.out", "w", stdout);
ll n; int p;
scanf("%lld %d", &n, &p);
vector<point> v;
for (int i = 1; i <= p; i++) {
ll t1, t2, t3, t4;
scanf("%lld %lld %lld %lld", &t1, &t2, &t3, &t4);
v.emplace_back(t1, t2, -i);
v.emplace_back(t3, t4, i);
dist[i] = t3 - t1 + t4 - t2;
}
sort(v.begin(), v.end(), [&](point a, point b) {
if (a.x == b.x) return a.y > b.y;
else return a.x > b.x;
});
ST seg(n + 1);
for (point h : v) {
if (h.k < 0) {
int th = -h.k;
seg.update(h.y, value[th] + dist[th]);
continue;
}
value[h.k] = seg.query(h.y, n);
}
printf("%lld", 2*n-seg.query(0, n));
return 0;
}여담
죽여버리고 싶은 티스토리 때문에 코드를 이미지로 올렸다.
예쁘게 코드를 올리는 방법을 아시는 분 있으면 댓글로 달아주길 바란다.
Edit) 해결됨!!!