2023 3주차 멘토링 일지

CCO 2022 Day 1을 돌아 만점을 받았다. 2시간 16분 걸렸는데 상당히 쉬운 셋이라는 느낌이 들었다.

 

[BOJ 25220] Rainy Markets (0:50)

일단 해가 존재하는지부터 판별해보자. 각 사람에 대해, 왼쪽 정류장에 가는 경우를 $L$, 우산을 사는 경우를 $M$, 오른쪽 정류장에 가는 경우를 $R$이라고 한다. 왼쪽부터 보면서 최대한 $L$, $M$, $R$ 순으로 그리디하게 배정한다. 자리가 없는 경우 불가능, 아니면 가능이 된다.

 

이제 해가 존재할 때, $\sum M$을 최소화시키는 방법을 찾아보자. 이번에는 오른쪽부터 보면서, $L$에 있는 사람을 최대한 $R$로 옮기고, 그래도 자리가 남으면 $M$에 있는 사람을 $R$로 옮기고, 그래도 자리가 남으면 $M$에 있는 사람을 $L$로 옮긴다. $L$과 $M$의 사람을 $R$로 옮기는 것은 별 문제가 없어 보이지만, $M$에 있는 사람을 $L$로 옮겨도 되는 걸까? 그로 인해 더 왼쪽에 있는 $M$을 $R$로 옮기지 못하게 될 수는 없을까? 핵심 관찰은, 어떤 오른쪽의 $M$ 하나를 $L$로 옮겼을 경우, 그로 인해 왼쪽에서 $M$을 $R$로 옮기지 못하게 되는 $M$은 최대 하나라는 것이다. 따라서, 이렇게 해도 최적해임을 보장할 수 있고, 문제를 $O(N)$에 풀 수 있다.

 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
ll arr[1000002], people[1000002], umb[1000002];
ll L[1000002], M[1000002], R[1000002];

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%lld", &arr[i]);
    for(int i=1; i<n; i++) scanf("%lld", &people[i]);
    for(int i=1; i<n; i++) scanf("%lld", &umb[i]);

    /// 최대한 왼쪽으로
    for(int i=1; i<n; i++){
        L[i] = min(people[i], arr[i] - R[i-1]);
        M[i] = min(people[i]-L[i], umb[i]);
        R[i] = min(people[i]-L[i]-M[i], arr[i+1]);
        if(L[i]+M[i]+R[i] != people[i]){
            puts("NO");
            exit(0);
        }
    }

    /// 이제는 최대한 오른쪽으로, M을 늘리지 않으면서
    for(int i=n-1; i>=1; i--){
        int x = min(L[i], arr[i+1]-R[i]-L[i+1]);
        L[i] -= x, R[i] += x;
        x = min(M[i], arr[i+1]-R[i]-L[i+1]);
        M[i] -= x, R[i] += x;
        x = min(M[i], arr[i]-L[i]-R[i-1]);
        M[i] -= x, L[i] += x;
    }

    puts("YES");
    printf("%lld\n", accumulate(M+1, M+n, 0LL));
    for(int i=1; i<n; i++) printf("%lld %lld %lld\n", L[i], M[i], R[i]);
}

 

[BOJ 25219] Alternating Heights (0:57)

$[L, R]$ 구간을 만드는 것이 가능하다면 $[L, R-1]$도 가능하며, $[L, R]$이 불가능하면 $[L, R+1]$이 불가능하다. 따라서 각 $L$별로 가능한 최대 $R$값을 구해 놓는 것이 필요한데, 이분 탐색을 할 수도 있겠지만, 여기서는 투 포인터를 이용한다. $L$과 $R$을 투 포인터로 가지고 가면 가능성 판별을 $O(N)$에 할 때 $O(N^2)$에 문제를 해결할 수 있다.

 

가능성 판별은 쉽다. 대소 관계를 그래프로 보고 사이클이 있는지를 판별해야 하는데, 위상 정렬이 가능한지를 판별하면 된다. 시간 복잡도는 $O(N^2)$이다.

 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, k, q;
int arr[3002];
int lim[3002];

vector<int> link[3002];
int deg[3002];

bool able(int l, int r){
    for(int i=1; i<=n; i++) link[i].clear(), deg[i]=0;
    for(int i=l, dir=0; i<r; i++, dir=!dir){
        if(dir==0) link[arr[i]].push_back(arr[i+1]), deg[arr[i+1]]++;
        else       link[arr[i+1]].push_back(arr[i]), deg[arr[i]]++;
    }

    queue<int> que;
    for(int i=1; i<=n; i++) if(!deg[i]) que.push(i);
    while(!que.empty()){
        int x = que.front(); que.pop();
        for(auto y: link[x]){
            deg[y]--;
            if(!deg[y]) que.push(y);
        }
    }
    for(int i=1; i<=n; i++) if(deg[i]) return false;
    return true;
}

int main(){
    scanf("%d %d %d", &n, &k, &q);
    for(int i=1; i<=n; i++){
        scanf("%d", &arr[i]);
    }
    for(int a=1, b=1; a<=n && b<=n; ){
        if(able(a, b)){
            if(b==n) lim[a] = n, a++;
            else b++;
        }
        else{
            lim[a] = b-1, a++;
            if(a>b) b++;
        }
    }
    for(int i=1; i<=q; i++){
        int l, r;
        scanf("%d %d", &l, &r);
        printf("%s\n", lim[l] >= r ? "YES" : "NO");
    }
}

 

[BOJ 25221] Double Attendance (2:16)

Subtask 1과 2는 쉬우나 Full Task와는 조금 방향이 다르다. Subtask 3을 보자. 이 경우 $B-A \le 2K$라는 조건이 있는데 이것은 어떤 슬라이드를 듣고 다른 방으로 갔다 와서 다시 그 슬라이드를 볼 일이 없다는 것이다. 여기서 DP를 다음과 같이 정의한다.

 

$DP[d][i]$는 $d$번 강의실 ($d \in \{ 0, 1 \}$)에 시간 $t$에 있을때 지금까지 $i$개 슬라이드를 본 상태가 가능하다고 할 때, 최소의 $t$로 정의하자. $DP[d][i]$에서 두 가지 선택지가 있는데, $(d, i) \rightarrow (d, i+1)$의 경우 다음 강의 때까지 기다리는 것을 해 주면 된다. $(d, i) \rightarrow (!d, i+x)$의 경우 시각 $i$에서 다음 강의실로 이동해 주면 되고, 시각 $DP[d][i]+k$에 슬라이드가 있으면 $x=1$, 아니면 $x=0$이 될 것이다. DP를 전이하는 순서가 조금 중요한데, $i$가 그대로인 것부터 하고 $i$가 증가하는 것을 해 줘야 한다.

 

위 풀이는 Subtask 3을 풀 수 있지만, 어떤 슬라이드를 중복해서 세는 문제 때문에 Full Task를 해결하지 못한다. 이를 해결하기 위해 해에 대한 관찰을 하나 더 해주어야 한다. 강의실 $0$에서 어떤 슬라이드 $A$를 보고, 다른 강의실 $1$로 갔다가, 다시 강의실 $0$에서 슬라이드 $A$를 보러 올 필요가 없다. 강의실 $0$에서 슬라이드 $A$가 끝나는 시점을 $t$라 할 때, 시점 $t-k$ 전까지는 강의실 $1$에서 강의실 $0$으로 돌아올 이유가 전혀 없다. 온다고 해도 새로운 슬라이드를 볼 가능성이 없기 때문이다. 따라서 전이 $(d, i) \rightarrow (!d, i+x)$를 해줄 때, 시간을 $k$만큼만 더하지 말고, 위 사항을 고려해 가끔씩은 추가로 더해주기로 한다. 이렇게 전이를 하면 한 슬라이드를 두 번 보는 경우를 고려할 필요가 없다.

 

최종 시간 복잡도는 $O(N \log N)$이다.

 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n[2], k;
pair<ll, ll> arr[2][300002];
vector<ll> pl[2], pr[2];
ll DP[2][600002];
int ans;

inline int idx(int d, ll t){
    return upper_bound(pl[d].begin(), pl[d].end(), t) - pl[d].begin();
}

inline bool inside(int d, ll t){
    int x = idx(d, t);
    return x && arr[d][x].first <= t && t <= arr[d][x].second;
}

inline int sum(int d, ll L, ll R){
//    printf("%d %lld %lld: %d %d\n", d, L, R, lower_bound(pl[d].begin(), pl[d].end(), R) - pl[d].begin(),
//           lower_bound(pr[d].begin(), pr[d].end(), L) - pr[d].begin());
    return (upper_bound(pl[d].begin(), pl[d].end(), R) - pl[d].begin())
         - (lower_bound(pr[d].begin(), pr[d].end(), L) - pr[d].begin());
}

int main(){
    scanf("%d %d %d", &n[0], &n[1], &k); k*=2;
    for(int d=0; d<=1; d++){
        for(int i=1; i<=n[d]; i++){
            scanf("%lld %lld", &arr[d][i].first, &arr[d][i].second);
            arr[d][i].first = arr[d][i].first * 2 + 1;
            arr[d][i].second = arr[d][i].second * 2 - 1;
            pl[d].push_back(arr[d][i].first);
            pr[d].push_back(arr[d][i].second);
        }
        sort(arr[d]+1, arr[d]+n[d]+1);
        sort(pl[d].begin(), pl[d].end());
        sort(pr[d].begin(), pr[d].end());
    }
    arr[0][n[0]+1] = arr[1][n[1]+1] = make_pair(ll(2e18), ll(2e18));
    for(int i=0; i<=1; i++) for(int j=0; j<=600000; j++) DP[i][j] = 1e18;
    DP[0][0] = 0;
    for(int i=0; i<=n[0]+n[1]; i++){
        /// 이후로 보내기
        for(int s=0; s<2; s++){
            int e = !s;
            ll L = DP[s][i] + k;
            ll R = L;
            if(inside(s, DP[s][i])) R = max(R, arr[s][idx(s, DP[s][i])].second-k+1);
            ll S = sum(e,L,R);
            DP[e][i+S] = min(DP[e][i+S], R);
        }
        for(int s=0; s<2; s++){
            DP[s][i+1] = min(DP[s][i+1], arr[s][idx(s, DP[s][i])+1].first);
        }
//        printf("%d: %lld %lld\n", i, DP[0][i], DP[1][i]);
    }
    for(int i=0; i<=n[0]+n[1]; i++) if(DP[0][i] < 1e17 || DP[1][i] < 1e17) ans = i;
    printf("%d", ans);
}