2016.06.30 모임 58

모임 공지

활동 일시: 06월 30일 (목) 19:02
모임 장소: 하이퍼스페이스 (하이퍼커넥트 14층)
내용 : LGE public codejam 2016
샌드위치 형성

장소는 이곳을 참고 하세요

문제 1

root 를 찾은 다음, tree 를 순회하면서 가장 깊은 depth 를 찾으면 된다.
아래 코드에서는 set 을 이용해서 root 를 찾고,
BFS 로 모든 노드를 순회하여 마지막 노드의 depth 를 찾는 방식임

#include <iostream>
#include <cstring>
#include <set>
#include <queue>

using namespace std;

int n;
int in[50001][2];
vector<int> v[50001];
bool visit[50001] = { false, };

void clear() {
    memset(visit, 0, sizeof(visit));
    for (int i = 0; i <= 50000; i++) v[i].clear();
}

void solve() {
    cin >> n; n--;

    set<int> s;
    for (int i = 0; i < n; i++) {
        cin >> in[i][0] >> in[i][1];
        v[in[i][0]].push_back(in[i][1]);
    }

    for (int i = 0; i < n; i++) { s.insert(in[i][0]); }
    for (int i = 0; i < n; i++) { s.erase(in[i][1]); }

    queue<pair<int, int>> Q; // id - depth
    Q.push(make_pair(*s.begin(), 1));

    int r = 1;
    while (!Q.empty()) {
        auto x = Q.front(); Q.pop();
        int id = x.first;
        int depth = x.second;
        if (visit[id]) continue;
        visit[id] = true;

        for (int i : v[id]) {
            Q.push(make_pair(i, depth+1));
        }
        if (Q.empty()) {
            cout << depth << endl;
        }
    }

    clear();
}

int main() {
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

문제 2

문제 보기

문제 3

문제 보기

문자열의 모든 문자열의 수는 길이가 n 일 때 n * (n+1) / 2 이다.
입력이 5만개 인 경우 1 초 이상 걸릴 수 있지만, 어쨌든 해결이 가능하다.

부분 문자열의 길이가 짝수인 경우만 검사하고,
문자열을 2 개씩 늘려가면서 새로 들어오는 문자에 대해 비트에서 xor 로 값을 추가한다. O (n^2) 코드

#include <iostream>
#include <string>

using namespace std;

string str;
int size;

void input() {
    cin >> str;
    size = str.size();
    for (char &c : str) c -= 'a';
}

void solve() {
    long long r = 0;
    for (int from = 0; from < size; from++) {
        int ok = 0;
        for (int to = from+1; to < size; to+=2) {
            ok ^= 1 << str[to-1];
            ok ^= 1 << str[to];
            if (ok == 0) r++;
        }
    }
    cout << r << endl;
}

int main() {
    int t; cin >> t;
    while (t--) { input(); solve(); }
    return 0;
}

O (n) 방식 각 알파벳이 하나씩 들어올 때마다 누적된 xor 값을 저장하고 있다가
동일한 값이 나오는 경우를 모두 카운트 한다.
그러면 그 사이의 부분 문자열은 문제 조건을 만족하는 케이스가 된다.
따라서 동일한 xor 값이 나오는 개수가 x 이면 조건을 만족하는 경우의 수는 x * (x - 1) / 2 가 된다.

#include <iostream>
#include <string>
#include <map>

using namespace std;

string str;
int size;
int xors[50002];

void input() {
    cin >> str;
    size = str.size();
}

void solve() {
    xors[0] = 0;
    for (int i = 1; i <= size; i++) xors[i] = xors[i-1] ^ (1 << (str[i-1]-'a'));

    map<int, int> m;
    for (int i = 0; i <= size; i++) m[xors[i]]++;

    long long r = 0;
    for (const auto &it : m) {
        const int &c = it.second;
        r += c * (c - 1) / 2;
    }
    cout << r << endl;
}

int main() {
    int t; cin >> t;
    while (t--) { input(); solve(); }
    return 0;
}

문제 4

문제 보기

사진

Written on June 15, 2016