2022.08.04 PS 일지

내일 국민대 알고리즘 대회라서 장장 두 달만에 키보드를 잡아보았다. 사실 그 사이에 쇼미더코드 치느라 딱 하루 한 적이 있긴 하다.

 

문제집

문제 링크

위상정렬 + 순서 관계 없는 것들끼리는 번호순으로.

예전에 풀어봤던 문제라 거의 5분 컷 한 것 같다.

풀이

칸 알고리즘으로 구현해야 한다. 코사라주 알고리즘(역간선 활용)으로는 아마 방법이 없을 것이다.

기존의 칸 알고리즘의 큐 부분을 우선순위 큐로 바꾸어 풀어주면 된다.

#include <bits/stdc++.h>
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
using namespace std;

const int N = 32003;
int n, m, ind[N];
vector<int> adj[N];
priority_queue<int,vector<int>,greater<>> pq;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    rep(i,1,m) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        ind[b]++;
    }
    rep(i,1,n) {
        if (ind[i] == 0) {
            pq.push(i);
        }
    }
    while (not empty(pq)) {
        int s = pq.top(); pq.pop();
        cout << s << ' ';
        for (auto u : adj[s]) {
            if (--ind[u] == 0) {
                pq.push(u);
            }
        }
    }
}

정렬 게임

문제 링크

40분만에 풀었다.

반성: 꽤 간단하기는 한데, 사례를 직접 써봤으면 좀 더 빨리 짰을 수도 있겠다.

풀이

#include <bits/stdc++.h>
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
using namespace std;

const int N = 100003, K = N;
int n, arr[N], k, idx[N];
pair<int,bool> d[N];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    rep(i,1,n) cin >> arr[i];
    cin >> k;
    int tmp = 0;
    rep(i,1,k) {
        int a, b;
        cin >> a >> b;
        tmp = max({tmp,a,b});
        d[a] = {i,0};
        d[b] = {i,1};
    }
    int m = n, n = tmp;
    sort(arr+1,arr+n+1);
    pair<int,bool> mx_idx = {0,0};
    int a = 1, b = n;
    bool flow = 0;
    for (int i = n, j; i >= 1; --i) {
        if (mx_idx < d[i]) {
            if (d[i].second) j = a++, flow = 1;
            else j = b--, flow = 0;
            mx_idx = d[i];
        } else {
            if (flow) j = a++;
            else j = b--;
        }
        idx[i] = j;
    }
    rep(i,1,n) cout << arr[idx[i]] << ' ';
    rep(i,n+1,m) cout << arr[i] << ' ';
}