hckim

문제링크

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

풀이

• 가장 먼 점 두개는 convex hull 을 이루는 점이다.
• rotating calipers 테크닉으로 가장 먼 점이 될 수 있는 후보를 $O(N)$ 에 구한다
  
  1. 초기 캘리퍼스 벡터 =  y 축, 초기 두점 = 가장 왼쪽점(pl)과 가장 오른쪽점(pr)
  2. 볼록 껍질을 회전시킴
  3. 캘리퍼스와 다음으로 만나는 점 중 먼저 바뀌는 점은 직선 pl pl + 1, 과 직선 pr pr + 1 중 캘리퍼스와 각이 더 작은 직선의 점
     1. 벡터 외적으로 구함
  4. 위 과정을 초기 두점 나올때까지 하는데 최대 $O(N)$ 번

코드

• 시간복잡도: $O(NlogN)$
  • (convex hull)

#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 ccw = [&](pair<long long , long long >& p1, pair<long long , long long >& p2, pair<long long , long long >& p3) {
        return (p2.first - p1.first) * (p3.second - p2.second) - (p2.second - p1.second) * (p3.first - p2.first);
    };
    auto distSqr = [&](pair<long long , long long >& p1, pair<long long , long long >& p2) {
        return (p2.first - p1.first) * (p2.first - p1.first) + (p2.second - p1.second) * (p2.second - p1.second);
    };
    auto buildConvexHull = [&](vector<pair<long long , long long > >& p) {

        swap(p[0], *min_element(all(p)));
        auto base = p[0];

        auto cmp = [&](pair<long long , long long >& p1, pair<long long , long long >& p2) {
            auto ccw_ = ccw(base, p1, p2);
            if (ccw_ == 0) {
                return distSqr(base, p1) < distSqr(base, p2); 
            }
            return ccw_ > 0;
        };
        sort(all(p), cmp);
        stack<pair<long long , long long > > st;
        st.push(p[0]);
        st.push(p[1]);
        for (int i = 2; i < p.size(); ++i) {
            auto p2 = st.top(); st.pop();
            auto p1 = st.top();
            auto p3 = p[i];
            auto ccw_ = ccw(p1, p2, p3);
            while (ccw_ < 0) {
                p2 = p1;
                st.pop(); p1 = st.top();
                ccw_ = ccw(p1, p2, p3);
            }

            if (ccw_ > 0) {
                st.push(p2);
                st.push(p3);
            } else {
                st.push(p3);
            }
        }
        vector<pair<long long , long long > > convexHull(st.size());
        while (st.size()) {
            convexHull[st.size() - 1] = st.top();
            st.pop();
        }

        return convexHull;
    };

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

        vector<pair<long long, long long> > v(N);
        for (auto& e: v) {
            cin >> e.first >> e.second;
        }

        auto ch = buildConvexHull(v);
        auto pl = min_element(all(ch)) - ch.begin();
        auto pr = max_element(all(ch)) - ch.begin();

        pair<int, int> answer = {pl, pr};
        long long tmp = distSqr(ch[pl], ch[pr]);
        int chSize = ch.size();
        for (int i = 0; i < chSize; ++i) {
            pair<long long, long long> v1 = {ch[(pl + 1) % chSize].first - ch[pl].first, ch[(pl + 1) % chSize].second - ch[pl].second};
            pair<long long, long long> v2 = {ch[pr].first - ch[(pr + 1) % chSize].first, ch[pr].second - ch[(pr + 1) % chSize].second};
            if (v1.first * v2.second - v1.second * v2.first > 0) {
                pl = (pl + 1) % chSize;
            } else {
                pr = (pr + 1) % chSize;
            }

            if (tmp < distSqr(ch[pl], ch[pr])) {
                tmp = distSqr(ch[pl], ch[pr]);
                answer = {pl, pr};
            }
        }

        cout << ch[answer.first].first << ' ' << ch[answer.first].second << ' ';
        cout << ch[answer.second].first << ' ' << ch[answer.second].second << '\n';
    }
}

문제링크

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

풀이

• 업데이트 쿼리가 없으므로 쿼리 처리 순서를 속도면에서 유리하게 바꿔서 푼다
• 원소값에 대한 cnt 배열 관리
  • 구간 집합에 원소가 추가되고 추가되면서 원소 cnt 가 1 이면 종류 증가
  • 구간 집합에 원소가 제거되고 제거되면서 원소 cnt 가 0 이면 종류 감소
• Mo's algorithm 으로 쿼리를 정렬하여 이전 쿼리 결과 재사용률 높임

코드

• 시간복잡도: $O((N + M)\sqrt{N}T)$
  • $T:$ 원소 추가 제거하는데 걸리는 시간 (이 문제에서는 $O(1)$)

#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;
    cin >> N;

    vector<int> 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 l, r;
        cin >> l >> r;
        query[i] = {l - 1, r - 1, i};
    }

    int sqrtN = sqrt(N);
    auto cmp = [&](tuple<int, int, int> t1, tuple<int, int, int> t2) {
        return get<0>(t1) / sqrtN < get<0>(t2) / sqrtN || (get<0>(t1) / sqrtN == get<0>(t2) / sqrtN && get<1>(t1) < get<1>(t2));
    };
    sort(all(query), cmp);

    vector<int> answer(M);
    vector<int> cnt(1e6 + 1, 0);
    int l = 1;
    int r = 0;
    int tmp = 0;
    for (auto [i, j, ai]: query) {
        while (i < l) tmp += ++cnt[a[--l]] == 1;
        while (i > l) tmp -= --cnt[a[l++]] == 0;
        while (j < r) tmp -= --cnt[a[r--]] == 0;
        while (j > r) tmp += ++cnt[a[++r]] == 1;
        answer[ai] = tmp;
    }

    for (auto e: answer) {
        cout << e << '\n';
    }
}

문제링크

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

풀이

• 시계 시간이 같다는건 각 시계의 바늘들의 위치관계가 같다는 것
• $v[x]:$ x 각도에 있는지 없는지로 정의
• v1 이랑 v2 를 shift 한거랑 같을 때가 있는지 찾기
  • 는 v1 두개 붙인 배열에서 v2 찾기랑 같음

코드

• 시간복잡도: 
  • $v[x]: $ x 각도 바늘 유무로 하면 $O(360,000 * 3 + 2N)$
  • $v[i]: $ 각도 오름차순 기준으로 i + 1 번째 바늘과 i 번째 바늘의 차이로 정의하면 $O(2N + NlogN + N + 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);

    int N;
    cin >> N;
    
    vector<int> a(360000), b(360000);
    for (int i = 0; i < N; ++i) {
        int num;
        cin >> num;
        a[num] = 1;
    }
    for (int i = 0; i < N; ++i) {
        int num;
        cin >> num;
        b[num] = 1;
    }

    auto buildPi = [&](vector<int>& p) {
        int pLen = p.size();
        vector<int> pi(pLen, 0);
        for (int j = 0, i = 1; i < pLen; ++i) {
            while (j > 0 && p[i] != p[j]) j = pi[j - 1];
            if (p[i] == p[j]) ++j, pi[i] = j;
        }
        return pi;
    };
    auto kmp = [&](vector<int>& s, vector<int>& p) {
        // find p in s
        vector<int> answer;
        int sLen = s.size(), pLen = p.size();
        auto pi = buildPi(p);
        for (int j = 0, i = 0; i < 2 * sLen; ++i) {
            while (j > 0 && s[i % sLen] != p[j]) j = pi[j - 1];
            if (j == pLen - 1) answer.push_back(i % sLen - pLen + 2), j = pi[j];
            else ++j;
        }
        return answer;
    };

    auto answer = kmp(a, b);
    if (answer.size()) {
        cout << "possible\n";
    } else {
        cout << "impossible\n";
    }
}

문제링크

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

풀이

• 최대 유량문제에서 증가경로를 찾을 때 cost 에 대해 최단 경로로 찾음
• 역방향 간선의 cost 가 음수이므로 음수간선에 대해서도 동작해야함
  • SPFA

코드

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

#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 N, M;
    cin >> N >> M;

    vector<int> A(N + 1, 0), B(M + 1, 0);
    vector<vector<Edge*> > adj(N + M + 2);
    int S = 0;
    int T = adj.size() - 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);
    };
    
    for (int i = 1; i <= N; ++i) {
        makeEdge(S, i, 1, 0);
        int cnt = 0;
        cin >> cnt;
        while (cnt--) {
            int v, cost;
            cin >> v >> cost;
            makeEdge(i, N + v, 1, cost);
        }
    }
    for (int i = 1; i <= M; ++i) {
        makeEdge(N + i, T, 1, 0);
    }
    
    int maxFlow = 0;
    int minCost2 = 0;
    while (true) {
        vector<Edge*> prev(N + M + 2, nullptr);
        queue<int> q;
        vector<int> inQ(N + M + 2, false);
        vector<int> minCost(N + M + 2, 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 << maxFlow << '\n';
    cout << minCost2 << '\n';
}

문제링크

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

풀이

• SA 구하기
  • suffix 들을 앞부분 길이 1, 2, 4, 8 ... 에 대해서 정렬
  • 앞부분 길이 d 에서 정렬한 정보를 2 * d 를 정렬할 때 이용할 수 있음
• LCP 구하기 (Kasai's algorithm)
  • 인덱스 0 시작, 1시작, ... 접미사들에 대해서 차례로 lcp 를 구한다
  • $lcp[isa[i]] = k$ 이면 $lcp[isa[i + 1]] \geq k - 1$ 임을 이용한다

코드

• 시간복잡도
  • 문자열길이: $N$ 
  • SA: $O(Nlog^2N)$
    • counting sort 로 정렬시 $O(NlogN)$
  • LCP: $O(O(SA) + N)$

#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);
        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;
        }
        for (auto& e: sa) {
            cout << e + 1 << ' ';
        }
        cout << '\n';
        return sa;
    };

    auto buildLCP = [&](string& s) {
        int N = s.size();
        auto sa = buildSA(s);
        vector<int> isa(N), lcp(N);
        for (int i = 0; i < N; ++i) {
            isa[sa[i]] = i;
        }

        for (int k = 0, i = 0; i < N; ++i) {
            if (isa[i] == 0) continue;
            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);

    for (int i = 0; i < lcp.size(); ++i) {
        if (i) {
            cout << lcp[i] << ' ';
        } else {
            cout << "x ";
        }
    }
}

문제 링크

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

풀이 1. Hashing, Rabin-Karp algorithm, Parametric search

• 길이 $l$ 인 부분 문자열이 전체 문자열내에서 두번 이상 등장한다고 하자
• 그 부분 문자열의 부분 문자열들(길이 $1, 2, ..., l$) 또한 전체 문자열내에서 두번 이상 등장한다
• 따라서 결정문제: 길이 $l$ 부분문자열이 2번이상 등장하는가? 에 대한 답의 분포는 이분적이다($T, ..., T, F, F, ..., F$)
• 각 결정문제를 해결할 때에는 라빈카프 알고리즘의 롤링해쉬함수를 이용한다

코드 1.

• 시간복잡도: $O(LlogL)$
  • Parametric search: $O(logL)$
  • 결정문제: $O(L)$

#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 L;
    cin >> L;
    string s;
    cin >> s;

    long long MOD = 1e5 + 3;
    long long MUL = 2;

    auto check = [&](int l) {
        vector<vector<int> > hashTable(MOD);
        long long h = 0;
        long long MUL_POW_L = 1;
        for (int i = 0; i < l; ++i) {
            h *= MUL;
            h += s[i] - 'a' + 1;
            h %= MOD;
            MUL_POW_L *= MUL;
            MUL_POW_L %= MOD;
        }
        hashTable[h].push_back(0);

        for (int i = 1; i + l - 1 < L; ++i) {
            h *= MUL;
            h %= MOD;
            h -= (1LL * (s[i - 1] - 'a' + 1) * MUL_POW_L) % MOD;
            h += s[i + l - 1] - 'a' + 1; 
            h %= MOD;
            if (h < 0) h += MOD;

            for (auto idx: hashTable[h]) {
                if (s.compare(i, l, s, idx, l) == 0) return true;
            }
            hashTable[h].push_back(i);
        }
        return false;
    };

    int lo = 0;
    int hi = L;

    while (lo + 1 < hi) {
        int mid = lo + hi >> 1;
        if (check(mid)) lo = mid;
        else hi = mid;
    }

    cout << lo << '\n';
}

풀이 2. Suffix array and LCP array

• $*max\_element(all(lcp)) = lcp[i]$ 일 때
  • 반복 문자열 최대길이 $= lcp[i]$
  • 반복 문자열 $= s[sa[i]:sa[i] + lcp[i] - 1]$

코드 2.

#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 L;
    cin >> L;
    string s;
    cin >> s;

    auto buildSA = [&](string& s) {
        int N = s.size();
        vector<int> sa(N), r(2 * N), nr(2 * N);
        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);
            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;
    };

    auto lcp = buildLCP(s);
    cout << *max_element(all(lcp)) << '\n';
}

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

풀이

• 1, 2번 제외한 정점들은 한번씩만 지날 수 있다 -> 용량 1 인 간선으로 각 정점분할
  • u 의 in 정점 : 2u - 1, out 정점: 2u
  • in -> out 단방향 간선 용량 1
  • 1, 2번 정점은 여러번 지날 수 있어야 하므로 (in -> out) 간선 용량은 400(최대 경로 수) 로 지정
• u - v : 양방향 간선을 두개의 단방향 간선으로 (u out -> v in, v out -> u in)

코드

#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;
    Edge* reverse;
    Edge() {
        to = c = f = 0;
        reverse = nullptr; 
    }
    Edge(int to_, int c_) {
        f = 0;
        c = c_;
        to = to_;
        reverse = nullptr;
    }

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

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

    int N, P;
    cin >> N >> P;

    vector<vector<Edge*> > adj(2 * N + 1);

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

    for (int i = 0; i < P; ++i) {
        int u, v;
        cin >> u >> v;
        makeEdge(2 * u, 2 * v - 1, 1);
        makeEdge(2 * v, 2 * u - 1, 1);
    }
    for (int i = 1; i <= N; ++i) {
        int c = 1;
        if (i == 1 || i == 2) c = 400;
        makeEdge(2 * i - 1, 2 * i, c);
    }

    int S = 1 * 2 - 1;
    int T = 2 * 2;
    int answer = 0;

    while (true) {
        vector<Edge*> prev(2 * N + 1, nullptr);
        queue<int> q;
        q.push(S);
        while (q.size()) {
            auto f = q.front();
            q.pop();
            for (auto e: adj[f]) {
                if (prev[e -> to]) continue;
                if (e -> residual() <= 0) continue;
                q.push(e -> to);
                prev[e -> to] = e;
                if (e -> to == T) break;
            }
            if (prev[T]) break;
        }

        if (!prev[T]) break;

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

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

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

풀이

• 기본적인 세그먼트 트리에서 노드의 값을 해당 노드 구간의 배열을 정렬된 상태로 가지는 머지 소트 트리를 이용

코드

• 시간복잡도: $O(NlogN + Mlog^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);

    int N;
    cin >> N;

    vector<vector<long long> > t(2 * N);
    for (int i = 0; i < N; ++i) {
        int num;
        cin >> num;
        t[N + i].push_back(num);
    }

    for (int i = N - 1; i >= 1; --i) {
        t[i].resize(t[i << 1 | 1].size() + t[i << 1].size());
        merge(all(t[i << 1 | 1]), all(t[i << 1]), t[i].begin());
    }

    auto query = [&](int l, int r, int k) {
        int ret = 0;
        for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
            if (l & 1) ret += t[l].end() - upper_bound(all(t[l]), k), ++l;
            if (r & 1) --r, ret += t[r].end() - upper_bound(all(t[r]), k);
        }
        return ret;
    };

    int M;
    cin >> M;
    while (M--) {
        int i, j, k;
        cin >> i >> j >> k;
        cout << query(i - 1, j, k) << '\n';
    }
}