hckim

문제링크

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

풀이

• Mo's
• 각 값마다 idx 를 deque 으로 관리
• 각 값의 idx 차이 최대값 등장횟수 cnt 로 관리
• cnt를 square root decomposition 하여 탐색속도 최적화
  • bucket 먼저 찾고 그 안에서 탐색

코드

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, K;
    cin >> N >> K;

    vector<long long> a(N);
    for (auto& e: a) {
        cin >> e;
    }

    int M;
    cin >> M;

    vector<tuple<int, int, int> > query(M);
    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        query[i] = {a, b, i};
    }

    int srqtN = sqrt(N);

    auto cmp = [&](tuple<int, int, int> p1, tuple<int, int, int> p2) {
        return get<0>(p1) / srqtN < get<0>(p2) / srqtN || (get<0>(p1) / srqtN == get<0>(p2) / srqtN && get<1>(p1) < get<1>(p2));
    };

    sort(all(query), cmp);
    
    vector<int> cnt(N, 0), bucket(N / srqtN + 1, 0);
    vector<deque<int> > pos(K + 1);
    auto include = [&](int idx) {
        int prev = -1;
        if (!pos[a[idx]].size()) pos[a[idx]].push_front(idx);
        else if (pos[a[idx]].back() < idx) prev = pos[a[idx]].back() - pos[a[idx]].front(),pos[a[idx]].push_back(idx);
        else prev = pos[a[idx]].back() - pos[a[idx]].front(), pos[a[idx]].push_front(idx);

        if (prev != -1) --cnt[prev], --bucket[prev / srqtN];
        int cur = pos[a[idx]].back() - pos[a[idx]].front();
        ++cnt[cur], ++bucket[cur / srqtN];
    };

    auto exclude = [&](int idx) {
        int prev = pos[a[idx]].back() - pos[a[idx]].front();
        --cnt[prev], --bucket[prev / srqtN];

        if (pos[a[idx]].back() == idx) pos[a[idx]].pop_back();
        else pos[a[idx]].pop_front();

        int cur = -1;
        if (pos[a[idx]].size()) cur = pos[a[idx]].back() - pos[a[idx]].front();

        if (cur != -1) ++cnt[cur], ++bucket[cur / srqtN];
    };

    auto getMax = [&]() {
        for (int i = bucket.size() - 1; i >= 0; --i) {
            if (!bucket[i]) continue;
            for (int j = (i + 1) * srqtN - 1; j >= i * srqtN; --j) {
                if (j >= cnt.size()) continue;
                if (!cnt[j]) continue;
                return j;
            }
        }
        return -1;
    };

    auto [l, r, idx] = query[0];
    for (int i = l; i <= r; ++i) {
        include(i);
    }

    vector<int> ans(M);
    for (auto [ll, rr, i]: query) {
        while (l > ll) include(--l);
        while (r < rr) include(++r);
        while (l < ll) exclude(l++);
        while (r > rr) exclude(r--);
        ans[i] = getMax();
    }
    for (auto e: ans) {
        cout << e << '\n';
    }
}

문제링크

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

풀이

• 자신의 w, h 보다 모두 큰 땅이 존재하면 그 땅은 그 큰 땅에 포함하여 사면 비용을 들이지 않고 사기 가능
• 그러한 땅들을 모두 제외하면 w 오름차순으로 정렬했을 때 h 는 내림차순으로 정렬됨
• i 번 땅과 j 번 땅을 같이 묶어서 사면, 그 사이에 있는 땅들은 포함해도 추가 비용 들지 않음
  • i번 땅과 묶인 땅들의 비용 = w[i] * h[j] 이므로
• 따라서, $dp[i]:$ i 번 땅까지 사는데 필요한 최소 비용이라고 정의하면
• $dp[i] = min_{0 \leq j < i} (dp[j] + w[i] * h[j + 1]) $
  • CHT 적용
    • x: 증가
    • 기울기: 감소
    • getMin

코드

• 시간복잡도: $O(N)$

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()

struct line {
    long long m, c;
    long long eval(long long x) {return m * x + c;}
    long long intersecX(line l) {return (c - l.c) / (l.m - m);}
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

    vector<pair<long long, long long> > v(N);

    for (int i = 0; i < N; ++i) {
        cin >> v[i].first >> v[i].second;
    }

    sort(all(v));

    vector<pair<long long, long long> > v2;

    long long prevMax = v.back().second;
    v2.push_back(v.back());
    for (int i = N - 2; i >= 0; --i) {
        if (v[i].second > prevMax) {
            v2.push_back(v[i]);
            prevMax = v[i].second;
        }
    }

    reverse(all(v2));

    deque<line> dq;
    long long ans = 0;
    dq.push_back({v2[0].second, 0});
    for (int i = 0; i < v2.size(); ++i) {
        while (dq.size() >= 2 && dq[0].eval(v2[i].first) >= dq[1].eval(v2[i].first)) dq.pop_front();
        ans = dq.front().eval(v2[i].first);
        ans = dq.front().eval(v2[i].first);
        if (i == v2.size() - 1) break;
        line cur = {v2[i + 1].second, ans};
        while (dq.size() >= 2 && cur.intersecX(dq.back()) <= dq.back().intersecX(dq[dq.size() - 2])) dq.pop_back();
        dq.push_back(cur);
    }

    cout << ans << '\n';
}

문제링크

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

풀이

• 구조의 가치는 구조를 이루는 간선의 수이다.
• 링 또는 선형으로만 구성되어있다는 것은 한 정점에서 나가는 간선, 들어오는 간선은 최대 1개씩 있을 수 있다는 뜻
• 간선의 시작점, 도착점 두 그룹으로 이분매칭

코드

• 시간복잡도: $O(VE) = O(NM)$

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int TC; cin >> TC;
    while (TC--) {
        int N, M;
        cin >> N >> M;

        vector<vector<int> > adj(N);
        vector<int> B(N, -1);

        for (int i = 0; i < M; ++i) {
            int u, v;
            cin >> u >> v;
            adj[u].push_back(v);
        }
        vector<int> visited(N, 0);
        function<bool(int)> f = [&](int a) {
            visited[a] = true;
            for (auto b: adj[a]) {
                if (B[b] == -1 || (!visited[B[b]] && f(B[b]))) {
                    B[b] = a;
                    return true;
                }
            }
            return false;
        };

        long long ans = 0;
        for (int i = 0; i < N; ++i) {
            fill(all(visited), false);
            ans += f(i);
        }
        cout << ans << '\n';
    }
}

문제링크

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

풀이

• 반복 부분문자열의 길이의 최대는 max(lcp[i]) 이다.

코드

• 시간복잡도: $O(Nlog^2N)$

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    auto buildSA = [&](string& s) {
        int N = s.size();
        vector<int> sa(N, 0), r(2 * N, 0), nr(2 * N, 0);
        for (int i = 0; i < N; ++i) {
            sa[i] = i;
            r[i] = s[i];
        }
        for (int d = 1; d < N; d <<= 1) {
            auto cmp = [&](int i, int j) {
                return r[i] < r[j] || (r[i] == r[j] && r[i + d] < r[j + d]);
            };
            sort(all(sa), cmp);
            nr[sa[0]] = 1;
            for (int i = 1; i < N; ++i) {
                nr[sa[i]] = nr[sa[i - 1]] + cmp(sa[i - 1], sa[i]);
            }
            r = nr;
        }
        return sa;
    };

    auto buildLCP = [&](string& s) {
        int N = s.size();
        auto sa = buildSA(s);
        vector<int> lcp(N), isa(N);
        for (int i = 0; i < N; ++i) {
            isa[sa[i]] = i;
        }
        for(int k = 0, i = 0;i < N;++i) {
            if(isa[i]){
                for(int j = sa[isa[i]-1]; max(i, j) + k < N && s[i+k] == s[j+k]; ++k);
                lcp[isa[i]] = (k ? k-- : 0);
            }
        }
        return lcp;
    };

    int L;
    cin >> L;
    string s;
    cin >> s;

    auto lcp = buildLCP(s);

    cout << *max_element(lcp.begin() + 1, lcp.end());
}

문제링크

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

풀이

• 문자열의 서로 다른 부분 문자열 = 모든 접미사의 접두사
• 각 접미사에 대해 lcp 상의 앞 인덱스에 있는 접미사와 겹치는 접두사부분 길이만큼이 중복
• $ans = \frac{N(N + 1)}{2} - \sum_{i = 1}^{N - 1} lcp[i]$

코드

• 시간복잡도: $O(Nlog^2N)$

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string s;
    cin >> s;

    auto buildSA = [&](string& s) {
        int N = s.size();
        vector<int> sa(N), r(2 * N, 0), nr(2 * N, 0);
        for (int i = 0; i < N; ++i) {
            sa[i] = i;
            r[i] = s[i];
        }
        for (int d = 1; d < N; d <<= 1) {
            auto cmp = [&](int i, int j) {
                return r[i] < r[j] || (r[i] == r[j] && r[i + d] < r[j + d]);
            };
            sort(all(sa), cmp);
            nr[sa[0]] = 1;
            for (int i = 1; i < N; ++i) {
                nr[sa[i]] = nr[sa[i - 1]] + cmp(sa[i - 1], sa[i]);
            }
            r = nr;
        }
        return sa;
    };

    auto buildLCP = [&](string& s) {
        int N = s.size();
        auto sa = buildSA(s);
        vector<int> lcp(N, 0), isa(N);
        for (int i = 0; i < N; ++i) {
            isa[sa[i]] = i;
        }
        for(int k = 0, i = 0;i < N;++i) {
            if(isa[i]){
                for(int j = sa[isa[i]-1]; max(i, j) + k < N && s[i+k] == s[j+k]; ++k);
                lcp[isa[i]] = (k ? k-- : 0);
            }
        }
        return lcp;
    };

    auto lcp = buildLCP(s);
    long long N = s.size();
    long long ans = N * (N + 1) / 2;
    for (int i = 1; i < N; ++i) {
        ans -= lcp[i];
    }
    cout << ans << '\n';
}

문제링크

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

풀이

• 시작점에서 끝지점까지 최대 용량을 2로 해두고 MCMF 해주기
• 두 경로사이에 겹치는 정점, 간선 없게하기위해 각 정점 한번씩만 지날 수 있도록 -> 정점분할
  • v : 2v - 1 -> 2v

코드

• 시간복잡도: $O((V+E)f) = O(V+E)$

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

struct Edge {
    int to, c, f, cost;
    Edge* reverse;

    Edge() {
        to = c = f = cost = 0;
        reverse = nullptr;
    }
    Edge(int to_, int c_, int cost_) {
        to = to_;
        c = c_;
        cost = cost_;
        f = 0;

        reverse = nullptr;
    }

    int reisidual() {
        return c - f;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int v, e;
    while (cin >> v >> e) {
        int S = 1;
        int T = 2 * v - 1;
        vector<vector<Edge*> > adj(2 * v + 1);

        auto makeEdge = [&](int u, int v, int c, int cost) {
            auto e1 = new Edge(v, c, cost);
            auto e2 = new Edge(u, 0, -cost);
            e1 -> reverse = e2;
            e2 -> reverse = e1;
            adj[u].push_back(e1);
            adj[v].push_back(e2);
        };

        while (e--) {
            int u, v, c;
            cin >> u >> v >> c;
            makeEdge(2 * u, 2 * v - 1, 1, c);
        }
        makeEdge(1, 2, 2, 0);
        for (int i = 2; i <= v; ++i) {
            makeEdge(2 * i - 1, 2 * i, 1, 0);
        }

        int maxFlow = 0;
        int minCost2 = 0;
        while (true) {
            vector<Edge*> prev(2 * v + 1, nullptr);
            queue<int> q;
            vector<int> inQ(2 * v + 1, false);
            vector<int> minCost(2 * v + 1, 1e9);
            q.push(S);
            minCost[S] = 0;
            inQ[S] = true;
            while (q.size()) {
                int cur = q.front();
                q.pop();
                inQ[cur] = false;
                for (auto e: adj[cur]) {
                    if (e -> reisidual() > 0 && minCost[e -> to] > minCost[cur] + e -> cost) {
                        minCost[e -> to] = minCost[cur] + e -> cost;
                        prev[e -> to] = e;
                        if (!inQ[e -> to]) {
                            q.push(e -> to);
                            inQ[e -> to] = true;
                        }
                    }
                }
            }

            if (!prev[T]) break;

            int flow = 1e9;
            for (auto cur = T; cur != S; cur = prev[cur] -> reverse -> to) {
                flow = min(flow, prev[cur] -> reisidual());
            }

            for (auto cur = T; cur != S; cur = prev[cur] -> reverse -> to) {
                prev[cur] -> f += flow;
                prev[cur] -> reverse -> f -= flow;
            }
            maxFlow += flow;
            minCost2 += minCost[T];
        }
        cout << minCost2 << '\n';
    }
}

문제링크

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

풀이

• $dp[i]:$ i 번 나무를 완전히 자르는데 필요한 총 충전비용의 최솟값이라 하자
• $dp[i] = max_{0 <= j < i} (dp[j] + b[j] * a[i])$ 이다.
  • 이는 컨벡스헐트릭(Convex hull trick) 을 적용할 수 있는 점화식 형태이다.
• 또한 $b[N] = 0$ 이므로 $N$ 번 나무를 모두 자른 이후에는 충전비용이 0이 되고 이는 곧 문제의 답이 $dp[N]$ 임을 알 수 있다.

코드

• 시간복잡도: $O(N)$

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
struct line {
    long long m, c;
    long long eval(long long x) { return m * x + c; }
    long double intersectX(line l) { return (long double) (c - l.c) / (l.m - m); }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;
    vector<long long> a(N), b(N);
    for (auto& e: a) {
        cin >> e;
    }
    for (auto& e: b) {
        cin >> e;
    }

    deque<line> dq;
    long long ans = 0;
    dq.push_front({b[0], 0});
    for (int i = 1; i < N; i++) {
        while (dq.size() >= 2 && dq[0].eval(a[i]) >= dq[1].eval(a[i]))
            dq.pop_front();
        ans = dq.front().eval(a[i]);
        line cur = {b[i], ans};
        while (dq.size() >= 2 && cur.intersectX(dq.back()) <= dq.back().intersectX(dq[dq.size() - 2]))
            dq.pop_back();
        dq.push_back(cur);
    }
    cout << ans << '\n';
}

문제링크

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

풀이

• $dp[i]:$ i 번 병사들로 특공대를 만들었을 때 조정된 전체 전투력의 최댓값이라고 하고
• $v[i], pv[i]$ 는 각각 병사의 전투력과 그 누적합 배열이라 하자
• $dp[i]$ 는 i 번 병사가 속해있는 특공대가 앞의 몇명을 포함하느냐에 따라서 생각해 볼 수 있고 그를 나타낸 점화식은 다음과 같다.
  • $dp[i] = max_{0 <= j  < i} (dp[j] + a * (pv[i] - pv[j])^2 + b * (pv[i] - pv[j]) + c)$
• 이를 정리하면 다음과 같다.
  • $dp[i] = max_{0 <= j < i} (-2a*pv[j]*pv[i] + dp[j] + a * pv[j]^2 - pv[j] + a*pv[i]^2 + b* pv[i] + c)$
• 컨벡스헐트릭(Convex hull trick)을 적용할 수 있는 점화식 형태이며 $pv$ 배열또한 단조성을 가지고 있으므로 $O(N)$ 에 해결할 수 있다.

코드

• 시간복잡도: $O(N)$

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
struct line {
    long long m, c;
    long long eval(long long x) { return m * x + c; }
    long double intersectX(line l) { return (long double) (c - l.c) / (l.m - m); }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N;
    cin >> N;
    long long a, b, c;
    cin >> a >> b >> c;
    vector<long long> v(N + 1, 0), pv(N + 1, 0);
    for (int i = 1; i <= N; ++i) {
        cin >> v[i];
        pv[i] = v[i] + pv[i - 1];
    }

    deque<line> dq;
    dq.push_front({0, 0});
    long long ans = 0;
    for (int i = 1; i <= N; i++) {
        while (dq.size() >= 2 && dq[0].eval(pv[i]) <= dq[1].eval(pv[i]))
            dq.pop_front();

        ans = dq.front().eval(pv[i]);

        line cur = {-2LL * a * pv[i], a * pv[i] * pv[i] - b * pv[i] + ans +a * pv[i] * pv[i] + b * pv[i] + c };
        while (dq.size() >= 2 && cur.intersectX(dq.back()) <= dq.back().intersectX(dq[dq.size() - 2]))
            dq.pop_back();
        dq.push_back(cur);
    }

    cout << ans + a * pv[N] * pv[N] + b * pv[N] + c << '\n';
}