KimHwon

Expert라 언레다. 푼 사람 수를 보면 F,G도 풀었어야하는데 좀 아쉽다.

A. Strange Table

n x m 행렬 A에서 A_ij 를 알 때, A_ji를 구하는 문제. 행과 열을 나눈 몫과 나머지를 다시 조합해서 해결.

B. Partial Replacement

주어진 문자열에서 정해진 위치만 x로 바꿀 수 있다. 최소한으로 바꿔서 각 x들 사이 거리가 k 미만이 되도록 하는 문제. 왼쪽 끝과 오른쪽 끝은 문제에서 무조건 바꾸라고 하였으니 그대로 바꾼다. 양 끝의 바뀐 x들 사이를 순회하면서, 길이가 k 이상이 되는 지점 직전을 교체해 나간다. 왼쪽 끝과 오른쪽 끝 사이 길이는 고정이니, 어떻게 바꾸던지 (r-l+1)/k 개 교환됨은 자명하다.

C. Double-ended Strings

문자열의 맨 앞 글자 또는 맨 뒷 글자를 제거할 수 있다. 최소한으로 제거하여 두 문자열이 일치하게 만드는 문제. 두 문자열의 길이가 20으로 매우 짧으므로, 첫 번째 문자열의 모든 substring, 두 번째 문자열의 모든 substring을 비교할 수 있다. 가능한 긴 공통 substring을 찾으면 된다.

D. Epic Transformation

주어진 수열에서 서로 다른 임의의 두 원소를 고르고, 고른 둘을 없앨 수 있다. 만들 수 있는 수열의 최소 크기를 구하는 문제. 해석해보면 www.acmicpc.net/problem/19590 이 문제와 일치한다. 즉, 수열에서 가장 많은 원소가 절반 이하면 무조건 가능하고, 절반 이상이면 절반을 넘는 만큼 남는다.

E. Restoring the Permutation

주어진 수열에서 원소의 값이 바뀌었다는 것은 원본 수열의 해당 위치가 새로운 최댓값이라는 뜻이며, 그렇지 않다는 것은 원본 수열의 해당 위치에 현재 최대값 이하의 원소가 있다는 뜻이다. 수열의 값이 바뀌는 지점에서는 원본 수열의 값이 자명하므로 고정하고, 남은 위치들을 조건에 맞게 적절히 채워 나가면 된다. 최소 수열을 만드려면, 가능한 작은 값을 앞에서부터 채워 나가면 된다. 한편, 최대 수열의 경우는 가능한 큰 값을 앞에서부터 채워 나가야 하는데 현재 최댓값 이하의 원소가 있어야 하므로, set을 사용해 upper_bound-1 값으로 채워 나가면 된다.

이분매칭 : O(V+E)

struct BiMatch {
    bool vst[MAX];
    int match[MAX];     // match[i] <-match-- i
    vector<int> adj[MAX];
    bool dfs(int here) {
        if (vst[here]) return false;
        vst[here] = true;
        for (auto there : adj[here]) {
            if (match[there]<0 || dfs(match[there])) {
                //매칭이 되어있지 않은 정점을 만나거나 이미 매칭된 정점이 다른 정점과 매칭이 가능할 때
                match[there] = here;
                return true;
            }
        }
        return false;
    }
    int bimatch(int cap = 1, int n = MAX-1) { // 1-index
        memset(match, -1, sizeof(match));
        int ret = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < cap; ++j) { // st당 몇 번 매칭?
                memset(vst, 0, sizeof(vst));
                if (dfs(i)) ret++;
            }
        }
        return ret;
    }
} BI;

디닉 : O(EV^2), 0-1 cap에서 min{O(EV^(2/3), O(E^(3/2))}   (대충 다익스트라랑 비슷하다고 하자 (ainta 피셜))

struct Dinic {
    struct edg {int pos, cap, rev;};
    vector<edg> adj[MAX];
    void clear() { for (int i = 0; i < MAX; i++) adj[i].clear(); }
    void make_edge(int s, int e, int x) {
        adj[s].push_back({e, x, (int) adj[e].size()});
        adj[e].push_back({s, 0, (int) adj[s].size() - 1});
    }
    int dis[MAX], pnt[MAX];
    bool bfs(int src, int sink) {
        memset(dis, 0, sizeof(dis));
        memset(pnt, 0, sizeof(pnt));
        queue<int> que;
        que.push(src);
        dis[src] = 1;
        while (!que.empty()) {
            int x = que.front();
            que.pop();
            for (auto &e : adj[x]) {
                if (e.cap > 0 && !dis[e.pos]) {
                    dis[e.pos] = dis[x] + 1;
                    que.push(e.pos);
                }
            }
        }
        return dis[sink] > 0;
    }
    int dfs(int x, int sink, int f) {
        if (x == sink) return f;
        for (; pnt[x] < adj[x].size(); pnt[x]++) {
            edg e = adj[x][pnt[x]];
            if (e.cap > 0 && dis[e.pos] == dis[x] + 1) {
                int w = dfs(e.pos, sink, min(f, e.cap));
                if (w) {
                    adj[x][pnt[x]].cap -= w;
                    adj[e.pos][e.rev].cap += w;
                    return w;
                }
            }
        }
        return 0;
    }
    ll maxflow(int src, int sink) {
        ll ret = 0;
        while (bfs(src, sink)) {
            int r;
            while ((r = dfs(src, sink, 2e9))) ret += r;
        }
        return ret;
    }
} FW;

• 반례찾기
  • 지금 나에게 최적인 거를 뒤에놈들을 위해서 아껴야 최적인 경우가 존재한가? -> 반례
• 2개 요소를 쓰는 그리디
  
  • www.acmicpc.net/problem/1202
  • 작은 가방부터 제일 비싼거를 담기
  • 왜냐면 뒤에서 쓸 가방은 더 유리한 가방이니까... 내가 최선을 골라도 뒤에선 알아서 최선을 고를 수 있다

유클리드 거리

• 교차판정 할 때, ccw 결과값에 sign 씌우는게 좋다 (오버플로)
• rotate matrix : [cos, -sin // sin, cos]  : 꼬마신신고
• 벡터
  • vec = (ed - st), sum(vec) = sum(ed) - sum(ed)
  • AB = OB - OA (종점 - 시점)

맨하탄 거리

• 원이 마름모꼴
  • (x+y, y-x) 로 45도 회전해서 정사각형으로 핸들링
  • [x, y] * [cos(45), -sin(45) // sin(45), cos(45)] 로 rotation matrix를 곱한 것 (에다가 sq2 상수배 곱함)
  • 당연히 역과정은 성립 안함
• 각 점들에서 거리의 합이 최소인 지점
  • (x좌표 중앙값, y좌표 중앙값)
  • 짝수개면 두 점 사이 아무데나

좋은 글이라 공감이 되어 가져왔다.

https://blog.naver.com/pasdfq/222217957003