티스토리 뷰
COI 2021을 세 시간 동안 돌았다. 원래 5시간 셋이었는데 오늘도 5시간을 내기 어려웠다. 3시간 동안 302.4122점을 받았다. 대회 3등에 해당하는 성적이다.
A. Autobahn
각 사람이 탑승한 시각, 벌금을 내기 시작해야 하는 시각(다른 조건은 무시하고 $l_i + t_i$ 만 생각), 내린 시각을 정리하면 대략 $3N$개 정도의 구간으로 전체 시간을 나눌 수 있다. 이 구간 내에서는 벌금을 내는 사람의 수와 총 벌금, 탄 사람 수 등이 모든 시각에 대해 똑같다. 그래서 좌표 압축을 하고 시작할 수 있다. 좌표 압축을 하고 나면, 가능한 모든 구간에 대해 해주면 되는데, 이때 가능한 모든 구간은 (1) 좌표압축된 점 중 하나에서 시작해 $X$의 시간 동안 이어지거나 (2) 좌표압축도니 점 중 하나에서 끝나고 시간이 $X$인 형태 중 하나이다. 만약 어중간하게 답 구간이 걸친 경우가 최적해라면, 그 구간을 왼쪽 또는 오른쪽으로 밀어서 최적해를 또 만들 수 있다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, k, x, len;
ll l[300002], t[300002], r[300002];
vector<ll> point = {-1'000'000'000, 1'000'000'000};
ll cnt[300002], sum[300002], w[300002], wsum[300002]; /// 사람 수, 벌금 사람 수
ll ans;
int main(){
scanf("%lld %lld %lld", &n, &k, &x);
for(ll i=1; i<=n; i++){
scanf("%lld %lld %lld", &l[i], &t[i], &r[i]);
r[i]++;
point.push_back(l[i]), point.push_back(r[i]);
if(l[i] + t[i] < r[i]) point.push_back(l[i] + t[i]);
}
sort(point.begin(), point.end());
point.erase(unique(point.begin(), point.end()), point.end());
len = (ll)point.size();
for(ll i=1; i<=n; i++){
ll lp = lower_bound(point.begin(), point.end(), l[i]) - point.begin();
ll mp = lower_bound(point.begin(), point.end(), min(r[i], l[i] + t[i])) - point.begin();
ll rp = lower_bound(point.begin(), point.end(), r[i]) - point.begin();
cnt[lp]++, cnt[rp]--;
sum[mp]++, sum[rp]--;
}
for(ll i=0; i<len-1; i++){
if(i) cnt[i] += cnt[i-1], sum[i] += sum[i-1];
}
for(ll i=0; i<len-1; i++){
if(cnt[i] < k) sum[i] = 0;
w[i] = sum[i] * (point[i+1] - point[i]);
wsum[i] = (i ? wsum[i-1] : 0LL) + w[i];
}
ll pnt;
for(ll i=1; i<len; i++){
pnt = upper_bound(point.begin(), point.end(), point[i] + x - 1) - 1 - point.begin();
ans = max(ans, wsum[pnt-1] - wsum[i-1] + (point[i] + x - point[pnt]) * sum[pnt]);
}
for(ll i=0; i<len-1; i++){
pnt = upper_bound(point.begin(), point.end(), point[i+1] - x) - 1 - point.begin();
if(pnt) ans = max(ans, wsum[i] - wsum[pnt] + (point[pnt+1] - (point[i+1] - x)) * sum[pnt]);
}
printf("%lld", ans);
}
B. Cigle
$DP[x][y]$를 마지막 층이 $x$에서 $y$까지의 구간인 경우 최대 점수라고 해 보자. 이렇게 하면, $DP[a][b]$에서 $DP[b+1][c]$로 넘어가는 것을 $O(N)$에 나이브하게 처리하면 네제곱 DP가 나온다. $a$와 $b$를 고정하고 $c$를 점점 키워 나가면 세제곱으로 시간 복잡도를 줄일 수 있다.
여기서 끝내지 않고, 제곱으로 줄이는 방법이 있다. 먼저 $b$를 고정하고 $a$와 $c$를 $b$에서 떨어뜨리는 방식으로 진행한다. $A \ge C$거나 $C < A$인 경우로 나눈다. (단 $A$는 $a$에서 $b$까지 누적합, $C$는 $b+1$에서 $c$까지 누적합) 각각의 경우에 대해 $A$랑 $C$를 멀리 떨어뜨리면서, 적당한 처리를 통해 각 $C$별 최댓값을 구할 수 있다. 이게 구현이 굉장히 헷갈리는 부분이 많다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int arr[5002], sum[5002];
int DP[5002][5002];
int maxV[5002];
int ans;
int main(){
scanf("%d", &n);
for(int i=1; i<=n; i++) scanf("%d", &arr[i]), sum[i] = sum[i-1] + arr[i];
for(int m=1; m<n; m++){
/// Case 1. 아래가 더 짧거나 같다
{
int s = m, maxVal = 0, match = 0, nextturn = 0;
for(int e=m+1; e<=n; e++){
if(arr[m] > sum[e] - sum[m]) continue;
if(nextturn) match++, nextturn = 0;
while(s>1 && sum[e] - sum[m] >= sum[m] - sum[s-2]){
s--;
maxVal = max(maxVal, DP[s][m] + match);
}
if(sum[e] - sum[m] == sum[m] - sum[s-1]) nextturn = 1;
DP[m+1][e] = max(DP[m+1][e], maxVal);
}
}
/// Case 2. 위가 더 짧다
{
for(int i=1; i<=m; i++) maxV[i] = max(maxV[i-1], DP[i][m]);
int s = m, match = 0, nextturn = 0;
for(int e=m+1; e<=n; e++){
if(nextturn) match++, nextturn = 0;
while(s > 1 && sum[e] - sum[m] >= sum[m] - sum[s-1]){
if(sum[e] - sum[m] == sum[m] - sum[s-1]) nextturn = 1;
s--;
}
if(s == 1 && sum[e] - sum[m] >= sum[m] - sum[s-1]) break;
DP[m+1][e] = max(DP[m+1][e], match + maxV[s]);
}
}
}
// for(int i=1; i<=n; i++) for(int j=i; j<=n; j++) printf("%d %d: %d\n", i, j, DP[i][j]);
for(int i=1; i<=n; i++) ans = max(ans, DP[i][n]);
printf("%d", ans);
}
C. Izvanzemaljci
시간 내에 못 풀었다. 핵심 관찰은 세 정사각형의 위치 관계인데, 세 정사각형 중 하나는 $x$축에 평행하거나 $y$축에 평행한 직선 하나로 다른 두 정사각형과 분리되며, 두 정사각형도 마찬가지로 분리된다. 대략 아래와 같은 두 형태를 돌린 게 가능하다.
모든 형태에 대해서 그 경계를 기준으로 이분탐색하는 방식으로 풀릴 것으로 추측된다. 경계를 적당히 잡아 A / B로 나뉘었다면, A쪽 정사각형 변 길이가 더 길면 A쪽을 줄여주고, 아니면 B쪽을 줄여주는 방식으로 이분탐색하면 될 것으로 보인다. (안 짜봐서 확실하지는 않다) 반례가 있다.
D. MalnaRISC
Batcher's odd-even mergesort를 짤 줄 아는지 물어보는 문제이다. 난 모른다. 그래서 IOI2022 Register 에서 쓰는 정렬을 그대로 구현하고 72점 정도를 받았다.