코딩펭귄

풀이:

https://rkm0959.tistory.com/124 처럼 2는 2개의 3과 연결되어야 하고, 3은 1개의 3 또는 1개의 2와 연결되어야 한다는 걸 플로우로 모델링하면 된다.

처음에는 에드몬드-카프를 썼는데 TLE가 나왔고, bipartite matching을 써서 통과했다.

푼 사람 중에서 속도가 가장 느린 축에 속하는데 플로우로 모델링한 점에 만족하고 넘어간다.

#include "prelude.h"

constexpr int INF = INT_MAX / 2;
constexpr int xs[4] = {-1, 0, 0, 1};
constexpr int ys[4] = {0, -1, 1, 0};

using namespace std;
using pii = pair<int, int>;
using pli = pair<long, int>;
using ll = long long;

class BipartiteMatching {
public:
    BipartiteMatching(int N, int M) : graph(N), A(N, -1), B(M, -1), cnt(-1) {}

    void addEdge(int from, int to) {
        graph[from].push_back(to);
    }

    bool dfs(vector<bool>& visited, int cur) {
        visited[cur] = true;
        for (auto to : graph[cur]) {
            if (B[to] == -1 || (!visited[B[to]] && dfs(visited, B[to]))) {
                A[cur] = to;
                B[to] = cur;
                return true;
            }
        }
        return false;
    }

    int count() {
        if (cnt != -1) {
            return cnt;
        }
        cnt = 0;
        for (int i = 0; i < A.size(); ++i) {
            if (A[i] == -1) {
                vector<bool> visited(A.size(), false);
                if (dfs(visited, i)) {
                    ++cnt;
                }
            }
        }
        return cnt;
    }

    vector<vector<int>> graph;
    vector<int> A;
    vector<int> B;
    int cnt;
};

int board[101][101];

int main() {
    DEFIN2(N, M);
    bool inval = false;
    FOR(i, N) {
        FOR(j, M) {
            IN(board[i][j]);
            if (board[i][j] < 2) {
                inval = true;
            }
        }
    }
    if (inval) {
        PRINTLN("HOMELESS");
        return 0;
    }

    BipartiteMatching bm(N*M*2+2, N*M*2+2);
    auto to = [&](int x, int y) { return (x * M + y) * 2; };

    int totin = 0;
    int totout = 0;
    FOR(i, N) {
        FOR(j, M) {
            if ((i + j) % 2 == 0) {
                if (board[i][j] == 4) {
                    continue;
                }
                totin += (board[i][j] == 3 ? 1 : 2);
                for (int k = 0; k < 4; ++k) {
                    int ni = i + xs[k];
                    int nj = j + ys[k];
                    if (Board(ni, nj, N, M)) {
                        int f = board[i][j];
                        int t = board[ni][nj];
                        if (f == 2 && t == 3) {
                            bm.addEdge(to(i, j), to(ni, nj));
                            bm.addEdge(to(i, j) + 1, to(ni, nj));
                        } else if (f == 3 && t == 2) {
                            bm.addEdge(to(i, j), to(ni, nj));
                            bm.addEdge(to(i, j), to(ni, nj) + 1);
                        } else if (f == 3 && t == 3) {
                            bm.addEdge(to(i, j), to(ni, nj));
                        }
                    }
                }
            } else {
                if (board[i][j] == 4) {
                    continue;
                }
                totout += (board[i][j] == 3 ? 1 : 2);
            }
        }
    }

    auto maxflow = bm.count();
    if (maxflow == max(totin, totout)) {
        PRINTLN("HAPPY");
    } else {
        PRINTLN("HOMELESS");
    }

    return 0;
}

요약

주어진 그래프의 꼭지점을 최대한 많은 그룹으로 나누되, 각 꼭지점은 다른 그룹에 속한 모든 꼭지점과 연결되어 있어야 한다.

참고

[1] https://github.com/koosaga/olympiad/blob/master/POI/poi07_biu.cpp

[2] https://www.cnblogs.com/Delostik/archive/2011/08/09/2132463.html

풀이

주어진 그래프의 complement 그래프를 (있는 edge는 없애고, 없는 edge는 만든다) connected component로 쪼개는 문제다.

BFS를 쓰면 되는데, 문제는 complement 그래프의 edge가 최대 O(N^2)개라는 점이다.

이때 BFS에서 한 꼭지점의 이웃 꼭지점들을 찾는 과정을 간소화시키기 위해 어느 component에 들어갈지 정해진 꼭지점 번호를 없애주는 테크닉을 사용한다.

[1]은 set + upper_bound를 사용했고, 나는 [1]과 [2]를 섞어 list + two pointer를 사용했다.

코드

#include "prelude.h"  // 개인 라이브러리

constexpr int INF = INT_MAX / 2;

using namespace std;

int main() {
    DEFIN2(N, M);
    list<int> li;
    FOR1(i, N) {
        li.push_back(i);
    }
    vector<vector<int>> graph(N + 1);
    LOOP(M) {
        DEFIN2(v, w);
        graph[v].push_back(w);
        graph[w].push_back(v);
    }
    for (auto& e : graph) {
        e.push_back(INF);
        sort(begin(e), end(e));
    }

    auto bfs = [&](int cur) {
        int ret = li.size();
        queue<int> q;
        q.push(cur);
        li.pop_front();

        while (!q.empty()) {
            int e = q.front();
            q.pop();

            auto& nbd = graph[e];
            int l = 0;
            auto it = begin(li);
            while (it != end(li)) {
                if (*it < nbd[l]) {
                    q.push(*it);
                    it = li.erase(it);
                } else if (*it == nbd[l]) {
                    ++it;
                } else {
                    ++l;
                }
            }
        }
        return ret - li.size();
    };

    vector<int> ret;
    while (!li.empty()) {
        ret.push_back(bfs(*begin(li)));
    }
    sort(begin(ret), end(ret));

    COUTLN(ret.size());
    for (auto e : ret) {
        PRINT("{} ", e);
    } LN();

    return 0;
}

#include "bits/stdc++.h"

#define DEFIN(x) int _##x; scanf("%d", &_##x); const int x = _##x
#define DEFIN2(x, y) DEFIN(x); DEFIN(y)
#define DEFIN3(x, y, z) DEFIN(x); DEFIN(y); DEFIN(z)
#define DEFIN4(x, y, z, w) DEFIN(x); DEFIN(y); DEFIN(z); DEFIN(w)
#define DEFIN5(x, y, z, w, v) DEFIN(x); DEFIN(y); DEFIN(z); DEFIN(w); DEFIN(v)
#define DEFCIN(type, x) type _##x; ::std::cin >> _##x ; const type x = ::std::move(_##x)
#define DEFLINE(x) \
    ::std::string _##x; ::std::getline(::std::cin, _##x); const ::std::string x = ::std::move(_##x)
#define IN(x) scanf("%d", &x)
#define CIN(x) ::std::cin >> x
#define DETACH_STDIO ::ios::sync_with_stdio(0); ::std::cin.tie(0); ::std::cout.tie(0)

#define OUT(x) printf("%d ", x)
#define OUTLN(x) printf("%d\n", x)
#define COUT(x) ::std::cout << x << " "
#define COUTLN(x) ::std::cout << x << "\n"
#define LN() printf("\n")
#define PRINT(...) ::std::cout << format(__VA_ARGS__);
#define PRINTLN(...) ::std::cout << format(__VA_ARGS__) << "\n";

#define LOOP(x) for (int _loop_macro = 0; _loop_macro < (x); ++_loop_macro)
#define FOR(i, n) for (int i = 0; i < (n); ++i)
#define FOR1(i, n) for (int i = 1; i <= (n); ++i)

#define MP(x, y) ::std::make_pair(x, y)
#define FAT ::std::forward_as_tuple

///////////////////////////////////////////////////////////////////////////////
// macro-like functions & helpers
///////////////////////////////////////////////////////////////////////////////

template <typename T>
void Maxin(T&& x, T&& y) { x = ::std::max(x, y); }

template <typename T>
void Minin(T&& x, T&& y) { x = ::std::min(x, y); }

template <typename T>
bool Board(T&& x, T&& y, T&& N, T&& M) { return 0 <= x && x < N && 0 <= y && y < M; }

template <typename T>
void Sort(T&& v) { ::std::sort(begin(v), end(v)); }

///////////////////////////////////////////////////////////////////////////////
// container sfinae & helper
///////////////////////////////////////////////////////////////////////////////

template <typename> struct _is_container : std::false_type {};
template <typename T, size_t N> struct _is_container<std::array<T, N>> : std::true_type {};
template <typename T, typename Alloc> struct _is_container<std::vector<T, Alloc>> : std::true_type {};
template <typename T, typename Alloc> struct _is_container<std::list<T, Alloc>> : std::true_type {};
template <typename T, typename Alloc> struct _is_container<std::deque<T, Alloc>> : std::true_type {};
template <typename T, typename Alloc> struct _is_container<std::set<T, Alloc>> : std::true_type {};
template <typename T, typename Alloc> struct _is_container<std::map<T, Alloc>> : std::true_type {};
template <typename T, typename Alloc> struct _is_container<std::multiset<T, Alloc>> : std::true_type {};
template <typename T, typename Alloc> struct _is_container<std::multimap<T, Alloc>> : std::true_type {};
template <typename T, typename Alloc> struct _is_container<std::unordered_set<T, Alloc>> : std::true_type {};
template <typename T, typename Alloc> struct _is_container<std::unordered_map<T, Alloc>> : std::true_type {};

template <typename> struct _is_pair : std::false_type {};
template <typename T1, typename T2> struct _is_pair<std::pair<T1, T2>> : std::true_type {};

template <typename> struct _is_string : std::false_type {};
template <> struct _is_string<std::string> : std::true_type {};
template <typename T> using _is_string_decay = _is_string<std::decay_t<T>>;

template <typename Container>
int len(const Container& c) {
    return c.size();
}

///////////////////////////////////////////////////////////////////////////////
// STL ostream
///////////////////////////////////////////////////////////////////////////////

template <typename T, typename std::enable_if_t<_is_pair<T>::value>* = nullptr>
std::ostream& operator<< (std::ostream& out, const T& v) {
    out << "(" << v.first << ", " << v.second << ")";
    return out;
}

template <typename T, typename std::enable_if_t<_is_container<T>::value>* = nullptr>
std::ostream& operator<< (std::ostream& out, const T& v) {
    if (v.empty()) {
        out << "[]";
    } else {
        out << "[";
        for (const auto& e : v) {
            out << e << ", ";
        }
        out << "\b\b]";
    }
    return out;
}

///////////////////////////////////////////////////////////////////////////////
// string formatter
///////////////////////////////////////////////////////////////////////////////

std::string format() {
    return {};
}

std::string format(const char* fmt) {
    return {fmt};
}

template <typename T>
std::string format(const char* fmt, T&& arg) {
    bool substituted = false;
    std::string res;
    while (*fmt != 0) {
        if (!substituted && *fmt == '{' && *(fmt + 1) == '}') {
            std::stringstream ss;
            ss << arg;
            res.append(ss.str());
            substituted = true;
            fmt += 2;
        } else {
            res.push_back(*fmt);
            ++fmt;
        }
    }
    return res;
}

template <typename T, typename... Args>
std::string format(const char* fmt, T&& arg, Args&&... args) {
    std::string res;
    while (*fmt != 0) {
        if (*fmt == '{' && *(fmt + 1) == '}') {
            std::stringstream ss;
            ss << arg;
            res.append(ss.str());
            res.append(format(fmt + 2, std::forward<Args>(args)...));
            break;

        } else {
            res.push_back(*fmt);
            ++fmt;
        }
    }
    return res;
}

///////////////////////////////////////////////////////////////////////////////
// improved pair
///////////////////////////////////////////////////////////////////////////////

template <typename T1, typename T2>
std::pair<T1, T2>& operator+=(std::pair<T1, T2>& a, const std::pair<T1, T2>& b) {
	a.first += b.first, a.second += b.second;
	return a;
}

template <typename T1, typename T2>
std::pair<T1, T2>& operator-=(std::pair<T1, T2>& a, const std::pair<T1, T2>& b) {
	a.first -= b.first, a.second -= b.second;
	return a;
}

namespace std {

template <typename T1, typename T2>
struct hash<std::pair<T1, T2>> {
public:
    size_t operator()(const std::pair<T1, T2>& p) const
    {
        auto hash1 = std::hash<T1>{}(p.first);
        auto hash2 = std::hash<T2>{}(p.second);
        return hash1 ^ (hash2 << 1);
    }
};

}   // namespace std

///////////////////////////////////////////////////////////////////////////////
// end of file
///////////////////////////////////////////////////////////////////////////////

한 일을 순서대로 적어본다.

• MySQL 설치
  • 검색하면 다 나옴
• 무료 DDNS 설치
  • https://jimnong.tistory.com/788
  • 근데 사용하는 kt 기가 UTP가 DHCP 방식이 아니라서 연결된 모든 PC에 공인 IP를 준다. 그래서 DDNS가 필요 x (뭔 소리지 ㅎㅎ)
  • 일단 IP로 접속하기로 했다.
• MediaWiki 설치
  • https://www.mediawiki.org/wiki/Manual:Running_MediaWiki_on_Debian_or_Ubuntu/ko 내용을 그대로 따라하면 된다.
  • IP가 바뀌거나 도메인 이름을 사용하고 싶으면 LocalSettings.php의 $wgServer를 바꾸면 된다.

끝. 생각보다 금방 끝난다.

Law of Large Numbers

• X̄ = \sum{i} X_i 일 때, P(|X̄ - μ| < ε) = 1 as n → ∞.

Central Limit Theorem

• X̄ = \sum{i} X_i 이고 n >> 1일 때 (heuristic하게는 n > 30), X̄ ~ N(μ, σ^2/n).
• 모집단의 σ를 알 때, n이 얼마여야 x̄ = μ ± α w/ 95% certainty 인지 계산하는 데에 사용된다.

Sample Mean & Variance

• X̄ = \sum{i} X_i / n
• S^2 = \sum{i} (X_i - X̄)^2 / (n-1)
  • 왜 n-1?
    • S^2는 σ^2의 정확한 estimator가 아니다. X̄의 정의상 항상 S^2 <= σ^2 이기 때문.
    • 다행히도 둘 사이에는 일정 관계가 성립한다.
    • 먼저 Σ(X_i - μ)^2 = Σ(X_i - X̄)^2 + Σ(X̄ - μ)^2 이다. (좌변 전개 후 가운데 항 상쇄)
    • 양변에 E를 씌우고 정리하면 E[(n-1)S^2] = (n-1)σ^2. 따라서 E[S^2] = σ^2.

Standard Error

• Var(X̄) = σ^2 / n
• Std(X̄) = S / sqrt(n)
• 이건 X̄의 분포에 관한 통계수치. 즉, sampling을 할 때 X̄가 μ랑 얼마나 떨어져 있는지를 나타냄.