KimHwon

overflow에 안전한 int 자료형

struct mint {
    int val;
    mint() { val = 0; }
    mint(const ll& v) {
        val = (-MOD <= v && v < MOD) ? v : v % MOD;
        if (val < 0) val += MOD;
    }

    friend ostream& operator<<(ostream& os, const mint& a) { return os << a.val; }
    friend bool operator==(const mint& a, const mint& b) { return a.val == b.val; }
    friend bool operator!=(const mint& a, const mint& b) { return !(a == b); }
    friend bool operator<(const mint& a, const mint& b) { return a.val < b.val; }

    mint operator-() const { return mint(-val); }
    mint& operator+=(const mint& m) { if ((val += m.val) >= MOD) val -= MOD; return *this; }
    mint& operator-=(const mint& m) { if ((val -= m.val) < 0) val += MOD; return *this; }
    mint& operator*=(const mint& m) { val = (ll)val*m.val%MOD; return *this; }
    friend mint ipow(mint a, ll p) {
        mint ans = 1; for (; p; p /= 2, a *= a) if (p&1) ans *= a;
        return ans;
    }
    friend mint inv(const mint& a) { assert(a.val); return ipow(a, MOD - 2); }
    mint& operator/=(const mint& m) { return (*this) *= inv(m); }

    friend mint operator+(mint a, const mint& b) { return a += b; }
    friend mint operator-(mint a, const mint& b) { return a -= b; }
    friend mint operator*(mint a, const mint& b) { return a *= b; }
    friend mint operator/(mint a, const mint& b) { return a /= b; }
    operator int64_t() const { return val; }
};

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define TREE_NODE ll
#define ordered_set tree<TREE_NODE, null_type, less<TREE_NODE>, rb_tree_tag, tree_order_statistics_node_update>
// 중복이 있을 때 less<TREE_NODE> 이면 첫 원소, less_equal<TREE_NODE> 이면 마지막 원소

{
	ordered_set X;
	*X.find_by_order(x);
	X.order_of_key(x);
}

codeforces.com/blog/entry/11080

gcc.gnu.org/onlinedocs/libstdc++/manual/policy_data_structures_design.html

이분매칭 : 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좌표 중앙값)
  • 짝수개면 두 점 사이 아무데나