취미로 코딩하기

※ 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 8551번 문제인 Blokada이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/8551

최소한 몇 개의 방향간선을 지워야 1번 정점에서 \(N\)번 정점으로의 연결된 경로가 없게 할 수 있는지를 묻는 문제이다.

이 값은 Max-Flow Min-Cut Theorem에 의해 각 간선의 가중치를 1으로 가정할 때의 1번 정점에서 \(N\)번 정점까지 흘릴 수 있는 최대 유량과 같다.

Dinic's Algorithm을 이용해 최대 유량을 구하고 문제를 해결하자. 모든 간선의 가중치가 1인 유량 그래프에서 Dinic's Algorithm의 시간복잡도는 \(O(\min(E\sqrt{E}, E\sqrt{V^{\frac{2}{3}}}))\)이므로 주어지는 입력의 크기가 상식적이라면 문제를 충분히 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <bitset>
#include <queue>
#include <cstring>
using namespace std;

int ans, src, snk, N, M;
vector<int> G[10002];
bitset<10002> flow[10002];
int lv[10002], trn[10002];
queue<int> que;

bool dfs(int cur) {
    if (cur == snk) return 1;
    int sz = G[cur].size();
    for (int &i = trn[cur]; i < sz; i++) {
        int nxt = G[cur][i];
        if (lv[nxt] != lv[cur] + 1 || !flow[cur][nxt]) continue;
        if (dfs(nxt)) {
            flow[cur][nxt] = 0;
            flow[nxt][cur] = 1;
            return 1;
        }
    }
    return 0;
}

bool bfs() {
    memset(lv, 0, sizeof(lv));
    lv[src] = 1;
    que.push(src);
    while (!que.empty()) {
        int cur = que.front(); que.pop();
        for (auto &nxt:G[cur]) {
            if (lv[nxt] || !flow[cur][nxt]) continue;
            lv[nxt] = lv[cur] + 1;
            que.push(nxt);
        }
    }
    return lv[snk];
}

void dinic() {
    while (bfs()) {
        memset(trn, 0, sizeof(trn));
        while (dfs(src)) ans++;
    }
}

void addedge(int x, int y) {
    flow[x][y] = 1;
    G[x].emplace_back(y);
    G[y].emplace_back(x);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;
    src = 1, snk = N;
    while (M--) {
        int x, y; cin >> x >> y;
        addedge(x, y);
    }
    dinic();
    cout << ans;
}

※ 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 34316번 문제인 사각형 개수 세기이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/34316

\(NM\le10^5\) 제약조건을 눈여겨보자. 이 조건으로부터 \(\min(N,M)\le\sqrt{10^5}\)임을 알 수 있다. 이러한 형태로 문제에서 주어지는 입력에 추가적인 제한을 주는 경우는 제법 자주 나타나므로 잘 알아두는 것이 좋다.

\(N\)과 \(M\) 중 더 작은 값을 행의 개수로 하고, 두 개의 행을 골라 각 열의 두 행의 수의 합을 각각 구하는 작업의 시간복잡도는 \(O(\min(N,M)^2\max(N,M))=O(\min(N,M)NM)\)과 같다. \(NM\le10^5\)와 \(\min(N,M)\le\sqrt{10^5}\)가 성립하므로, 이와 같은 접근의 연산량은 1초 안에 충분히 수행 가능하는 점을 관찰할 수 있다. 여기까지 관찰했다면 이후의 계산은 어렵지 않을 것이다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;

int R, C;
vector<int> v[316];
ll ans;
int cnt[20];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> R >> C;
    if (R < C) {
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) cin >> v[r].emplace_back();
        }
    }
    else {
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                cin >> v[c].emplace_back();
            }
        }
        swap(R, C);
    }

    for (int r1 = 0; r1 < R; r1++) {
        for (int r2 = r1 + 1; r2 < R; r2++) {
            memset(cnt, 0, sizeof(cnt));
            for (int c = 0; c < C; c++) {
                cnt[v[r1][c] + v[r2][c]]++;
            }
            for (int i = 2; i < 10; i++) ans += cnt[i] * cnt[20 - i];
            int v1 = cnt[10], v2 = v1 - 1;
            if (v1 & 1) v2 /= 2;
            else v1 /= 2;
            ans += v1 * v2;
        }
    }
    cout << ans;
}

※ 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 33922번 문제인 책 쌓기이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/33922

먼저, 주어진 책들을 가로가 세로 길이 이상인 방향으로 일괄적으로 돌려 생각해도 충분하다는 점을 관찰하자. 가로가 세로 길이 이상인 책 위에 세로가 가로 길이 이상인 책을 얹을 수 있다면 문제 제약에 의해 위의 책을 회전시킨 책도 올릴 수 있으며, 이것이 그 위로 새로 올릴 수 있는 책의 집합을 바꾸지 않기 때문이다.

주어진 책들의 몇몇 쌍에 대하여, 어떤 책을 다른 책 위에 올릴 수 있다는 관계가 성립하며, 이 관계는 poset을 이룬다. 따라서 이 문제는 이 책들의 집합의 poset에서의 최대 antichain의 크기를 구하는 것으로 해결할 수 있다. 같은 antichain에 속한 두 원소는 항상 서로 비교가 불가능해야 하므로, 책을 적절하게 뽑아 적절히 나열했을 때 가로의 길이가 strict하게 증가할 때 세로의 길이 또한 strict하게 증가하게끔 뽑을 수 있은 최대 책의 개수를 구하면 문제가 해결된다.

위의 문제는 LIS를 구하는 것으로 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

int N, ans;
int A[200001];
pair<int, int> P[200001];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> P[i].first >> P[i].second;
        if (P[i].first < P[i].second) swap(P[i].first, P[i].second);
    }
    sort(P + 1, P + N + 1, greater<>());
    memset(A, 0x3f, sizeof(A));
    A[0] = 0;
    for (int i = 1; i <= N; i++) {
        int L = 0, R = i;
        while (L < R) {
            int mid = (L + R) / 2 + 1;
            if (A[mid] >= P[i].second) R = mid - 1;
            else L = mid;
        }
        A[L + 1] = min(A[L + 1], P[i].second);
    }
    ans = N;
    while (A[ans] == 0x3f3f3f3f) ans--;
    cout << ans;
}

※ 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 33921번 문제인 아름다운 수열이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/33921

전형적인 0-1 Fractional Programming 문제이다. 0-1 Fractional Programming에 대한 설명은 다음 공부 일지에 서술하였다.

https://measurezero.tistory.com/2371

글쓴이는 구현 연습 겸 이 문제를 Dinkelbach's Algorithm으로 해결했다. 계산 과정에서 64비트 정수 자료형의 오버플로우가 발생할 수 있으므로, 구현 과정에서 128비트 정수 자료형을 사용했다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;
typedef __int128 lll;

ll N, K, X, Y = 1, XX, YY;
ll A[100001], B[100001];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> K;
    for (int i = 1; i <= N; i++) {
        cin >> B[i]; A[i] = B[i] * B[i];
        A[i] += A[i - 1], B[i] += B[i - 1];
    }
    XX = A[N], YY = B[N];

    while ((lll)X * YY != (lll)Y * XX) {
        X = XX, Y = YY;
        lll val = 0, mx = 0; int qL = 0, qR = 0;
        for (int i = 0, lft = 0; i <= N - K; i++) {
            val += (lll)(A[i] - A[i - 1]) * Y - (lll)(B[i] - B[i - 1]) * X;
            if (val < 0) val = 0, lft = i + 1;
            lll v = val + (lll)(A[i + K] - A[i]) * Y - (lll)(B[i + K] - B[i]) * X;
            if (v > mx) mx = v, qL = lft, qR = i + K;
        }
        if (mx) XX = A[qR] - A[qL - 1], YY = B[qR] - B[qL - 1];
    }

    cout << X / Y << '.'; X %= Y;
    for (int k = 0; k < 10; k++) {
        X *= 10;
        cout << X / Y;
        X %= Y;
    }
}

※ 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 22516번 문제인 Magical Girl Sayaka-chan이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/22516

\(K\)의 나열에서 증가했다가 감소했다가 다시 증가하는 부분이 있다면 이 부분을 단조증가 또는 단조감소의 형태로 순서를 바꿔 항상 이 부분의 반발력을 유지 또는 줄일 수 있음을 관찰하자. 이러한 관찰을 이용하면 \(K\)의 나열은 증가와 감소의 변화를 최소화하는 방식으로 나열된 경우에서 반발력이 최소가 되는 경우 중 하나를 항상 찾을 수 있음을 알 수 있다.

증가와 감소의 변화가 최소화되는 나열방식은 가장 작은 \(K\)에서 가장 큰 \(K\)까지 단조증가하면서 이동한 뒤 이 과정에서 사용하지 않은 모든 \(K\)를 단조감소하게 나열하는 것이다. 이는 모든 \(K\)값을 다 사용하면서 가장 작은 \(K\)에서 가장 큰 \(K\)까지 도달하는 두 개의 수열을 구성하는 것으로도 생각할 수 있으며, 여기까지 생각을 해냈다면 남은 문제는 경찰차 DP가 됨을 어렵지 않게 알 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;

ll ans = 0x3f3f3f3f3f3f3f3f;
int N, M, L;
int A[2001]; ll P[100001];
ll dp[2001][2001];

ll func(ll i, ll j) {
    if (i < j) swap(i, j);
    if (dp[i][j] < 0x3f3f3f3f3f3f3f3f) return dp[i][j];
    ll &ret = dp[i][j];
    if (i == j + 1) {
        for (int k = 0; k < j; k++) ret = min(ret, func(j, k) + (P[A[i]] - P[A[k] - 1]) / L);
    }
    else ret = func(i - 1, j) + (P[A[i]] - P[A[i - 1] - 1]) / L;
    return ret;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M >> L;
    for (int i = 0; i < N; i++) cin >> A[i];
    sort(A, A + N);
    for (int i = 1; i <= M; i++) cin >> P[i], P[i] += P[i - 1];

    memset(dp, 0x3f, sizeof(dp));
    dp[0][0] = 0;
    dp[1][0] = (P[A[1]] - P[A[0] - 1]) / L;
    for (int k = 0; k + 1 < N; k++) ans = min(ans, func(N - 1, k) + (P[A[N - 1]] - P[A[k] - 1]) / L);
    cout << ans;
}