티스토리 뷰
문제들의 난이도가 작년보다 전체적으로 높았습니다. 1회차 문제부터 쉽지 않다고 느끼는 문제들이 등장했고, 2회차부터는 모든 문제를 푸는 것도 매우 힘들어졌습니다. 특히 2회차 문제에서부터 삼분 탐색과 이분 매칭이 나오는 것은 난이도에 상당한 변화가 생겼음을 의미합니다.
문제의 퀄리티도 작년에 비해 매우 높아졌습니다. 특히 3, 4, 5회차 문제들은 한 문제 한 문제가 깊은 고민을 해야 풀 수 있는 문제였던 만큼 매우 재밌었습니다.
연습 문제
1. 최대구간합
앞에서부터의 누적 합을 구해 주면서 답을 갱신해 나가면, $O(N)$에 풀 수 있습니다. 유명한 문제이므로 간단하게 설명했습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll arr[1000002];
ll ans = LLONG_MIN;
ll sum, minSum;
int main(){
scanf("%d", &n);
for(int i=1; i<=n; i++){
scanf("%lld", &arr[i]);
sum += arr[i];
ans = max(ans, sum - minSum);
minSum = min(minSum, sum);
}
printf("%lld", ans);
}
2. 돌 밀기
작년 기출문제입니다. 시뮬레이터를 이용해 직접 답을 구할 수도 있지만, BFS 코드를 짜면 귀찮은 작업을 하지 않고도 쉽게 풀 수 있습니다. 이때 BFS의 시간 복잡도는 $O(N^2 M^2)$가 됩니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct data{
int x, y, sx, sy, d;
data(){}
data(int x, int y, int sx, int sy, int d): x(x), y(y), sx(sx), sy(sy), d(d){}
};
int n, m;
int x, y;
int sx, sy, dx, dy;
char board[62][62];
bool visited[62][62][62][62];
data recent[62][62][62][62];
char chr[4] = {'R', 'D', 'L', 'U'};
queue<data> que;
vector<char> vec;
int xx[]={0, 1, 0, -1}, yy[]={1, 0, -1, 0};
bool isInside(int a, int b, int c, int d){
return ((c==a)||(c==a+1)) && ((d==b)||(d==b+1));
}
bool isOut(int a, int b){
return a<1||a>n||b<1||b>m;
}
bool isAble(int a, int b){
for(int i=0; i<2; i++) for(int j=0; j<2; j++){
if(isOut(a+i, b+j) || board[a+i][b+j]=='X') return 0;
}
return 1;
}
int main(){
scanf("%d %d", &n, &m);
for(int i=1; i<=n; i++){
scanf("%s", board[i]+1);
}
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
if(board[i][j] == 'O') x=i, y=j;
else if(board[i][j] == '-' && !dx) dx=i, dy=j;
else if(board[i][j] == '*' && !sx) sx=i, sy=j;
}
}
que.push(data(x, y, sx, sy, 0));
visited[x][y][sx][sy] = 1;
while(!que.empty()){
data tmp = que.front();
que.pop();
int tx=tmp.x, ty=tmp.y, tsx=tmp.sx, tsy=tmp.sy, td=tmp.d;
if(tsx==dx && tsy==dy){
printf("Got answer: %d times\n", td);
while(tmp.d){
data ttmp = recent[tmp.x][tmp.y][tmp.sx][tmp.sy];
for(int i=0; i<4; i++){
if(ttmp.x+xx[i] == tmp.x && ttmp.y+yy[i] == tmp.y){
vec.push_back(chr[i]);
break;
}
}
tmp=ttmp;
}
while(!vec.empty()){
printf("%c", vec.back());
vec.pop_back();
}
break;
}
for(int i=0; i<4; i++){
/// 만약 상자 칸일 때
int ttx=tx+xx[i], tty=ty+yy[i];
if(ttx<1||ttx>n||tty<1||tty>m) continue;
if(isInside(tsx, tsy, ttx, tty)){
int ttsx=tsx+xx[i], ttsy=tsy+yy[i];
if(isAble(ttsx, ttsy) && !visited[ttx][tty][ttsx][ttsy]){
que.push(data(ttx, tty, ttsx, ttsy, td+1));
visited[ttx][tty][ttsx][ttsy] = 1;
recent[ttx][tty][ttsx][ttsy] = tmp;
}
}
else if(board[ttx][tty] == 'X') continue;
else if(!visited[ttx][tty][tsx][tsy]){
que.push(data(ttx, tty, tsx, tsy, td+1));
visited[ttx][tty][tsx][tsy] = 1;
recent[ttx][tty][tsx][tsy] = tmp;
}
}
}
}
3. UP & DOWN
인터랙티브 문제가 NYPC에 나오다니, 상당히 놀랐습니다. 풀이 자체는 simple한 이분 탐색을 이용한 쉬운 풀이이지만, 본 대회에 인터랙티브 문제가 나온다는 생각을 하니 상당히 흥미로웠습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int l=1, r=1000;
string s;
int main(){
while(l <= r){
printf("%d\n", (l+r)/2);
fflush(stdout);
cin >> s;
if(s[0] == 'C') return 0;
if(s[0] == 'U') l = (l+r)/2+1;
else r = (l+r)/2-1;
}
return 1;
}
예선 문제
1. S OR T
제목이 상당히 센스 있어 보입니다.
커서의 위치를 변수에 관리하면 $O(|S|)$에 매우 쉽게 풀 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
string s;
int ans = 0;
int main(){
cin >> s;
for(auto &X: s){
if(X == 'S') ans++;
else{
ans++;
while(ans % 4) ans++;
}
}
printf("%d", ans);
}
2. 카트라이더 별 모으기
시간을 직접 비교해도 되지만, (분 * 6000 + 초 * 100 + 백분의 일초) 의 공식으로 수 하나로 만들면 비교가 훨씬 편리해집니다. 별 몇 개를 획득하는지 판단하는 것은 쉽습니다. $O(N)$에 풀립니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int input(){
int x, y, z;
scanf("%d:%d:%d", &x, &y, &z);
return x*6000+y*100+z;
}
int t1, t2, t3;
int n;
int main(){
t1 = input();
t2 = input();
t3 = input();
scanf("%d", &n);
while(n--){
int t = input();
if(t <= t3) printf("***\n");
else if(t <= t2) printf("**\n");
else if(t <= t1) printf("*\n");
else printf(":(\n");
}
}
3. 스피드전 할까 아이템전 할까
단순 구현 문제입니다. C++의 경우 STL 내장함수 accumulate와 max_element를 사용하면 매우 간단하게 구현할 수 있습니다. 시간 복잡도는 테스트 케이스당 $O(1)$입니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t;
int arr[8];
int main(){
scanf("%d", &t);
while(t--){
for(int i=0; i<8; i++) scanf("%d", &arr[i]);
bool a=0, b=0;
if(accumulate(arr, arr+4, 0) > accumulate(arr+4, arr+8, 0)) a=1;
if(*max_element(arr, arr+4) > *max_element(arr+4, arr+8)) b=1;
if(a&&!b) printf("S\n");
else if(!a&&b) printf("I\n");
else printf("R\n");
}
}
4. 실력별 매칭
모든 유저를 실력이 $S$보다 큰 유저와 $S$보다 큰 유저로 나누고, priority queue 등의 힙 자료구조에 저장합니다.
남아 있는 유저들 중 실력이 가장 가까운 유저를 찾으려면, 실력이 $S$보다 큰 유저 중 가장 못하는 유저와 실력이 $S$보다 작은 유저 중 가장 잘하는 유저를 비교하면 됩니다. 이 과정을 $K$번 반복합니다.
시간 복잡도는 $O(K \log N)$입니다.
p.s. 추후에 알아낸 사실로, $O(N+K)$의 쉬운 풀이가 존재합니다. 방법은 투 포인터입니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int s, k;
int arr[500002];
priority_queue<pair<int, int> > pq1; /// 작은 것들
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq2; /// 큰 것들
int main(){
scanf("%d %d %d", &n, &s, &k);
for(int i=1; i<=n; i++){
scanf("%d", &arr[i]);
if(arr[i] < s) pq1.push({arr[i], i});
else pq2.push({arr[i], i});
}
while(k--){
if(pq1.empty()) printf("%d ", pq2.top().second), pq2.pop();
else if(pq2.empty()) printf("%d ", pq1.top().second), pq1.pop();
else if(s - pq1.top().first <= pq2.top().first - s) printf("%d ", pq1.top().second), pq1.pop();
else printf("%d ", pq2.top().second), pq2.pop();
}
}
5. 우승자 찾기
어떤 유저 $i$가 우승자가 될 수 있다는 것은, 아래 조건을 만족하는 구간이 존재한다는 것과 동치입니다.
- 구간의 양 끝 두 수는 $i$입니다.
- 구간에는 $i$를 제외하고 두 번 이상 나오는 수가 없습니다.
증명은 생각보다 간단한데, 만약 구간 안에 $i$ 말고 두 번 이상 나오는 수가 있다면 구간은 $i \cdots j \cdots j \cdots i$의 형태를 띠게 됩니다. 이때 $j$의 랩 타임이 $i$의 랩 타임보다 무조건 작기 때문에, $i$는 이 구간만으로는 우승할 수 없게 됩니다.
반면 이 구간 말에 $i$ 말고 두 번 이상 나오는 수가 없다면, 이 구간 내의 시간 간격을 매우 작게 줄여버리고, 이 구간 밖의 시간 간격을 매우 크게 하면 $i$가 우승하게 만들 수 있습니다. 따라서 위와 같은 구간이 있는지만 판별하면 됩니다.
수열 $x$의 각 원소 $x_i$에 대해, 자신과 같은 원소가 다음으로 나오는 시간 $r_i$를 구합니다. 그리고 $j>i$인 $j$에 대해, $r_j < r_i$인 것이 있는지 판별합니다. 그러한 것이 없다면, $x_i$번 유저는 우승 후보가 됩니다.
한 가지 처리를 더 해 주어야 하는데, $x_1$번 사람은 무조건 우승 후보입니다. 이유는 생략합니다.
시간 복잡도는 $O(K^2)$이지만, 구현 방식을 바꿔서 $O(K)$까지 줄일 수 있습니다. 하지만 이 문제에서는 불필요합니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, k;
int arr[10002];
int l[10002], r[10002];
vector<int> ans;
int main(){
scanf("%d %d", &n, &k);
for(int i=1; i<=k; i++) scanf("%d", &arr[i]);
for(int i=1; i<=k; i++){
for(int j=i+1; j<=k; j++){
if(arr[i] == arr[j]){
r[i] = j;
l[j] = i;
break;
}
}
}
for(int i=1; i<=k; i++){
if(!r[i]) continue;
bool able = 1;
for(int j=i+1; j<=k; j++){
if(r[j] && r[j] < r[i]){
able = 0;
break;
}
}
if(able) ans.push_back(arr[i]);
}
ans.push_back(arr[1]);
sort(ans.begin(), ans.end());
ans.erase(unique(ans.begin(), ans.end()), ans.end());
printf("%d\n", (int)ans.size());
for(auto &x: ans) printf("%d ", x);
}
6. 도토리를 주워라
시뮬레이터가 제공되어 있지만, 손으로 만점을 맞는 것은 사실상 불가능합니다. (하지만 이걸 해낸 사람이 있다고 합니다!) 이 문제는 DP를 이용해 풀 수 있습니다. 이 문제 풀이에서는 좌표평면과 $x, y$를 다르게 사용하겠습니다. (즉 아래로 갈수록 $x$좌표가, 오른쪽으로 갈수록 $y$좌표가 늘어납니다)
같은 행 위에서는 유저에게 막히지 않는 한 얼마든지 좌우로 움직일 수 있습니다. 이 범위를 구간이라고 하면, $(x, y)$를 포함하는 구간을 $(x, l_y) \cdots (x, r_y)$로 표현할 수 있게 됩니다. 각 좌표별로 $l_y$와 $r_y$를 찾는 것은 $O(N^2)$ 시간에 가능합니다.
$DP[x][y]$: $(x, y)$까지 가는 경로에서 주울 수 있는 도토리 개수의 최댓값으로 정의합시다. 이때 같은 구간 내에 있는 모든 칸은 $DP[x][y]$의 값이 서로 같습니다. 이 값은 아래와 같이 구해집니다.
$$DP[x][y] = cnt((x, l_y) \cdots (x, r_y)) + max(DP[x-1][l_y], \cdots, DP[x-1][r_y])$$
이때 $cnt$는 구간 내에 있는 도토리의 개수입니다. 위 값을 $O(N^2)$에 구하면, 역추적도 쉽게 할 수 있고, 문제를 풀 수 있습니다. 초기에 $(1, 1)$에서 시작하고, $(N, N)$에 도착해야 한다는 사실에 주의하며 문제를 풀도록 합시다. 시간 복잡도는 $O(N^2)$입니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
char c[55][55];
int DP[55][55];
int lLimit[55][55], rLimit[55][55];
int track[55][55];
void print(int x, int y){
if(x==1){
for(int i=2; i<=rLimit[1][1]; i++) printf("R");
return;
}
int tmp = track[x][y], tmp2 = rLimit[x-1][tmp];
print(x-1, tmp);
for(int i=tmp2-1; i>=tmp; i--) printf("L");
printf("D");
for(int i=tmp-1; i>=lLimit[x][y]; i--) printf("L");
for(int i=lLimit[x][y]+1; i<=rLimit[x][y]; i++) printf("R");
}
int main(){
scanf("%d", &n);
for(int i=1; i<=n; i++) scanf("%s", c[i]+1);
DP[0][1] = 10000;
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
if(c[i][j] == 'U') continue;
int s = j;
int e = j;
while(e<n && c[i][e+1] != 'U') e++;
j = e;
int toHere = *max_element(DP[i-1]+s, DP[i-1]+e+1);
int maxLocation = max_element(DP[i-1]+s, DP[i-1]+e+1) - DP[i-1];
int cnt = 0;
for(int k=s; k<=e; k++) if(c[i][k] == 'D') cnt++;
toHere += cnt;
for(int k=s; k<=e; k++) DP[i][k] = toHere;
for(int k=s; k<=e; k++){
lLimit[i][k] = s, rLimit[i][k] = e;
track[i][k] = maxLocation;
}
}
}
printf("도토리 개수: %d\n", DP[n][n] - 10000);
print(n, n);
}
7. 난센스 퀴즈
구현만 매우 까다로운 문제이고, 실질적으로 생각하는 난이도는 별로 높지 않았던 문제라고 생각합니다. 케이스 처리를 매우 힘들게 하신 분들이 많을 것 같은데, 사실 python의 eval 내장함수를 쓰면 간단하게 구현할 수는 있습니다.시간 복잡도는 $O(T)$입니다.
t = int(input())
for tc in range(t):
a, b, c, d = map(int, input().split())
opr = "+-*/."
for i in range(5):
for j in range(5):
if i==j:
continue
s = str(a) + opr[i] + str(b) + opr[j] + str(c)
val = eval(s)
if abs(val - d) < 0.00000001:
print(s + '=' + str(d))8. 이어달리기
먼저 시간을 백분의 일 초 단위로 환산해 정수로 만듭니다. 그리고 임의의 구간 $[x, x+999]$를 잡아서, 그 안에 넣을 수 있는 최대한 많은 팀의 수를 계산한 뒤 그 최댓값을 구하면 됩니다.
구간을 잡았을 때, 그 안에 넣을 수 있는 최대한 많은 팀 수는 쉽게 구할 수 있습니다. 먼저 시간들을 정렬한 다음, 왼쪽과 오른쪽에 포인터 두 개를 만듭니다. 포인터를 점점 안쪽으로 이동시키면서, 팀을 최대한 많이 구성하면 됩니다. 시간 복잡도는 $O(N \log N + TN)$입니다. 여기서 저는 $T=1.2 \times 10^6$으로 구현했습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int arr[402];
int input(){
int a, b, c;
scanf("%d:%d:%d", &a, &b, &c);
return a*6000+b*100+c;
}
int ans;
int main(){
scanf("%d", &n);
for(int i=1; i<=n; i++) arr[i] = input();
sort(arr+1, arr+n+1);
for(int d=0; d<1200000; d++){
int l = d, r = d+999; /// l 이상 r 이하로 최대한 많은 팀을 만들어야 한다.
int s = 1, e = n;
int cnt = 0;
while(s<e){
int tmp = arr[s] + arr[e];
if(l <= tmp && tmp <= r){
cnt++, s++, e--;
}
else if(tmp < l) s++;
else e--;
}
ans = max(ans, cnt);
}
printf("%d", ans);
}
9. 몰이 사냥
가장 왼쪽에 있는 몬스터와 오른쪽에 있는 몬스터의 위치 차이가 $R$ 이하이고, 모든 몬스터의 위치가 0 이상 $X+R$ 이 사실을 이용해, 몬스터의 위치 차이가 언제 $R$ 이하가 되는지 그 시간을 구하고, 그 시간 동안 양쪽 끝 몬스터가 0 이상 $R+X$ 이하인 곳에 있게 되는지 판별하면 됩니다.
시간을 x축, 가장 왼쪽에 있는 몬스터의 위치를 y축으로 해서 그래프를 그리면 그래프는 위로 볼록합니다. 마찬가지로 가장 오른쪽에 있는 몬스터의 위치를 y축으로 하면 그래프는 아래로 볼록합니다. 따라서 두 괴물 사이 거리의 그래프는 위로 볼록한 형태가 됩니다.
위로 볼록하기 때문에 삼분 탐색으로 볼록한 점을 찾아줄 수 있습니다. 볼록한 극점을 찾고 난 뒤, 극점을 기준으로 양쪽으로 그래프를 나눠서 다시 이분 탐색을 하면 양쪽 끝 몬스터의 위치 차이가 $R$ 이하인 구간을 찾을 수 있습니다.
여기서 위 과정을 다시 반복하면 오른쪽 끝 몬스터와 왼쪽 끝 몬스터의 위치가 0 이상 $R+X$ 이하인 구간이 언제인지 판별할 수 있고, 이 교집합을 찾아 문제를 해결할 수 있습니다. 시간 복잡도는 $O(N \log N)$입니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int x, r, n;
ll key;
ll d[100002], s[100002];
int mode = 0;
ll diff(ll t){
ll minElem = LLONG_MAX, maxElem = LLONG_MIN;
for(int i=1; i<=n; i++){
minElem = min(minElem, d[i] + s[i] * t);
maxElem = max(maxElem, d[i] + s[i] * t);
}
if(mode == 0) return maxElem - minElem;
if(mode == 1) return -minElem;
if(mode == 2) return maxElem;
exit(1);
}
ll ternarySearch(ll s, ll e){
if(e-s<=3){
ll tmp = LLONG_MAX;
ll ret = 0;
for(ll i=s; i<=e; i++){
ll tmp2 = diff(i);
if(tmp > tmp2) tmp = tmp2, ret = i;
}
return ret;
}
ll p = (s+s+e)/3;
ll q = (s+e+e)/3;
ll pDiff = diff(p);
ll qDiff = diff(q);
if(pDiff < qDiff) return ternarySearch(s, q);
return ternarySearch(p, e);
}
ll binarySearch(ll s, ll e, bool tmp){ /// tmp = 0 : \, 1 : /
ll ret = (!tmp ? e : s);
while(s <= e){
ll m = (s+e)/2;
if(diff(m) <= key){
ret = m;
if(!tmp) e = m-1;
else s = m+1;
}
else{
if(!tmp) s = m+1;
else e = m-1;
}
}
return ret;
}
int main(){
scanf("%d %d %d", &x, &r, &n);
for(int i=1; i<=n; i++){
scanf("%lld %lld", &d[i], &s[i]);
}
ll mid = ternarySearch(0, INT_MAX);
if(diff(mid) > r){
printf("F");
return 0;
}
key = r;
ll lTime = binarySearch(0, mid, 0);
ll rTime = binarySearch(mid, INT_MAX, 1);
mode = 1;
key = 0;
ll leftMid = ternarySearch(lTime, rTime);
if(diff(leftMid) > 0){
printf("F");
return 0;
}
ll leftL = binarySearch(lTime, leftMid, 0);
ll leftR = binarySearch(leftMid, rTime, 1);
mode = 2;
key = x+r;
ll rightMid = ternarySearch(lTime, rTime);
if(diff(rightMid) > x+r){
printf("F");
return 0;
}
ll rightL = binarySearch(lTime, rightMid, 0);
ll rightR = binarySearch(rightMid, rTime, 1);
if(leftR < rightL || rightR < leftL) printf("F");
else printf("T");
}
10. 탐험 로봇
서브태스크 1, 3 (50점)
$S=\min$ 일 때는 풀기 쉽습니다. 물음표를 연결 성분별로 분리한 다음에, 인접한 육지가 하나라도 있는 물음표 연결 성분은 모두 육지로, 아닌 것은 바다로 채워 주면 됩니다. 이렇게 해도 되지만, 다르게 하는 방법으로는, 육지와 인접한 물음표를 모두 육지로 만들고, 그것과 인접한 물음표를 또 육지로 만들고, ...와 같은 과정을 큐를 이용해 구현하면 됩니다. 시간 복잡도는 $O(RC)$입니다.
서브태스크 2, 4 (50점)
$S=\max$일 때도 어렵지만 풀 수 있습니다. 물음표 중 땅과 인접한 물음표들을 제거하고, 나머지 물음표들에 대해서만 생각하겠습니다. 각각의 물음표 연결 성분에서 최대로 얻어낼 수 있는 땅의 개수를 구해야 합니다.
그런데 격자점들을 정점으로, 인접한 격자점을 간선으로 이으면 이 문제는 그래프 위에서 maximum independent set을 찾는 문제와 같습니다. 심지어 그래프는 이분 그래프입니다. 따라서 maximum independent set은 minimum edge covering과 같습니다. (Konig's theorem)
minimum edge covering을 찾기 위해서는 maximum matching을 찾고 greedy하게 확장해 주면 됩니다. 이분 그래프이므로 이분 매칭을 $O(V^2)$, 즉 $O(R^2 C^2)$에 계산해 줄 수 있습니다. 그렇게 하고 나면 남는 점들이 있을 텐데, 이들의 개수를 최대 매칭에 더해 주면 답이 됩니다.
시간 복잡도는 $O(R^2 C^2)$이지만, 이분 매칭을 더 빠르게 계산하면 시간복잡도를 줄일 수 있습니다. 하지만 이 문제에서는 필요하지 않습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m;
string command;
char s[1005][1005];
int xx[] = {0, 1, 0, -1}, yy[]={1, 0, -1, 0};
int number[1005][1005], numberCntA, numberCntB;
vector<int> link[1005];
bool visited[1005][1005];
int ans;
int A[1005], B[1005];
bool vst[1005];
void dfs(int i, int j){
visited[i][j] = 1;
for(int d=0; d<4; d++){
int x = i+xx[d], y = j+yy[d];
if(x<1 || x>n || y<1 || y>m || visited[x][y] || s[x][y] != 'L') continue;
dfs(x, y);
}
}
void operateMin(){
queue<pair<int, int> > que;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
if(s[i][j] == 'L') visited[i][j] = 1, que.push({i, j});
}
}
while(!que.empty()){
pair<int, int> tmp = que.front(); que.pop();
for(int d=0; d<4; d++){
int x = tmp.first + xx[d], y = tmp.second + yy[d];
if(x < 1 || x > n || y < 1 || y > m || visited[x][y] || s[x][y] != '?') continue;
s[x][y] = 'L';
que.push({x, y});
visited[x][y] = 1;
}
}
memset(visited, 0, sizeof(visited));
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
if(!visited[i][j] && s[i][j] == 'L'){
ans++;
dfs(i, j);
}
}
}
printf("%d", ans);
exit(0);
}
bool dfs2(int x){
vst[x] = 1;
for(auto &y: link[x]){
if(B[y] == -1 || (!vst[B[y]] && dfs2(B[y]))){
A[x] = y;
B[y] = x;
return true;
}
}
return false;
}
void bipartiteMatching(){
fill(A+1, A+numberCntA+1, -1);
fill(B+1, B+numberCntB+1, -1);
for(int i=1; i<=numberCntA; i++){
if(A[i] == -1){
memset(vst, 0, sizeof(vst));
if(dfs2(i)) ans++;
}
}
}
void operateMax(){
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
if(s[i][j] != '?') continue;
for(int d=0; d<4; d++){
if(s[i+xx[d]][j+yy[d]] == 'L') s[i][j] = 'X';
}
if(s[i][j] == '?'){
if((i+j)%2==0) number[i][j] = ++numberCntA;
else number[i][j] = ++numberCntB;
}
}
}
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
if(s[i][j] != '?' || visited[i][j] || (i+j)%2) continue;
for(int d=0; d<4; d++){
if(s[i+xx[d]][j+yy[d]] == '?'){
link[number[i][j]].push_back(number[i+xx[d]][j+yy[d]]);
}
}
}
}
bipartiteMatching();
ans = numberCntA + numberCntB - ans;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
if(!visited[i][j] && s[i][j] == 'L'){
ans++;
dfs(i, j);
}
}
}
printf("%d", ans);
exit(0);
}
int main(){
scanf("%d %d", &n, &m);
cin >> command;
for(int i=1; i<=n; i++){
scanf("%s", s[i]+1);
}
if(command == "min"){
operateMin();
}
else{
operateMax();
}
}
11. 격자 게임
필승 전략을 찾아야 한다고 생각할 수도 있으나, $N \le 100$으로 제한이 작으므로 그냥 DP를 이용해도 됩니다.
$DP[x][y][z]$: 3행에 돌 $x$개, 2행에 돌 $y$개, 1행에 돌 $z$개가 있을 때 먼저 시작하는 사람이 이길 수 있으면 1, 이길 수 없으면 0으로 정의합시다. 이때 초기값 $DP[0][0][0] = 1$로 설정해 주고, $O(N^4)$에 DP table을 채울 수 있습니다. table을 채우면서 역추적 경로도 만들어줄 수 있고, 실제로 게임을 진행할 때는 역추적하면서 무조건 이기는 수만 두면 됩니다. 시간 복잡도는 $O(N^4)$입니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int x, y, z;
bool DP[102][102][102];
pair<int, int> track[102][102][102];
int main(){
scanf("%d %d %d", &z, &y, &x); /// z: 맨 윗줄, y: 둘째 줄, x: 맨 아랫줄
DP[0][0][0] = 1;
for(int i=1; i<=x; i++){
for(int j=0; j<=i && j<=y; j++){
for(int k=0; k<=j && k<=z; k++){
for(int a=1; a<=i; a++) if(!DP[a-1][min(j, a-1)][min(k, a-1)]){
DP[i][j][k] = 1;
track[i][j][k] = make_pair(1, a);
break;
}
for(int b=1; b<=j; b++) if(!DP[i][b-1][min(k, b-1)]){
DP[i][j][k] = 1;
track[i][j][k] = make_pair(2, b);
break;
}
for(int c=1; c<=k; c++) if(!DP[i][j][c-1]){
DP[i][j][k] = 1;
track[i][j][k] = make_pair(3, c);
break;
}
}
}
}
while(x>1 || y || z){
printf("%d %d\n", 4 - track[x][y][z].first, track[x][y][z].second);
fflush(stdout);
if(track[x][y][z].first == 1){
x = track[x][y][z].second - 1;
y = min(x, y);
z = min(x, z);
}
else if(track[x][y][z].first == 2){
y = track[x][y][z].second - 1;
z = min(z, y);
}
else{
z = track[x][y][z].second - 1;
}
int tmp1, tmp2;
scanf("%d %d", &tmp1, &tmp2);
if(tmp1 == 3) x = tmp2-1, y = min(x, y), z = min(x, z);
else if(tmp1 == 2) y = tmp2-1, z = min(y, z);
else z = tmp2-1;
}
}
12. 사회적 거리두기
bitmask DP를 활용해서 사람이 앉은 자리를 1, 앉지 않은 자리를 0으로 마크해 두고, DP table을 채워 나갑니다. 처리 방식에 따라 $O(N \times 3^N)$ 풀이 (SOS DP와 시간 복잡도 계산방식이 같습니다) 또는 $O(N^2 \times 2^N)$ 풀이로 나뉩니다. 전자를 활용하려면 아마 오랜 시간이 걸릴 것이고, 후자는 빠른 시간 안에 답을 구할 수 있는 알고리즘입니다. 구현 난이도도 비슷하니 $O(N^2 \times 2^N)$ 풀이를 추천드립니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, k, LIM;
bool arr[20][20];
int DP[402][1<<19];
int track[402][1<<19];
bool has[402][1<<19];
int ans;
int main(){
scanf("%d %d", &n, &k);
LIM = 1<<(n+1);
for(int i=1; i<=k; i++){
int x, y;
scanf("%d %d", &x, &y);
arr[x][y] = 1;
}
for(int i=0; i<=n*n; i++) for(int j=0; j<LIM; j++){
DP[i][j] = -1000;
}
DP[0][0] = 0;
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
int x = (i-1)*n+j;
int pv = x-1;
for(int d=0; d<LIM; d++){
if(DP[pv][d] < 0) continue;
bool canDo = !arr[i][j];
if(j!=1 && (d&(1<<n))) canDo = 0;
if((d&1) && j!=1) canDo = 0;
if(d&2) canDo = 0;
if((d&4) && j!=n) canDo = 0;
if(canDo){
int tmp = (d>>1) | (1<<n);
if(DP[x][tmp] < DP[pv][d] + 1){
DP[x][tmp] = DP[pv][d] + 1;
track[x][tmp] = d;
has[x][tmp] = 1;
}
}
if(DP[x][d>>1] < DP[pv][d]){
DP[x][d>>1] = DP[pv][d];
track[x][d>>1] = d;
has[x][d>>1] = 0;
}
}
}
}
int trkX = n*n, trkY = 0;
for(int i=0; i<LIM; i++){
if(ans < DP[n*n][i]){
trkY = i, ans = DP[n*n][i];
}
}
printf("%d\n", ans);
while(trkX){
if(has[trkX][trkY]) printf("%d %d\n", (trkX-1) / n + 1, (trkX-1) % n + 1);
trkY = track[trkX][trkY];
trkX--;
}
}
13. 물풍선 아티스트
각 위치별로, 아래 수를 계산합시다.
$P[i][j]$: 여기서 물풍선을 터뜨린다면 세기가 최대 몇인 것까지 터뜨릴 수 있는가?
위 배열을 계산했다고 가정해 봅시다. 그럼, 자명하게도 각 위치별로 최대로 터뜨리는 것이 최선의 전략입니다. 이렇게 했는데 색칠되지 않은 칸이 생긴다면, 그 칸은 어떤 방식으로도 색칠할 수 없기 때문입니다.
그렇다면, 여기서 두 가지 문제가 생깁니다. 첫 번째는 $P[i][j]$를 빠른 시간 안에 계산해야 합니다. 이것은 상하좌우로 인접한 물풍선의 개수를 센 뒤, 그 중 최솟값을 취하면 됩니다. 다른 방향은 모두 같은 방식으로 계산되니, 오른쪽 방향에 대해서만 언급하겠습니다. 먼저 물풍선을 오른쪽에서 아래로 가는 순으로, 만약 같은 가로줄에 있다면 왼쪽에서 오른쪽으로 가는 순으로 정렬합니다. 이렇게 정렬하고 나면 오른쪽 방향으로 인접한 물풍선들은 연속할 수밖에 없습니다. 따라서 간단한 이분 탐색으로 어디까지가 나와 오른쪽으로 연속한 물풍선인지를 계산해 줄 수 있습니다. 이 방식을 상하좌우에 대해 반복하면 $O(N \log N)$에 계산해 줄 수 있습니다.
두 번째는 그림을 그릴 수 있는지 판정하는 것입니다. 그런데 이것 역시 빠르게 계산할 수 있습니다. 위치 $(i, j)$에 대해서, 물풍선을 한 번 터뜨릴 때마다 자신을 포함한 오른쪽으로 연속한 $P[i][j]$개의 물풍선들에 체크를 해 줍니다. 이 과정을 상하좌우에 대해 반복해 준다면, 체크가 안 된 물풍선이 있는지 판별하는 것으로 그림을 그릴 수 있는지 알아낼 수 있습니다.
다행히도, 위에서 관찰한, 적당히 정렬을 잘 하면 오른쪽으로 연속한 물풍선들을 연속하게 할 수 있다는 성질 덕분에, 이 과정을 빠른 시간 안에 처리해줄 수 있습니다. 누적 합 기법을 사용해서, 우리가 $[l, r]$ 구간에 체크를 할 예정이라면, $l$번 물풍선에 +1을 체크하고, $r+1$번 물풍선에 -1을 체크합니다. 모든 체크가 끝난 뒤 앞에서부터 누적합을 계산하면, 이 과정을 매우 빠르게 처리할 수 있습니다. 정렬 시간을 포함하지 않는다면, 무려 $O(N)$에 처리가 가능합니다.
따라서 최종 시간 복잡도는 $O(N \log N)$이 됩니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct dat{
int x, y, p, cnt;
dat(){}
dat(int x, int y): x(x), y(y){
p = 1e7;
}
bool operator<(const dat &r)const{
return x == r.x ? y < r.y : x < r.x;
}
};
int n;
dat arr[1000002];
int tmpV[1000002];
int ans;
void calc(){
sort(arr+1, arr+n+1);
for(int i=1; i<=n; i++){
int l = 0, r = n-i, ret = 0;
while(l<=r){
int m = (l+r)>>1;
if(arr[i].x == arr[i+m].x && arr[i+m].y - arr[i].y == m){
ret = m, l = m+1;
}
else r = m-1;
}
arr[i].p = min(arr[i].p, ret);
}
}
void calc2(){
sort(arr+1, arr+n+1);
fill(tmpV+1, tmpV+n+1, 0);
for(int i=1; i<=n; i++){
if(!arr[i].p) continue;
tmpV[i]++;
tmpV[i+arr[i].p+1]--;
}
for(int i=1; i<=n; i++){
tmpV[i] += tmpV[i-1];
arr[i].cnt += tmpV[i];
}
}
void flipY(){
for(int i=1; i<=n; i++) arr[i].y = -arr[i].y;
}
void flipXY(){
for(int i=1; i<=n; i++) arr[i].y = -arr[i].y;
for(int i=1; i<=n; i++) swap(arr[i].x, arr[i].y);
}
int main(){
scanf("%d", &n);
for(int i=1; i<=n; i++){
scanf("%d %d", &arr[i].x, &arr[i].y);
arr[i].p = 1e7;
}
calc(); flipY();
calc(); flipXY();
calc(); flipY();
calc(); flipXY();
for(int i=1; i<=n; i++) if(arr[i].p) ans++;
calc2(); flipY();
calc2(); flipXY();
calc2(); flipY();
calc2(); flipXY();
for(int i=1; i<=n; i++){
if(!arr[i].cnt){
printf("-1");
return 0;
}
}
printf("%d\n", ans);
for(int i=1; i<=n; i++){
if(arr[i].p) printf("%d %d %d\n", arr[i].x, arr[i].y, arr[i].p);
}
}
14. 공격 상황 시뮬레이션
기하 문제입니다. 기하 문제 중에서는 꽤 어려운 편에 속하는 유형입니다.
먼저 아래에 있는 공격수가 앞에 오게 정렬합니다. 어떤 공격수 $i$가 $j$를 가린다는 것은 $j$의 슈팅 영역에 $i$가 있다는 것으로 정의합시다. 이떄 공격수 $i$가 $j$를 가리려면 아래 두 조건이 만족되어야 합니다. ($i<j$를 가정합니다.)
- 공격수 $j$ 기준으로, 공격수 $i$가 골대 $(B, 0)$보다 오른쪽에 있습니다.
- 공격수 $j$ 기준으로, 공격수 $i$가 골대 $(A, 0)$보다 왼쪽에 있습니다.
특이한 점은, 위 두 조건 중 하나는 반드시 성립한다는 사실입니다. 따라서 성립하지 않는 것이 1개이면, $i$가 $j$를 가리지 않는다고 할 수 있습니다. 다시 말하면, $j$보다 아래에 있는 모든 공격수 $i$에 대해, (공격수 $j$ 기준으로) 공격수가 왼쪽 골대보다 왼쪽에 있거나 오른쪽 골대보다 오른쪽에 있다면, 유효한 공격수가 됩니다. 위 두 조건 중 하나를 만족하지 않는 공격수의 수를 $P_j$라고 합시다. 이때 $P_j \neq j-1$이면 $j$번 공격수는 유효하지 않다고 할 수 있습니다.
여기서 관점을 바꿔서, 골대의 입장에서 봅시다. 골대 $(A, 0)$의 입장에서, $i<j$인 $i$ 중 $i$번 공격수가 $j$번 공격수보다 왼쪽에 있는 경우가 $k$개라면, 공격수 $j$ 기준에서 2번 기준을 만족하지 않는 공격수가 $k$명이라는 뜻이므로, $P_j$에 $k$를 더해줄 수 있습니다. 마찬가지로 골대 $(B, 0)$에 대해서도 똑같은 작업을 반복하고 나면, 유효한 공격수의 목록을 구할 수 있습니다.
위 작업은 펜윅 트리 등을 이용해서 $O(N \log N)$에 처리할 수 있습니다. 자세한 구현은 코드를 참고하세요.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct vector2{
ll x, y; int idx;
vector2(){}
vector2(ll x, ll y): x(x), y(y){}
vector2 operator-(const vector2 &r)const{
return vector2(x-r.x, y-r.y);
}
ll cross(const vector2 &r)const{
return x*r.y - y*r.x;
}
bool operator<(const vector2 &r)const{
return y==r.y ? x<r.x : y<r.y;
}
};
ll ccw(vector2 a, vector2 b){
return a.cross(b);
}
ll ccw(vector2 a, vector2 b, vector2 c){
return (b-a).cross(c-a);
}
int n; ll A, B;
vector2 arr[300002];
int AIdx[300002], BIdx[300002];
int sum[300002];
vector2 vecA, vecB;
struct Fenwick{
ll tree[300002];
void add(int x, ll y){
while(x <= n){
tree[x] += y;
x += x&(-x);
}
}
ll getSum(int x){
ll ret = 0;
while(x){
ret += tree[x];
x -= x&(-x);
}
return ret;
}
ll getSum(int s, int e){
return getSum(e) - getSum(s-1);
}
} treeA, treeB;
int ans;
int main(){
scanf("%d %lld %lld", &n, &A, &B);
vecA = vector2(A, 0), vecB = vector2(B, 0);
for(int i=1; i<=n; i++){
scanf("%lld %lld", &arr[i].x, &arr[i].y);
arr[i].idx = i;
}
sort(arr+1, arr+n+1, [&](vector2 &x, vector2 &y){
return ccw(vecA, x, y) < 0;
});
for(int i=1; i<=n; i++) AIdx[arr[i].idx] = i;
sort(arr+1, arr+n+1, [&](vector2 &x, vector2 &y){
return ccw(vecB, x, y) < 0;
});
for(int i=1; i<=n; i++) BIdx[arr[i].idx] = i;
sort(arr+1, arr+n+1);
for(int i=1; i<=n; i++){
int x = arr[i].idx;
sum[i] += treeA.getSum(1, AIdx[x]);
sum[i] += treeB.getSum(BIdx[x], n);
treeA.add(AIdx[x], 1);
treeB.add(BIdx[x], 1);
if(sum[i] == i-1) ans++;
}
printf("%d", ans);
}
15. 메이플 월드 라이딩 여행
서브태스크 1 (7점)
같은 점을 여러 번 방문할 일이 없기 때문에, priority_queue를 이용해 다익스트라 알고리즘을 조금만 변형하면 $O(M \log M)$에 쉽게 풀 수 있습니다. 이 풀이를 이용하면 서브태스크 2까지 풀 수 있을 것으로 보이나, 사실 그렇지 않습니다.
서브태스크 1, 2 (24점)
서브태스크 2가 풀리지 않는 이유는, priority queue가 매우 커져서 메모리 초과가 나기 때문입니다. 이 점을 개선하는 한 가지 방법은, 각 점에서 나가는 간선들을 비용 순으로 정렬한 뒤, 어떤 정점에 방문하면 거기서 갈 수 있는 모든 점을 priority queue에 넣는 것이 아니라 가장 작은 것만 넣는 것입니다. 그 뒤 방금 넣은 것을 꺼낼 차례가 오면, 그 다음으로 작은 것을 넣습니다. 이런 식으로 하면 매우 효율적으로 처리할 수 있게 됩니다. 시간 복잡도는 역시 $O(M \log M)$입니다.
서브태스크 1, 2, 3 (54점)
여기서부터는 한 번 방문한 정점을 다시 방문할 수 있습니다. 따라서 bitset을 이용해서 방문한 정점을 체크해 주는 식으로 문제를 해결하면 문제를 맞을 수 있습니다. 시간 복잡도는 $O(MK \log M)$이지만, bitset을 이용해 상수가 매우 작기 때문에 통과됩니다.
서브태스크 1, 2, 3, 4 (100점)
위 풀이는 메모리 초과로 인해 서브태스크 4를 통과하지 못합니다. 그 이유는 비트의 개수 때문인데, 10만 개의 최단 경로에 대해 10만 칸의 체크 배열을 저장하고 있기 때문에 메모리 초과가 나는 것입니다. 이때 사용되는 비트는 100억 개로, 이를 모두 저장하려면 1250 MB가 필요합니다. 문제의 메모리 제한인 512MB보다 훨씬 큽니다.
여기서 여러 가지 최적화 기법을 적용해 봅시다. 현재 bitset에는 0으로 채워진 빈 칸이 매우 많습니다. 그 이유는 먼 미래에나 방문하게 될 정점들을 bitset에 0으로 체크하고 있기 때문입니다. 따라서 dijkstra를 이용해 먼저 방문하는 정점의 번호를 더 작게 재배치한 뒤, bitset의 크기를 동적으로 관리해 메모리를 줄일 수 있습니다. 대충 계산해도, 메모리가 최소 반으로 줄어든다는 사실을 알 수 있습니다. 하지만 여전히 512MB보다 큽니다. 더 최적화해야 합니다. 더 이상 참조할 필요가 없는 비트셋들의 크기를 0으로 줄여 버리고, 그 비트셋을 추후에 재활용하는 식으로 코드를 짜면 약 600MB 정도로 메모리를 줄일 수 있습니다.
여전히 메모리가 부족합니다. 메모리가 약 600MB 정도 활용되고 있으니, 메모리를 어떻게든 반절 정도로만 줄이면 될 것 같습니다. 하지만 이미 온갖 최적화를 했는데, 반절로 줄이는 게 가능할까요?
어떤 경로 $x$의 끝점에서 한 번 라이딩을 이용하여 다른 경로 $y$를 만들어낼 수 있다면, $x$를 $y$의 부모 관계라고 합시다. 이때 우리는 정점이 $K$개인 트리를 찾게 될 텐데, 이때 루트는 '소요 시간이 0인 여행 경로'입니다. 여기서 깊이가 짝수인 bitset만 저장해 놓고, 깊이가 홀수인 bitset은 부모 노드를 이용해 계산하면, 메모리가 반절로 줄 것 같습니다. 하지만 만약 깊이가 홀수인 정점에 자식이 엄청나게 많다면, 반례가 존재한다는 사실을 쉽게 깨달을 수 있습니다. 그렇지만 여기서 한 발짝만 더 나아가 봅시다. 부모가 같은 두 노드를 형제 관계라고 합시다. 이때 형제 관계인 노드들은 하나의 bitset을 알면 다른 하나도 쉽게 알아낼 수 있습니다. 이렇게 하면, 모든 (우리가 bitset을 저장하고 있을) 노드들에 대해 (우리가 bitset을 저장하지 않고, 다른 bitset을 이용해 얻어낼) 노드를 최소 하나씩 대응시킬 수 있습니다. (부모 노드드를 대응시키면 됩니다.) 따라서 bitset을 저장할 노드보다 저장하지 않을 노드가 많다는 사실을 알아낼 수 있고, 메모리는 다시 반으로 줄어듭니다. 우리가 해냈습니다.
시간 복잡도는 $O(KM \log N)$, 공간 복잡도는 $O(KN)$입니다. 둘 다 상수가 작기 때문에 코드가 통과됩니다.
#include <bits/stdc++.h>
#define LIM n
using namespace std;
typedef long long ll;
struct Bitset{
int sz;
vector<ll> vec;
Bitset(){}
Bitset(int s){
sz = s;
vec.resize((s+63)>>6);
}
inline void resize(int s){
if(sz > s){
sz = s;
vec.resize((s+63)>>6);
vec.shrink_to_fit();
return;
}
sz = s;
vec.resize((s+63)>>6);
vec.shrink_to_fit();
}
inline void flip(int x){
if(sz<=x) resize(x+1);
vec[x>>6] ^= 1LL << ll(x&63);
}
inline bool bit(int x){
if(sz<=x) return 0;
return !!(vec[x>>6] & (1LL << ll(x&63)));
}
};
struct dat{
int x, pv, pnt, ti; ll y;
dat(){}
dat(int x, int pv, int pnt, int ti, ll y): x(x), pv(pv), pnt(pnt), ti(ti), y(y){}
bool operator<(const dat &r)const{
return y>r.y;
}
};
int n, m, k, s;
vector<pair<int, ll> > link[100002], link2[100002];
priority_queue<dat> pq;
vector<Bitset> btst;
int idx[100002], tmpIdx;
bitset<100001> visited;
int memoryLoc[100002], par[100002];
int depth[100002], smallest[100002], smallestLocation[100002], tSmall, location[100002];
bool hasSaved[100002];
void dijkstra(){
priority_queue<pair<ll, int> > pq;
pq.push({0, s});
while(!pq.empty()){
auto tmp = pq.top(); pq.pop();
if(visited[tmp.second]) continue;
visited[tmp.second] = 1;
idx[tmp.second] = ++tmpIdx;
for(auto &y: link[tmp.second]){
if(visited[y.first]) continue;
pq.push({tmp.first - y.second, y.first});
}
}
for(int i=1; i<=n; i++){
if(idx[i] > LIM || !idx[i]) continue;
for(auto &y: link[i]){
if(idx[y.first] > LIM) continue;
link2[idx[i]].push_back({idx[y.first], y.second});
}
}
for(int i=1; i<=LIM; i++){
link[i] = link2[i];
link2[i].clear();
link2[i].shrink_to_fit();
}
}
int main(){
scanf("%d %d %d %d", &n, &m, &k, &s);
for(int i=1; i<=m; i++){
int x, y; ll z;
scanf("%d %d %lld", &x, &y, &z);
link[x].push_back({y, z});
}
dijkstra();
s = idx[s];
for(int i=1; i<=n; i++){
sort(link[i].begin(), link[i].end(), [&](auto &x, auto &y){
return x.second < y.second;
});
}
pq.push(dat(s, 0, 0, 0, 0));
for(int c=1; c<=k; c++){
if(pq.empty()){
printf("-1");
return 0;
}
// if(c==112){
// printf("");
// }
dat tmp = pq.top(); pq.pop();
if(c==k){
printf("%lld", tmp.y);
return 0;
}
if(c>1){
depth[c] = depth[tmp.ti] + 1;
}
par[c] = tmp.ti;
location[c] = tmp.x;
if(depth[c] % 2 == 0 && (c == 1 || smallest[tmp.ti] == tmp.x)){
hasSaved[c] = 1;
btst.push_back(Bitset(0));
memoryLoc[c] = (int)btst.size()-1;
if(c!=1){
smallestLocation[tmp.ti] = memoryLoc[c];
if(hasSaved[par[par[c]]]){
btst[memoryLoc[c]] = btst[memoryLoc[par[par[c]]]];
btst[memoryLoc[c]].flip(tmp.pv-1);
btst[memoryLoc[c]].flip(tmp.x-1);
}
else{
tSmall = smallest[par[par[par[c]]]];
btst[memoryLoc[c]] = btst[smallestLocation[par[par[par[c]]]]];
btst[memoryLoc[c]].flip(tSmall-1);
btst[memoryLoc[c]].flip(location[par[par[c]]]-1);
btst[memoryLoc[c]].flip(tmp.pv-1);
btst[memoryLoc[c]].flip(tmp.x-1);
}
}
else btst[memoryLoc[c]].flip(tmp.x - 1);
// printf("%d -> memoryLoc %d, %lld\n", c, memoryLoc[c], btst[memoryLoc[c]].vec[0]);
// if(btst[memoryLoc[c]].bit(9)){
// printf("10 exist below:\n");
// }
}
// printf("%d -> %lld, tmpx: %d, prv:", c, tmp.y, tmp.x);
// cout << tmp.ti << '\n';
if(tmp.pv && (int)link[tmp.pv].size() > tmp.pnt){
for(int i=tmp.pnt; i<(int)link[tmp.pv].size(); i++){
auto y = link[tmp.pv][i];
if(hasSaved[tmp.ti]){
if(btst[memoryLoc[tmp.ti]].bit(y.first-1)) continue;
}
else if(depth[tmp.ti]%2==1){ /// c -> tmp.ti
if(hasSaved[par[tmp.ti]]){
if(btst[memoryLoc[par[tmp.ti]]].bit(y.first-1)) continue;
}
else{
if(y.first == location[par[tmp.ti]]) continue;
tSmall = smallest[par[par[tmp.ti]]];
if(btst[smallestLocation[par[par[tmp.ti]]]].bit(y.first-1)){
if(tSmall != y.first) continue;
}
if(y.first == location[par[tmp.ti]]) continue;
}
}
else{
tSmall = smallest[par[tmp.ti]];
if(tSmall != y.first && btst[smallestLocation[par[tmp.ti]]].bit(y.first-1) && tSmall != y.first) continue;
}
pq.push(dat(y.first, tmp.pv, i+1, tmp.ti, tmp.y - link[tmp.pv][tmp.pnt-1].second + y.second));
break;
}
}
if(!link[tmp.x].empty()){
for(int i=0; i<(int)link[tmp.x].size(); i++){
auto y = link[tmp.x][i];
if(hasSaved[c]){
if(btst[memoryLoc[c]].bit(y.first-1)) continue;
}
else if(depth[c]%2==1){
if(hasSaved[par[c]]){
if(btst[memoryLoc[par[c]]].bit(y.first-1)) continue;
}
else{
if(y.first == location[par[c]]) continue;
tSmall = smallest[par[par[c]]];
if(btst[smallestLocation[par[par[c]]]].bit(y.first-1)){
if(tSmall != y.first) continue;
}
if(y.first == location[par[c]]) continue;
}
}
else{
tSmall = smallest[par[c]];
if(tSmall != y.first && btst[smallestLocation[par[c]]].bit(y.first-1)) continue;
}
pq.push(dat(y.first, tmp.x, i+1, c, tmp.y + y.second));
smallest[c] = y.first;
break;
}
}
}
}
16. 덕분에 챌린지
서브태스크 1, 2 (49점)
문제를 있는 그대로 풀면 많이 힘듭니다. 트리 문제로 변형시키면, 정점이 $N+M$개인 트리를 만들되, 최대 깊이를 최소로 하는 이진 트리를 만드는 문제가 됩니다. 일반성을 잃지 않고 $X < Y$라고 가정합시다. ($X=Y$라면 완전 이진 트리 형태로 만드는 것이 항상 최적 전략임을 어렵지 않게 보일 수 있습니다.)
문제를 트리로 옮기고 나면, 여러 가지 관찰을 할 수 있습니다. 모든 정점은 시간이 $X$만큼 걸리거나 $Y$만큼 걸리는 정점입니다. 즉, 깊이를 $X$만큼 또는 $Y$만큼 증가시키는 정점입니다. 깊이를 $X$만큼 증가시키는 정점을 $X$-정점, 깊이를 $Y$만큼 증가시키는 정점을 $Y$-정점이라고 합시다.
여기서 DP를 생각해볼 수 있습니다. 위 관찰을 하지 못한 상태에서 만들 수 있는 점화식은,
$$DP[x][y]$$: $X$-정점이 $x$개, $Y$-정점이 $y$개 있는 트리의 최소 깊이
로 두고, DP table을 채워나가는 것입니다. 하나의 값을 채울 때 $O(N^2)$개의 상태를 참조해야 하기 때문에 총 $O(N^4)$의 시간이 걸립니다.
서브태스크 1, 2, 3 (100점)
시간 복잡도를 줄여야 합니다. 여기서 관찰 두 가지가 더 필요합니다.
- $Y$-정점이 $X$-정점의 부모인 경우가 없는 최적해가 항상 존재한다.
- $DP[x][y] < DP[x+1][y]$
위의 성질은 자명하고, 아래쪽 성질은 증명이 필요할 것 같지만 저는 증명 없이 사용하였습니다. 위 성질을 이용해 DP를 한 번에 한 줄씩 구해 봅시다.
$$DP[x][y] = \min_{0 \le i < x, 0 \le j \le y} \max(DP[i][j], DP[x-1-i][y-j]) + X$$
입니다. 여기서 $x$와 $i$를 고정시키고, 가능한 모든 $y$와 $j$를 빨리 탐색할 방법을 찾아 봅시다. 위 식을 조금 변형하면, $DP[i][j] \ge DP[x-1-i][y-j]$인 $DP[i][j]$의 최솟값을 찾는 것이 됩니다. 여기서 $(i, j)$를 고정한다면, 왼쪽 조건이 성립할 $y$의 범위를 알아낼 수 있습니다. $y$의 범위는 $0 \le y \le y_{MAX}$과 같은 꼴로 나타날 것입니다.
그렇다면 $y_{MIN}$을 빨리 구한 뒤, 구간 업데이트를 하는 식으로 DP table을 더 빠르게 채워나갈 수 있습니다. 구간 업데이트는 prefix minimum 기법 비슷한 걸 쓰면 상수 시간에 되지만, $y_{MAX}$을 찾는 것은 로그 시간보다 더 빠르게 하기 힘들어 보입니다. 하지만 $O(N^3 \log N)$은 문제를 맞기에는 너무 큰 시간 복잡도입니다.
여기서 lower_bound 등의 이분 탐색 알고리즘을 쓰는 대신 각 $(i, j)$별로 $y_{MAX}$를 계속 관리해 나가면서 한 칸씩 옮기면 전체 $y_{MIN}$에 업데이트의 횟수가 $O(N^4)$ 미만인데, 실제로는 이보다 업데이트 횟수가 훨씬 적기 때문에 코드가 통과됩니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, X, Y;
int DP[502][502];
int pnt[502][502];
int main(){
scanf("%d %d %d %d", &n, &m, &X, &Y);
if(X>Y) swap(n, m), swap(X, Y);
for(int i=1; i<=m; i++){ /// 먼저 DP[0][0] ~ DP[0][m]을 구한다. 간단한 수학 식으로 구할 수 있다.
DP[0][i] = DP[0][i/2] + Y;
}
for(int i=1; i<=n; i++){ /// 이제 DP[i][0] ~ DP[i][m]을 한 번에 구하자.
for(int y=0; y<=m; y++){
pnt[i-1][y] = m;
DP[i][y] = 2e9;
}
for(int x=0; x<i; x++){
for(int y=0; y<=m; y++){ /// pnt[x][y]의 위치를 관리할 것이다.
while(pnt[x][y] >= 0 && DP[x][y] < DP[i-1-x][pnt[x][y]]) pnt[x][y]--;
while(pnt[x][y] < m && DP[x][y] >= DP[i-1-x][pnt[x][y]+1]) pnt[x][y]++;
if(pnt[x][y] >= 0) DP[i][min(m, y+pnt[x][y])] = min(DP[i][min(m, y+pnt[x][y])], DP[x][y]+X);
}
}
for(int y=m-1; y>=0; y--){
DP[i][y] = min(DP[i][y], DP[i][y+1]);
}
}
printf("%d", DP[n][m]);
}
17. 좋은 카트 만들기
모든 카트 핸들 $j$에 대해, $(-D_j, -C_j)$를 좌표 평면에 찍습니다. 그럼 우리는 각 카트 엔진 $(B_i, A_i)$에 대해, 카트 핸들을 나타내는 점과 직선으로 이었을 때 만들 수 있는 최대 기울기를 구하면 됩니다.
엔진을 나타내는 점은 모두 제1사분면, 핸들을 나타내는 점은 모두 제3사분면에 있습니다. 여기서 우리가 해야 할 일은, 제3사분면에 있는 점과 이을 때 생기는 최대 기울기인데, 이때 후보가 될 수 있는 제3사분면의 점들은 볼록 껍질의 일부라는 사실을 알 수 있습니다. (정확히는 볼록 껍질에서 오른쪽 아래 부분에 해당하는 chain입니다.)
답이 두 개 이상일 때 더 작은 index를 출력해야 한다는 것은, 볼록 껍질을 구할 때 각 변의 중간에 있는 것들도 구해 주어야 한다는 뜻인데, 몇 가지 처리를 추가적으로 해야 해 난이도가 높아집니다. 조금 더 쉽게 구하려면 점들을 set 같은 자료구조에 관리해 주면서, 점들을 하나씩 추가해 나가며 set을 수정하는 방법입니다. convex hull을 구할 필요 없이 오른쪽 아래에 있는 단조 증가하는 볼록하는 점들의 집합만 구하면 되기 때문에 가능한 방법입니다.
결론적으로 이 chain은 $O(N \log N)$에 구할 수 있습니다. 그 뒤, 각 엔진에 대해 삼분 탐색으로 기울기의 최댓값을 찾아주면 문제를 풀 수 있습니다. 시간 복잡도는 $O(N \log N)$입니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct vector2{
ll x, y; int idx;
explicit vector2(double x_ = 0, double y_ = 0): x(x_), y(y_){}
bool operator==(const vector2 &r)const{
return x == r.x && y == r.y;
}
bool operator<(const vector2 &r)const{
return x != r.x ? x < r.x : y < r.y;
}
bool operator>(const vector2 &r)const{
return r < *this;
}
vector2 operator+(const vector2 &r)const{
return vector2(x+r.x, y+r.y);
}
vector2 operator-(const vector2 &r)const{
return vector2(x - r.x, y - r.y);
}
vector2 operator*(double r)const{
return vector2(x*r, y*r);
}
ll dot(vector2 &r)const{
return x*r.x + y*r.y;
}
ll cross(vector2 &r)const{
return x*r.y - y*r.x;
}
};
ll ccw(vector2 a, vector2 b){
return a.cross(b);
}
ll ccw(vector2 a, vector2 b, vector2 c){
return ccw(b-a, c-a);
}
ll dist(vector2 a, vector2 b){
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
int n, m, k;
vector2 query[300002];
vector2 arr[300002];
vector<vector2> hull;
int leftMax[300002];
int rightMax[300002];
void convexHull(){
map<pair<int, int>, int> mp;
for(int i=1; i<=m; i++){
if(!mp[make_pair(arr[i].x, arr[i].y)]) mp[make_pair(arr[i].x, arr[i].y)] = i;
arr[i] = vector2(0, 0);
}
m = 0;
for(auto &x: mp){
arr[++m] = vector2(x.first.first, x.first.second);
arr[m].idx = x.second;
}
set<vector2> st;
st.insert(arr[1]);
for(int i=2; i<=m; i++){
auto it = st.lower_bound(arr[i]);
if(it != st.begin() && prev(it)->x == arr[i].x) continue;
if(it != st.end() && it->y <= arr[i].y) continue;
if(it != st.begin() && it != st.end() && ccw(*prev(it), arr[i], *it) < 0) continue;
if(it != st.end() && it->x == arr[i].x){
st.erase(it);
it = st.lower_bound(arr[i]);
}
while(it != st.begin() && prev(it) != st.begin() && ccw(*prev(prev(it)), *prev(it), arr[i]) < 0){
--it;
st.erase(it);
it = st.lower_bound(arr[i]);
}
while(it != st.end() && next(it) != st.end() && ccw(arr[i], *it, *next(it)) < 0){
st.erase(it);
it = st.lower_bound(arr[i]);
}
st.insert(arr[i]);
}
for(auto &x: st){
hull.push_back(x);
}
k = (int)hull.size();
}
int ternarySearch(int l, int r, vector2 point){
if(r-l<=3){
int ret = l;
for(int i=l+1; i<=r; i++){
if(ccw(point, hull[ret], hull[i]) > 0) ret = i;
}
return ret;
}
int p = (l+l+r)/3, q = (l+r+r)/3;
if(ccw(point, hull[q], hull[p]) > 0) return ternarySearch(l, q, point);
return ternarySearch(p, r, point);
}
int main(){
scanf("%d %d", &n, &m);
for(int i=1; i<=n; i++){
scanf("%lld %lld", &query[i].y, &query[i].x);
}
for(int i=1; i<=m; i++){
scanf("%lld %lld", &arr[i].y, &arr[i].x);
arr[i].x *= -1, arr[i].y *= -1;
arr[i].idx = i;
}
convexHull();
leftMax[0] = hull[0].idx, leftMax[1] = min(hull[0].idx, hull[1].idx);
for(int i=2; i<k; i++){
if(ccw(hull[i-2], hull[i-1], hull[i]) == 0) leftMax[i] = min(hull[i].idx, leftMax[i-1]);
else leftMax[i] = min(hull[i].idx, hull[i-1].idx);
}
rightMax[k-1] = hull[k-1].idx, rightMax[k-2] = min(hull[k-1].idx, hull[k-2].idx);
for(int i=k-3; i>=0; i--){
if(ccw(hull[i+2], hull[i+1], hull[i]) == 0) rightMax[i] = min(hull[i].idx, rightMax[i+1]);
else rightMax[i] = min(hull[i].idx, hull[i+1].idx);
}
for(int i=1; i<=n; i++){
int tmp = ternarySearch(0, k-1, query[i]);
int ans = hull[tmp].idx;
if(tmp && ccw(query[i], hull[tmp], hull[tmp-1]) == 0) ans = min(ans, leftMax[tmp]);
if(tmp < k-1 && ccw(query[i], hull[tmp], hull[tmp+1]) == 0) ans = min(ans, rightMax[tmp]);
printf("%d\n", ans);
}
}
18. 유저 그룹 나누기
서브태스크 1, 2 (31점)
가능한 구간 합의 종류는 $N^2$개 이하입니다. 따라서 minimum sum과 maximum sum을 고정시켜 놓고, 가능한지 판별하는 식으로 $O(N^5 \log N)$ 풀이를 찾을 수 있습니다.
가능한 최소 구간 합을 $O(N^2)$개 중 하나로 고정시켜 놓고, 최대 구간 합이 어디까지 가능한지를 이분 탐색으로 찾으면 $O(N^3 \log^2 N)$ 풀이가 만들어집니다.
어떤 최솟값과 최댓값 쌍에 대해, 가능한지 판별하는 것은 앞에서부터 sweeping을 해 주면서 DP + segment tree 등의 기법을 조합해 쉽게 해결할 수 있습니다. ($DP[i]$: 1~$i$번 수들을 최솟값, 최댓값 사이의 구간 합을 가진 구간들로 쪼갤 때, 필요한 구간의 최소 개수와 최대 개수로 정의한 뒤, $DP[n]$의 최솟값과 최댓값 사이에 $k$가 있는지 판별하면 됩니다.)
위 풀이로 31점을 받을 수 있습니다. 시간 복잡도는 $O(N^3 \log^2 N)$입니다.
서브태스크 1, 2, 3 (100점)
사용할 수 있는 MIN 값이 늘어나면 MAX 값도 늘어난다는 성질을 이용해 MIN과 MAX를 투 포인터로 관리하면, $O(N^3 \log N)$ 풀이에 도달할 수 있습니다. 여전히 문제를 맞기에는 아슬아슬합니다.
DP table을 채울 때, lower bound를 이용해 직전 값으로 이용할 수 있는 범위를 찾고, 그 안에서 최댓값을 segment tree로 찾아서 시간 복잡도에 log가 붙고 있습니다. 이렇게 하지 않고 monotone deque을 이용하면 $O(N^3)$ 풀이가 완성됩니다.
눈치 빠른 독자 분들이라면 제 풀이에서는 $X \le U_i \le 2X$라는 조건이 전혀 사용되지 않았다는 사실을 파악하실 수 있습니다. 이 조건이 있어서 더 쉬운 풀이가 존재하는지는 잘 모르지만, 존재한다면 한번쯤 연구해 보는 것도 좋겠습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, k; ll x;
ll arr[402];
ll sum[402];
vector<ll> rangeSum;
ll ans = LLONG_MAX;
int DPMin[402], DPMax[402];
list<pair<int, int> > queMin, queMax;
int main(){
scanf("%d %d %lld", &n, &k, &x);
if(k==1){
printf("0");
return 0;
}
for(int i=1; i<=n; i++) scanf("%lld", &arr[i]);
for(int i=1; i<=n; i++) sum[i] = sum[i-1] + arr[i];
for(int i=1; i<=n; i++){
for(int j=1; j<=i; j++){
rangeSum.push_back(sum[i] - sum[j-1]);
}
}
sort(rangeSum.begin(), rangeSum.end());
rangeSum.erase(unique(rangeSum.begin(), rangeSum.end()), rangeSum.end());
int j = 0;
for(int i=0; i<(int)rangeSum.size(); i++){
ll MIN = rangeSum[i];
ll MAX = rangeSum[j];
while(j < (int)rangeSum.size()){
int minPnt = 0;
int maxPnt = -1;
queMin.clear(), queMax.clear();
for(int f=1; f<=n; f++){
while(sum[f] - sum[maxPnt+1] >= MIN){
maxPnt++;
while(!queMax.empty() && queMax.back().second <= DPMax[maxPnt]) queMax.pop_back();
queMax.push_back({maxPnt, DPMax[maxPnt]});
while(!queMin.empty() && queMin.back().second >= DPMin[maxPnt]) queMin.pop_back();
queMin.push_back({maxPnt, DPMin[maxPnt]});
}
while(sum[f] - sum[minPnt] > MAX){
minPnt++;
while(!queMax.empty() && queMax.front().first < minPnt) queMax.pop_front();
while(!queMin.empty() && queMin.front().first < minPnt) queMin.pop_front();
}
if(minPnt > maxPnt){
DPMax[f] = -1e9, DPMin[f] = 1e9;
continue;
}
DPMax[f] = queMax.front().second + 1;
DPMin[f] = queMin.front().second + 1;
}
if(DPMin[n] <= k && k <= DPMax[n]) break;
MAX = rangeSum[++j];
}
if(j == (int)rangeSum.size()) break;
ans = min(ans, MAX - MIN);
}
printf("%lld", ans);
}
19. 서비스 센터
binary search를 이용해 답을 찾아 나갑니다. 그렇다면 문제는 $d$일 안에 모든 방문 서비스가 수행될 수 있는가? 라는 결정 문제로 변환됩니다.
이제 $d$일 안에 가능한지를 판별하는 결정 문제를 풀어야 하는데, 적당한 그리디나 규칙을 잡아서 모든 사무실에 서비스 센터를 매칭해야 할 것 같습니다. 구간을 한 서비스 센터가 커버할 수 있는 영역이라고 합시다. 어떤 구간이 다른 구간을 완전히 포함하는 경우 등을 고려하면 규칙을 정하기란 매우 난감해 보입니다.
여기서 아이디어가 하나 생깁니다. 어떤 구간 $x$가 다른 구간 $y$를 완전히 포함한다면, $y$를 먼저 정하고 $x$를 정하는 것이 더 나을 것입니다. $x$를 먼저 정했는데, 다 $y$에 포함되는 것들이면 $y$ 입장에서 상당히 난감해질 것입니다. 그래서 위상 정렬과 같은 방식으로 다른 구간을 포함하지 않는 구간을 앞쪽에 배치하고, 앞쪽 구간부터 가면서 스위핑을 해 준다면 뭔가 되지 않을까? 하는 생각을 할 수 있습니다. 하지만 조금만 더 관찰해 보면, 이 순서는 결국 구간의 오른쪽 끝점 순서대로 정렬한 것이라는 사실을 알 수 있고(오른쪽 끝점이 같으면 왼쪽 끝점이 더 오른쪽에 있는 것부터), 그냥 $O(N \log N)$에 이 순서를 얻어낼 수 있습니다.
그럼 이제 사무실들을 어떻게 서비스 센터에 배정할까요? 그리디한 접근을 생각해 봅시다. 저는 아까 배정한 순서대로 서비스 센터 목록을 왼쪽부터 오른쪽으로 순회하면서, 서비스 센터에 사무실을 배정할 것입니다. 최대 $d$개까지 배정할 수 있으니, $y-x$가 큰 사무실부터 차례로 배치할 것입니다. 물론, 서비스 센터가 커버할 수 없는 영역에 있는 사무실은 배정하면 안 됩니다. 그럼 여기서 저희는 아래 연산을 지원하는 자료구조를 구현해야 합니다.
- $x+y$가 $L$ 이하이고 $y-x$가 $K$ 이상인 점들 중 $y-x$가 최대인 점을 반환한다.
이러한 자료구조는 현실적으로 로그 제곱 이상의 시간이 걸릴 수밖에 없습니다. 하지만 쿼리로 들어오는 $L$은, 무려 단조 증가합니다! 따라서 사무실들을 $x+y$ 순서대로 정렬해 놓고, 쿼리로 들어오는 $L$이 커질 때마다 set 등의 자료구조에 하나씩 삽입해 나간다면 평범한 set과 lower_bound 연산만으로 문제를 풀 수 있습니다! 이때 걸리는 시간 복잡도는 $O(N \log M \log X)$인데, 두 로그가 상당히 큰 편이기 때문에(red black tree의 로그는 느리기로 유명합니다.) 어느 정도 빠른 코드를 짜야만 통과될 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Service{
ll x, s;
Service(){}
Service(ll x, ll s): x(x), s(s){}
bool operator<(const Service &r)const{
if(x+s == r.x+r.s) return s<r.s;
return x+s < r.x+r.s;
}
};
struct Query{
ll x, y; int idx;
Query(){}
Query(ll x, ll y, int idx): x(x), y(y), idx(idx){}
bool operator<(const Query &r)const{
if(y-x == r.y-r.x) return y+x < r.y+r.x;
return y-x > r.y-r.x;
}
};
int n, k;
ll cap[100002], tcap[100002];
Service service[100002];
Query query[100002];
vector<int> invalid;
multiset<Query> mst;
bool able(ll key){
int pnt = 0; ll cnt = key;
mst.clear();
for(int i=1; i<=k; i++) tcap[i] = cap[i];
for(int i=1; i<=n; i++){
while(pnt < k && query[pnt+1].x + query[pnt+1].y <= service[i].x + service[i].s){
pnt++;
mst.insert(query[pnt]);
}
cnt = key;
while(cnt){
auto it = mst.lower_bound(Query(service[i].x - service[i].s - 1, -1, 0));
if(it == mst.end()) break;
if(tcap[it->idx] <= cnt){
cnt -= tcap[it->idx];
tcap[it->idx] = 0;
mst.erase(it);
}
else{
tcap[it->idx] -= cnt;
cnt = 0;
}
}
}
return mst.empty();
}
int main(){
scanf("%d %d", &n, &k);
for(int i=1; i<=n; i++) scanf("%lld %lld", &service[i].x, &service[i].s);
for(int i=1; i<=k; i++){
scanf("%lld %lld %lld", &query[i].x, &query[i].y, &cap[i]);
query[i].y = abs(query[i].y);
query[i].idx = i;
}
sort(service+1, service+n+1);
sort(query+1, query+k+1, [&](auto &a, auto &b){
if(a.y+a.x != b.y+b.x) return a.y+a.x < b.y+b.x;
return a.y-a.x > b.y-b.x;
});
ll l = 1, r = 100'000'000'000'000, ans = r;
while(l <= r){
ll m = (l+r)>>1;
if(able(m)) ans = m, r = m-1;
else l = m+1;
}
printf("%lld", ans);
}
20. 물풍선 테러리스트
어떤 물풍선을 터트렸을 때 터질 수 있는 다른 물풍선에 간선을 잇는다고 생각해 봅시다. 간선의 개수는 최악의 경우 $O(N^2)$개가 됩니다. 하지만 문제의 상황이 격자판 위에 있고, 네 방향으로 물줄기가 흐르는 특수한 경우이므로, 간선의 수를 잘 줄일 수 있어 보입니다.
간선의 수를 적당히 줄였다면, 이제 답을 어떻게 구해야 할까요? 그래프의 SCC를 구하면 두 경우 모두 쉽게 계산이 가능합니다. 따라서 간선의 개수만 쉽게 줄일 수 있다면, 그 뒤는 매우 쉽게 풀린다는 사실을 알 수 있습니다.
하지만 간선의 개수는 일반적으로 줄이기 매우 어렵습니다. 그 대신, 가상의 노드를 만들면 간선을 줄일 수 있습니다. 어쨌든 min, max 둘 다 SCC를 요구하기 때문에, 우선 간선의 개수를 줄이고 SCC를 만드는 법에 대해 살펴봅시다.
어떤 물풍선이 터질 때 터지는 물풍선은 가로로 연속한 구간과 세로로 연속한 구간으로 나누어볼 수 있습니다. 따라서 어떤 간선에서 특정 구간의 점들로 간선을 연결하는 방법을 찾으면 됩니다. 여기서 x좌표가 같은 / y좌표가 같은 점들을 묶어, 세그먼트 트리 형태로 관리합니다.
이런 형태로 관리하고 나면 어떤 점에서 특정 구간의 점들에 간선을 뿌리는 것을 $O(\log N)$개 정도의 간선으로 줄일 수 있고, 총 간선 개수는 $O(N \log N)$이 됩니다. SCC는 여러 가지 유명한 알고리즘(저는 비교적 구현을 외우기 쉬운 kosaraju 알고리즘을 선호합니다. tarjan 알고리즘도 좋습니다.)을 이용해 $O(V)$에 구할 수 있으므로 SCC까지 구하는 데 걸리는 총 시간 복잡도는 $O(N \log N)$이 됩니다.
여기까지 구하면 max가 끝나는 것 같아 보이지만, 사실 몇 가지 예외 처리가 필요합니다. 예를 들어, 저렇게 임시로 추가한 정점들로만 이루어진 SCC는 세면 안 되는 것과 같습니다. 하지만 그래도 max인 경우는 저 아이디어만 떠올렸다면 쉽습니다. (다만 구현이 매우 복잡합니다.)
이제 min은 어떻게 계산할까요? min의 경우는 기본적으로 SCC를 모두 구한 뒤, SCC graph를 만들어야 합니다. 이후 이 그래프에서 indegree가 0인 SCC의 개수를 세면 답을 구할 수 있습니다.
이걸 그대로 하면 시간 복잡도는 $O(N \log N)$, 메모리도 같은 복잡도인데... 실제로는 간선 개수가 많고 다른 것들도 너무 많기 때문에 메모리 제한에 걸립니다. 왜 그럴까요? 자세히 살펴보면,
간선 개수: $E = 4N + 4N + 4N \log N$
역간선 개수: $E$
SCC 관련 정보: $V = 4N + 4N + N$
SCC 간선 관련 정보: $E$
총합 1억 3천만 개 정도의 수가 저장되게 되는데, 실제로는 다른 정보들도 저장되니 메모리 초과가 날 이유는 다분합니다. 어떻게 하면 줄일 수 있을까요? 세그먼트 트리를 짓는 과정에서 낭비되는 노드들이 많은데, 그런 노드들의 개수를 줄이면 $V=3N$으로 줄일 수 있습니다. 물론 저는 여기까지만 하고 맞았지만, 만약 여전히 메모리 초과가 난다면 필요 없는 벡터들은 그때그때 clear해주고 shrink_to_fit으로 메모리를 없애 주면 됩니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
string command;
struct dat{
int x, y, p, idx;
dat(){}
dat(int x, int y): x(x), y(y){}
bool operator<(const dat &r)const{
return x==r.x ? y<r.y : x<r.x;
}
} arr[500002];
vector<int> link[1500002], linkRev[1500002]; int vCount;
int xSegRoot[500002], ySegRoot[500002]; /// 순서대로 x값이 같은 세그먼트 트리의 루트, y값이 같은 세그먼트 트리의 루트이다.
int segL[1500002], segR[1500002];
vector<vector<int> > SCC;
vector<vector<int> > SCCLink;
vector<bool> validSCC;
int SCCnum[1500002];
int SCCindegree[1500002];
int ansMin, ansMax;
namespace CALC_SCC{
bool visited[2500002];
stack<int> SCC_stk;
void constructTree(int i, int l, int r){
segL[i] = l, segR[i] = r;
int m = (l+r)>>1;
if(l!=m){
link[i].push_back(vCount+1), linkRev[vCount+1].push_back(i);
constructTree(++vCount, l, m);
}
else link[i].push_back(arr[l].idx), linkRev[arr[l].idx].push_back(i);
if(m+1!=r){
link[i].push_back(vCount+1), linkRev[vCount+1].push_back(i);
constructTree(++vCount, m+1, r);
}
else link[i].push_back(arr[r].idx), linkRev[arr[r].idx].push_back(i);
}
void makeSegtree(){
sort(arr+1, arr+n+1);
for(int i=1; i<=n; i++){
int s = i, e = i;
while(arr[s].x == arr[e+1].x) e++;
if(s==e) continue;
int tmp = ++vCount;
for(int j=s; j<=e; j++) xSegRoot[j] = tmp;
constructTree(vCount, s, e);
i = e;
}
for(int i=1; i<=n; i++) swap(arr[i].x, arr[i].y);
sort(arr+1, arr+n+1);
for(int i=1; i<=n; i++){
int s = i, e = i;
while(arr[s].x == arr[e+1].x) e++;
if(s==e) continue;
int tmp = ++vCount;
for(int j=s; j<=e; j++) ySegRoot[j] = tmp;
constructTree(vCount, s, e);
i = e;
}
for(int i=1; i<=n; i++) swap(arr[i].x, arr[i].y);
}
void connectEdges(int i, int s, int e, int from){
if((1<=i && i<=n) || (s <= segL[i] && segR[i] <= e)){
link[from].push_back(i);
linkRev[i].push_back(from);
return;
}
int m = (segL[i] + segR[i]) >> 1;
if(s <= m) connectEdges(link[i][0], s, min(m, e), from);
if(m < e) connectEdges(link[i][1], max(s, m+1), e, from);
}
void connectEdges(){
int connectL, connectR;
sort(arr+1, arr+n+1);
for(int i=1; i<=n; i++){
connectL = lower_bound(arr+1, arr+i, dat(arr[i].x, arr[i].y - arr[i].p)) - arr;
connectR = upper_bound(arr+i, arr+n+1, dat(arr[i].x, arr[i].y + arr[i].p)) - arr - 1;
if(connectL < i) connectEdges(xSegRoot[i], connectL, i-1, arr[i].idx);
if(i < connectR) connectEdges(xSegRoot[i], i+1, connectR, arr[i].idx);
}
for(int i=1; i<=n; i++) swap(arr[i].x, arr[i].y), swap(xSegRoot[i], ySegRoot[i]);
sort(arr+1, arr+n+1);
for(int i=1; i<=n; i++){
connectL = lower_bound(arr+1, arr+i, dat(arr[i].x, arr[i].y - arr[i].p)) - arr;
connectR = upper_bound(arr+i, arr+n+1, dat(arr[i].x, arr[i].y + arr[i].p)) - arr - 1;
if(connectL < i) connectEdges(xSegRoot[i], connectL, i-1, arr[i].idx);
if(i < connectR) connectEdges(xSegRoot[i], i+1, connectR, arr[i].idx);
}
for(int i=1; i<=n; i++) swap(arr[i].x, arr[i].y), swap(xSegRoot[i], ySegRoot[i]);
}
void SCC_dfs1(int x){
visited[x] = 1;
for(auto &y: link[x]){
if(!visited[y]) SCC_dfs1(y);
}
SCC_stk.push(x);
}
void SCC_dfs2(int x, int g){
SCC[g].push_back(x);
SCCnum[x] = g;
visited[x] = 1;
for(auto &y: linkRev[x]){
if(!visited[y]) SCC_dfs2(y, g);
}
}
void makeSCC(){
fill(visited, visited+vCount+1, false);
for(int i=1; i<=vCount; i++){
if(!visited[i]) SCC_dfs1(i);
}
fill(visited, visited+vCount+1, false);
while(!SCC_stk.empty()){
int x = SCC_stk.top(); SCC_stk.pop();
if(visited[x]) continue;
SCC.push_back({});
SCCLink.push_back({});
SCC_dfs2(x, (int)SCC.size() - 1);
}
// for(int i=0; i<(int)SCC.size(); i++){
// printf("SCC %d: ", i);
// for(auto &x: SCC[i]) printf("%d ", x);
// puts("");
// }
}
void operateSCC(){
int sccCount = (int)SCC.size();
queue<int> que;
/// check if valid
for(int i=0; i<sccCount; i++){
validSCC.push_back(0);
for(auto x: SCC[i]) if(1 <= x && x <= n) validSCC[i] = 1;
}
/// make SCC Link
for(int i=1; i<=vCount; i++){
for(auto j: link[i]){
if(SCCnum[i] == SCCnum[j]) continue;
SCCLink[SCCnum[i]].push_back(SCCnum[j]);
SCCindegree[SCCnum[j]]++;
}
}
for(int i=0; i<sccCount; i++){
if(!validSCC[i] && SCCindegree[i] == 0) que.push(i);
}
while(!que.empty()){
int tmp = que.front(); que.pop();
for(auto &nxt: SCCLink[tmp]){
SCCindegree[nxt]--;
if(validSCC[nxt]) continue;
if(SCCindegree[nxt] == 0) que.push(nxt);
}
}
/// get answers
for(int i=0; i<(int)SCC.size(); i++){
if(!validSCC[i]) continue;
ansMax++;
if(SCCindegree[i] == 0) ansMin++;
}
}
void calculate(){
vCount = n;
makeSegtree();
connectEdges();
makeSCC();
operateSCC();
}
}
int main(){
scanf("%d", &n);
// n = 500000;
cin >> command;
// command = "min";
for(int i=1; i<=n; i++){
scanf("%d %d %d", &arr[i].x, &arr[i].y, &arr[i].p);
// arr[i].x = i, arr[i].y = 1, arr[i].p = 1000000000;
arr[i].idx = i;
}
CALC_SCC::calculate();
if(command == "min") printf("%d", ansMin);
else printf("%d", ansMax);
}
'대회 > 기업 대회 & 올림피아드' 카테고리의 다른 글
| IOI 2022 업솔빙하기 (0) | 2023.02.04 |
|---|---|
| IOI 2021 후기 (14) | 2021.06.28 |
| APIO 2021 후기 (1) | 2021.05.27 |
| 폴리매스 제2회 코딩 챔피언십 풀이 및 후기 (5) | 2021.03.03 |
| KOI 2020 고등부 후기 (4) | 2020.11.17 |