hckim

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

풀이

$dp[i][diff]:$ $i$ 까지 고려해서 쌓은 경우에서 차이가 $diff$ 일 때 더 높은쪽의 높이의 최댓값

※ $i, diff$ 이 불가능한 경우: $dp[i][diff] = -1$

$dp[i - 1][j] \neq -1$ 일 때

1. $i$ 블록 안 쌓는 경우
   • $dp[i][j] = max(dp[i][j], dp[i - 1][j])$
2. $i$ 블록 쌓는 경우
   1. 높은 쪽에 쌓는 경우
      • $dp[i][j + a[i]] = max(dp[i][j + a[i]], dp[i - 1][j] + a[i])$
   2. 낮은 쪽에 쌓는 경우
      1. $a[i] < j$
         • $dp[i][j - a[i]] = max(dp[i][j - a[i]], dp[i - 1][j])$
      2. $a[i] \geq j$
         • $dp[i][a[i] - j] = max(dp[i][a[i] - j], dp[i - 1][j] + a[i] - j)$

코드

#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);
    vector<vector<int> > dp(N, vector<int> (500001, -1));
    for (int i = 0; i < N; ++i) {
        cin >> a[i];
    }
    
    dp[0][0] = 0;
    dp[0][a[0]] = a[0];
    for (int i = 1; i < N; ++i) {
        for (int j = 0; j <= 500000; ++j) {
            if (dp[i - 1][j] == -1) continue;
            dp[i][j] = max(dp[i][j], dp[i - 1][j]);
            if (j + a[i] <= 500000) dp[i][j + a[i]] = max(dp[i][j + a[i]], dp[i - 1][j] + a[i]);
            if (a[i] < j) {
                dp[i][j - a[i]] = max(dp[i][j - a[i]], dp[i - 1][j]);
            } else {
                dp[i][a[i] - j] = max(dp[i][a[i] - j], dp[i - 1][j] + a[i] - j);
            }
        }
    }
    if (dp[N - 1][0] > 0) {
        cout << dp[N - 1][0] << '\n';
    } else {
        cout << "-1\n";
    }
}

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

풀이1. Maximum flow(에드몬드 카프)

최대 K 명까지 일을 두개 할 수 있다는 것을 Source 에서 용량 K 로 이어진 추가 노드를 구성함으로써 구현

코드1.

• 단방향 플로우에서 역방향 간선의 capacity = 0 으로 해야함에 주의
• 시간복잡도: $min(O((V + E)f), O(VE^2)) \to O((V + E)(V + K))$ 

#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 = 0;
        c = 0;
        f = 0;
        reverse = nullptr;
    }
    int residual() {
        return c - f;
    }
};

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

    int N, M, K;
    cin >> N >> M >> K;
    vector<vector<Edge*> > adj(N + M + 3);
    auto makeEdge = [&](int n1, int n2, int cc) {
        auto e1 = new Edge();
        auto e2 = new Edge();

        e1 -> to = n2;
        e1 -> reverse = e2;
        e1 -> c = cc;
        e2 -> to = n1;
        e2 -> reverse = e1;

        adj[n1].push_back(e1);
        adj[n2].push_back(e2);
    };

    int S = 0, T = N + M + 1, X = N + M + 2;

    makeEdge(S, X, K);
    for (int i = 1; i <= N; ++i) {
        int num;
        cin >> num;
        makeEdge(S, i, 1);
        makeEdge(X, i, 1);
        while (num--) {
            int w;
            cin >> w;
            makeEdge(i, N + w, 1);
        }
    }
    for (int i = 1; i <= M; ++i) {
        makeEdge(N + i, T, 1);
    }

    while (true) {
        vector<Edge*> prev(N + M + 3, nullptr);
        queue<int> q;
        q.push(S);
        while (!q.empty()) {
            auto f = q.front();
            q.pop();

            for (auto e: adj[f]) {
                if (e -> residual() <= 0) continue;
                if (prev[e -> to]) 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 (auto cur = T; cur != S; cur = prev[cur] -> reverse -> to) {
            flow = min(flow, prev[cur] -> residual());
        }
        for (auto cur = T; cur != S; cur = prev[cur] -> reverse -> to) {
            prev[cur] -> f += flow;
            prev[cur] -> reverse -> f -= flow;
        }
    }

    int answer = 0;
    for (auto e: adj[T]) {
        answer += e -> reverse -> f;
    }
    cout << answer << '\n';
}

풀이2. Bipartite matching

직원당 두개의 노드를 만들고 그룹 두개로 나눠서 한그룹에서 이분매칭 후 두번째 그룹에서 K번 이하 이분매칭

코드2. 

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

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

    vector<int> A(2 * N + 1, 0), B(M + 1, 0);
    vector<vector<int> > adj(2 * N + 1);

    for (int i = 1; i <= N; ++i) {
        int num;
        cin >> num;
        while (num--) {
            int m;
            cin >> m;
            adj[2 * i - 1].push_back(m);
            adj[2 * i].push_back(m);
        }
    }

    vector<int> visited(2 * N + 1, false);
    function<bool(int)> f = [&](int a) {
        visited[a] = true;
        for (auto b: adj[a]) {
            if (!B[b] || (!visited[B[b]] && f(B[b]))) {
                A[a] = b;
                B[b] = a;
                return true;
            }            
        }
        return false;
    };

    int match = 0;
    for (int i = 1; i <= 2 * N; i += 2) {
        if (!A[i]) {
            fill(all(visited), false);
            if (f(i)) ++match;
        }
    }
    int matched2 = 0;
    for (int i = 2; i <= 2 * N && matched2 < K; i += 2) {
        if (!A[i]) {
            fill(all(visited), false);
            if (f(i)) ++matched2;
        }
    }

    cout << match + matched2 << '\n';
}

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

풀이

1. 입력받은 팀명의 앞에서부터 color 와 매치되는 인덱스들 체크
2. 팀명의 뒤에서부터 name 과 매치되는 인덱스들 체크
3. color 매치되는 인덱스 + 1 = name 과 매치되는 인덱스 이면 color + name 팀명

코드

• MLE 피하기 위해 map 사용한 Trie 구조체 사용

#include <bits/stdc++.h>

using namespace std;

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

struct Trie {
    bool isTerminal;
    map<char, Trie*> children;
    Trie() {
        isTerminal = false;
    }

    ~Trie() {
        for (auto& e: children) {
            delete e.second;
        }
        children.clear();
    }
};

void insert(Trie* root, string key) {
    Trie* tmp = root;
    for (auto e: key) {
        if (tmp -> children.find(e) == tmp -> children.end()) {
            tmp -> children[e] = new Trie();
        }
        tmp = tmp -> children[e];
    }
    tmp -> isTerminal = true;
}
void insert_rev(Trie* root, string key) {
    Trie* tmp = root;
    for (int i = key.size() - 1; i >= 0; --i) {
        if (tmp -> children.find(key[i]) == tmp -> children.end()) {
            tmp -> children[key[i]] = new Trie();
        }
        tmp = tmp -> children[key[i]];
    }
    tmp -> isTerminal = true;
}

void check(Trie* root, vector<int>& checked, string& key) {
    auto cur = root;
    for (int i = 0; i < key.size(); ++i) {
        if (cur -> children.find(key[i]) == cur -> children.end()) return;
        cur = cur -> children[key[i]];        
        if (cur -> isTerminal) checked[i] = true;
    }
}
void check_rev(Trie* root, vector<int>& checked, string& key) {
    auto cur = root;
    for (int i = key.size() - 1; i >= 0; --i) {
        if (cur -> children.find(key[i]) == cur -> children.end()) return;
        cur = cur -> children[key[i]];
        if (cur -> isTerminal) checked[i] = true;
    }
}

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

    int N, C, Q;
    cin >> C >> N;

    Trie* color = new Trie();
    Trie* name = new Trie();
    for (int i = 0; i < C; ++i) {
        string s;
        cin >> s;
        insert(color, s);
    }
    for (int i = 0; i < N; ++i) {
        string s;
        cin >> s;
        insert_rev(name, s);
    }

    cin >> Q;
    while (Q--) {
        string ss;
        cin >> ss;
        vector<int> checked1(ss.size(), 0);
        vector<int> checked2(ss.size(), 0);
        check(color, checked1, ss);
        check_rev(name, checked2, ss);
        bool yes = false;
        for (int i = 0; i < ss.size() - 1; ++i) {
            if (checked1[i] == 1 && checked2[i + 1] == 1) {
                yes = true;
                break;
            }
        }
        if (yes) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }
}

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

- 다각형이 통과하는데 필요한 최소 슈트 너비는 그 다각형의 점들을 포함하는 볼록 다각형, 즉 convex hull 이 통과하는데 필요한 최소 슈트 너비와 같다

- 볼록 다각형의 한 변이 슈트 한변에 접해서 통과한다고 할 때 필요한 최소 슈트 너비는 그 변에서 가장 멀리 떨어진 점과의 거리와 같다.

1. convex hull 이루는 점 집합 구하기

2. 각 변에 대해서 가장 멀리 떨어진 점까지의 거리들 중 최솟값이 답

  2-1. 변 p1p2 와 점 p3 거리는 외적(p1p2, p2p3)크기 / p1p2길이

  2-2. 올림할 때 소수점 셋째 자리이하가 0 보다 큰지 비교해서 올림하면 틀릴 수 있음, 1e-12 와 비교

#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 caseNum = 1;
    int N;

    auto cp = [&](pair<long double, long double> p1, pair<long double, long double> p2, pair<long double, long double> p3) {
        auto ret = (p2.first - p1.first) * (p3.second - p2.second) - (p2.second - p1.second) * (p3.first - p2.first);
        return ret;
    };
    
    pair<long double, long double> base;
    auto cmp = [&](pair<long double, long double> p1, pair<long double, long double> p2) {
        auto cp_ = cp(base, p1, p2);
        if (cp_ != 0) {
            return cp_ > 0;
        }
        return (base.first - p1.first) * (base.first - p1.first) + (base.second - p1.second) * (base.second - p1.second) < (base.first - p2.first) * (base.first - p2.first) + (base.second - p2.second) * (base.second - p2.second);
    };

    while (cin >> N && N) {

        vector<pair<long double, long double> > p(N);
        for (int i = 0; i < N; ++i) {
            cin >> p[i].first >> p[i].second;
        }

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

        base = p[0];

        sort(all(p), cmp);

        stack<pair<long double, long double> > st;
        st.push(p[0]);
        st.push(p[1]);
        for (int i = 2; i < N; ++i) {
            auto p2 = st.top(); st.pop();
            auto p1 = st.top();
            auto p3 = p[i];

            auto cp_ = cp(p1, p2, p3);
            while (cp_ < 0) {
                p2 = p1;
                st.pop(); p1 = st.top();
                cp_ = cp(p1, p2, p3);
            }

            if (cp_ > 0) {
                st.push(p2);
                st.push(p3);
            } else {
                //  cp_ = 0
                st.push(p3);
            }
        }

        vector<pair<long double, long double> > convexHull(st.size());
        while (st.size()) {
            convexHull[st.size() - 1] = st.top();
            st.pop();
        }

        long double answer = 1e18;
        
        for (int i = 0; i < convexHull.size(); ++i) {
            auto p1 = convexHull[i];
            auto p2 = convexHull[(i + 1) % (convexHull.size())];
            long double maxDist = 0;
            long double p1p2 = sqrtl((p1.first - p2.first) * (p1.first - p2.first) + (p1.second - p2.second) * (p1.second - p2.second));
            for (int j = 0; j < convexHull.size(); ++j) {
                auto p3 = convexHull[j];
                auto cp_ = abs(cp(p1, p2, p3));
                maxDist = max(maxDist, cp_ / p1p2);
            }
            answer = min(answer, maxDist);
        }

        answer *= 100;
        if (answer - (long long)answer > 1e-12) {
            answer += 1;
            answer = (long long)answer;
        }
        answer /= 100;
        cout.precision(2);
        cout << fixed;
        cout << "Case " << caseNum++ << ": " << answer << '\n';
    }
}