[카테고리:] Problem Solving

GCJ 2016 R1B

2016년 5월 1일 글쓴이 Qwaz·0개의 댓글

시작할 때는 컨디션이 좋아서 빠르게 A, C를 풀었지만 B에서 삽질을 많이 하면서 4 WA(…)를 받았다. 심지어 system test에서 B Large가 나갔다. 436위로 마무리. R2 액땜했다고 생각하자.

A

ZERO, ONE, TWO, THREE, …, NINE으로 이루어진 아나그램을 주고, 각 숫자를 몇 번씩 사용했는지 출력하는 문제다. 0, 2, 4, 6, 8, 1, 5, 3, 7, 9 순서로 그리디하게 빼 주면 유일해를 쉽게 찾을 수 있다. 구조화를 잘못해서 코드를 몇 번 지우고 다시 짜서 문제 난이도에 비해 코딩이 오래 걸렸다.

A Code

#include <cstdio>
#include <cstring>
#include <algorithm>

const int MAX = 2999;
using namespace std;

int countAlphabet[99], countDigit[10][99], usedDigit[10];

char * digitName[] = {
    "ZERO", "ONE", "TWO", "THREE", "FOUR", "FIVE", "SIX", "SEVEN", "EIGHT", "NINE"
};

void countNumber(char * str) {
    for (int i = 0; str[i]; i++)
        countAlphabet[str[i] - 'A']++;
}

void greedyUse(int digit) {
    int maxUse = MAX;

    for (char abc = 'A'; abc <= 'Z'; abc++) {
        if (countDigit[digit][abc - 'A'])
            maxUse = min(maxUse, countAlphabet[abc - 'A'] / countDigit[digit][abc - 'A']);
    }

    usedDigit[digit] += maxUse;

    for (char abc = 'A'; abc <= 'Z'; abc++) {
        countAlphabet[abc - 'A'] -= maxUse * countDigit[digit][abc - 'A'];
    }
}

int main() {
    freopen("output.txt", "w", stdout);

    for (int i = 0; i < 10; i++) {
        for (int j = 0; digitName[i][j]; j++) {
            countDigit[i][digitName[i][j] - 'A']++;
        }
    }

    int numCase, nowCase;
    scanf("%d", &numCase);
    for (nowCase = 1; nowCase <= numCase; nowCase++) {
        memset(countAlphabet, 0, sizeof(countAlphabet));
        memset(usedDigit, 0, sizeof(usedDigit));

        char str[MAX];
        scanf("%s", str);

        countNumber(str);

        greedyUse(0); //Zero
        greedyUse(2); //tWo
        greedyUse(4); //foUr
        greedyUse(6); //siX
        greedyUse(8); //eiGht
        //absoulute greedy

        greedyUse(1); //One
        greedyUse(5); //Five
        greedyUse(3); //THRee
        greedyUse(7); //SeVen
        greedyUse(9); //NINE
        //relative greedy

        printf("Case #%d: ", nowCase);
        for (int digit = 0; digit < 10; digit++) {
            for (int i = 0; i < usedDigit[digit]; i++)
                printf("%d", digit);
        }
        puts("");
    }

    return 0;
}

26:58 AC

C

B가 내가 약한 문제 유형이라 C부터 풀기로 했다. string을 정점으로 변환한 뒤 이분 그래프에서 minimum vertex cover를 찾으면 된다. 이분매칭을 너무 오랜만에 짜서 검색하느라 오래 걸렸지만 문제 자체는 알면 쉽다.

C Code

#include <cstdio>
#include <iostream>
#include <map>
#include <string>
#include <vector>

const int MAX = 1020;
using namespace std;

int fCount, sCount;
map < string, int > fWord, sWord;

int n, crossS[MAX];
bool visitS[MAX];
vector < int > edges[MAX];

bool dfs(int f) {
    for (int s : edges[f]) {
        if (!visitS[s]) {
            visitS[s] = 1;

            if (crossS[s] < 0 || dfs(crossS[s])) {
                crossS[s] = f;
                return true;
            }
        }
    }

    return false;
}

int bipartiteMatch() {
    int ret = 0;

    memset(crossS, -1, sizeof(crossS));

    for (int f = 0; f < fCount; f++) {
        memset(visitS, 0, sizeof(visitS));

        if (dfs(f)) {
            ret++;
        }
    }

    return ret;
}

int main() {
    freopen("output.txt", "w", stdout);

    ios::sync_with_stdio(true);

    int numCase, nowCase;
    scanf("%d", &numCase);
    for (nowCase = 1; nowCase <= numCase; nowCase++) {
        fWord.clear();
        sWord.clear();
        for (int i = 0; i < fCount; i++)
            edges[i].clear();
        fCount = sCount = 0;

        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            string fStr, sStr;
            cin >> fStr >> sStr;

            int fIndex, sIndex;
            if (fWord.find(fStr) == fWord.end()) {
                fWord[fStr] = fCount;
                fIndex = fCount;
                fCount++;
            } else {
                fIndex = fWord[fStr];
            }
            if (sWord.find(sStr) == sWord.end()) {
                sWord[sStr] = sCount;
                sIndex = sCount;
                sCount++;
            } else {
                sIndex = sWord[sStr];
            }

            edges[fIndex].push_back(sIndex);
        }

        int numMatch = bipartiteMatch();

        printf("Case #%d: %d\n", nowCase, n - (fCount + sCount - numMatch));
    }

    return 0;
}

58:57 AC

B

내가 잘 풀지 못하는 유형이라 생각하고 넘기고 풀었는데, 정말로 잘 못 푸는 유형이라 4번의 오답 끝에 small을 맞출 수 있었다. Large는 푼 줄 알았는데 system test에서 틀렸다.

문자열 두 개 모두 ?가 아니면서 서로 다른 위치 중 가장 앞에 있는 위치를 찾는다. 존재하지 않는 경우는 두 점수를 동일하게 만들 수 있다. 존재하는 경우는 그 위치를 기준으로 뒤쪽은 모두 0 또는 9로 채우고, 앞쪽을 최대한 비슷하게 만들면 된다.

PL 수업을 수강하면서 코드 설계력이 좋아지고 버그를 내는 빈도가 줄었다고 생각하고 있었는데, B 코드는 확실히 설계는 잘 한 것 같은데 사소한 버그를 너무 많이 내서 슬펐다. 값 비교할 때 절댓값을 취하지 않는다든가, break을 잊었다든가 하는 실수를 4번이나 저질렀다고 한다…

아래 코드는 small만 통과한다. ??8? ?02?는 0989 1020가 나와야 하는데 0089 0029가 나온다. ‘앞 부분을 최대한 비슷하게’ 하는 방법이 틀렸음.

B Code

#include <cstdio>
#include <cstring>
#include <string>

const int MAX = 20;
using namespace std;
typedef long long ll;

void makeSame(char *a, char *b, int n) {
    for (int i = 0; i < n; i++) {
        if (a[i] == '?') {
            if (b[i] == '?') {
                a[i] = b[i] = '0';
            } else {
                a[i] = b[i];
            }
        } else {
            if (b[i] == '?') {
                b[i] = a[i];
            }
        }
    }
}

void fill(char c, char *s, char *end) {
    while (s != end) {
        if (*s == '?') *s = c;
        s++;
    }
}

bool inc(char *s, char *tpl, int n) {
    for (int i = n-1; i >= 0; i--) {
        if (tpl[i] == '?') {
            if (s[i] == '9') {
                s[i] = '0';
            } else {
                s[i]++;
                return true;
            }
        }
    }
    return false;
}

bool dec(char *s, char *tpl, int n) {
    for (int i = n-1; i >= 0; i--) {
        if (tpl[i] == '?') {
            if (s[i] == '0') {
                s[i] = '9';
            } else {
                s[i]--;
                return true;
            }
        }
    }
    return false;
}

int main() {
    freopen("output.txt", "w", stdout);

    int numCase, nowCase;
    scanf("%d", &numCase);
    for (nowCase = 1; nowCase <= numCase; nowCase++) {
        int n;
        char f[MAX], s[MAX];
        char rf[MAX], rs[MAX];

        scanf("%s%s", f, s);

        n = strlen(f);

        int diff = -1;
        for (int i = 0; i < n; i++) {
            if (f[i] != '?' && s[i] != '?' && f[i] != s[i]) {
                diff = i;
                break;
            }
        }

        if (diff == -1) {
            //can be same
            makeSame(f, s, n);

            strcpy(rf, f);
            strcpy(rs, s);
        } else {
            ll fsDiff = 1e18;

            auto update = [&](char *fCand, char *sCand) {
                ll rfCand = atoll(fCand);
                ll rsCand = atoll(sCand);
                ll candDiff = abs(rsCand - rfCand);

                if (fsDiff > candDiff ||
                    (fsDiff == candDiff &&
                    (atoll(rf) > rfCand || (atoll(rf) == rfCand && atoll(rs) > rsCand)))) {
                    strcpy(rf, fCand);
                    strcpy(rs, sCand);
                    fsDiff = candDiff;
                }
            };

            char tf[MAX], ts[MAX];

            if (f[diff] < s[diff]) {
                //f < s
                strcpy(tf, f);
                strcpy(ts, s);
                makeSame(tf, ts, diff);
                fill('9', tf+diff, tf+n);
                fill('0', ts+diff, ts+n);
                update(tf, ts);

                //f > s
                strcpy(tf, f);
                strcpy(ts, s);
                makeSame(tf, ts, diff);
                if (inc(tf, f, diff)) {
                    fill('0', tf+diff, tf+n);
                    fill('9', ts+diff, ts+n);
                    update(tf, ts);
                }

                //f > s
                strcpy(tf, f);
                strcpy(ts, s);
                makeSame(tf, ts, diff);
                if (dec(ts, s, diff)) {
                    fill('0', tf+diff, tf+n);
                    fill('9', ts+diff, ts+n);
                    update(tf, ts);
                }
            } else {
                //f > s
                strcpy(tf, f);
                strcpy(ts, s);
                makeSame(tf, ts, diff);
                fill('0', tf+diff, tf+n);
                fill('9', ts+diff, ts+n);
                update(tf, ts);

                //f < s
                strcpy(tf, f);
                strcpy(ts, s);
                makeSame(tf, ts, diff);
                if (inc(ts, s, diff)) {
                    fill('9', tf+diff, tf+n);
                    fill('0', ts+diff, ts+n);
                    update(tf, ts);
                }

                //f < s
                strcpy(tf, f);
                strcpy(ts, s);
                makeSame(tf, ts, diff);
                if (dec(tf, f, diff)) {
                    fill('9', tf+diff, tf+n);
                    fill('0', ts+diff, ts+n);
                    update(tf, ts);
                }
            }
        }

        //printf("%s %s\n", f, s);
        printf("Case #%d: %s %s\n", nowCase, rf, rs);
    }

    return 0;
}

2:03:41 small AC

SCC

SCC는 Strongly Connected Component의 약자로, 방향 그래프의 SCC는 다음 조건을 만족하는 서브그래프들입니다.

같은 SCC 내에 속하는 임의의 서로 다른 두 정점은 서로 도달 가능합니다.
어떤 정점이나 간선도 1의 조건을 만족하면서 이 SCC에 추가될 수 없습니다.(최대부분집합)

SCC Example

위의 예시에서는 (a, b, e) (f, g) (c, d, h)가 하나의 SCC가 됩니다. 임의의 방향 그래프에서 SCC를 구했을 때 모든 정점은 단 하나의 SCC에만 속하게 되며, SCC 자체를 하나의 정점으로 보았을 때 전체 그래프를 사이클이 없는 방향 그래프(DAG) 형태로 변환할 수 있습니다.

임의의 방향 그래프가 주어질 때 SCC를 찾는 알고리즘으로 코사라주의 알고리즘과 타잔의 알고리즘이 유명하고, 둘 모두 $O(V+E)$ 에 동작함이 증명되어 있습니다. 아래는 각 알고리즘의 설명과 구현 코드입니다. 입출력은 BOJ의 Strongly Connected Component 문제를 기준으로 작성했습니다.

코사라주의 알고리즘(Kosaraju’s Algorithm)

코사라주의 알고리즘은 다음과 같이 동작합니다.

방향 그래프 G, 빈 스택 S, G의 간선 방향을 뒤집은 역방향 그래프 G’를 준비합니다.
G에서 아직 방문되지 않은 정점들에 대해 DFS를 시행하고, 각 정점의 탐색이 끝나는 순서대로 S에 넣습니다.(위상정렬) 스택에 모든 정점이 들어갈 때까지 반복합니다.
S가 빌 때까지 다음을 반복합니다.
S의 가장 위쪽에 있는 정점 v를 뽑습니다. v가 G’에서 이미 방문된 정점이라면 정점을 다시 뽑습니다.
G’에서 v에서 DFS를 시행해 이번 시도에 처음 방문한 정점들을 v와 같은 SCC로 묶습니다.

코사라주의 알고리즘은 정방향 그래프와 역방향 그래프가 동일한 SCC를 가진다는 점을 이용합니다. 정방향 DFS를 통해 정점들을 위상정렬하고, 역방향 DFS에서 SCC를 찾는다고 생각할 수 있습니다.

Kosaraju's Algorithm Code

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;
const int MAX = 10020;

int V, E;
vector < int > front[MAX], rev[MAX];

void input() {
    scanf("%d%d", &V, &E);

    // 그래프 초기화
    for (int i = 0; i < E; i++) {
        int f, s;
        scanf("%d%d", &f, &s);
        front[f].push_back(s);
        rev[s].push_back(f);
    }
}

int visited[MAX], stack[MAX], top;
vector < vector < int > > sccGroup;

void front_dfs(int node) {
    visited[node] = 1;
    for (auto next : front[node]) {
        if (!visited[next]) {
            front_dfs(next);
        }
    }
    // DFS를 빠져 나올 때 스택에 쌓음
    stack[top++] = node;
}

void rev_dfs(int node) {
    visited[node] = 1;
    // 마지막 그룹에 정점 추가
    sccGroup[sccGroup.size()-1].push_back(node);
    for (auto next : rev[node]) {
        if (!visited[next]) {
            rev_dfs(next);
        }
    }
}

void solve() {
    // 위상 정렬
    for (int v = 1; v <= V; v++) {
        if (!visited[v]) {
            front_dfs(v);
        }
    }

    // 그룹 묶기
    memset(visited, 0, sizeof(visited));
    while (top) {
        int node = stack[top-1];
        top--;
        if (!visited[node]) {
            // 빈 그룹 추가
            sccGroup.push_back(vector < int >());
            rev_dfs(node);
        }
    }

    // 문제 요구 조건대로 정렬
    for (auto &vec : sccGroup)
        sort(vec.begin(), vec.end());
    sort(sccGroup.begin(), sccGroup.end());

    // 출력
    printf("%dn", sccGroup.size());
    for (auto &vec : sccGroup) {
        for (auto elem : vec) {
            printf("%d ", elem);
        }
        puts("-1");
    }
}

int main() {
    input();

    solve();

    return 0;
}

코사라주의 알고리즘은 기억하기 쉬운 편이지만, 동일한 그래프를 두 가지 형태로 저장해야 하고 DFS를 두 번 시행하기 때문에 일반적으로 타잔의 알고리즘보다 약간 낮은 성능을 보여줍니다. 하지만 시간복잡도에는 차이가 없기 때문에 알고리즘 문제풀이에서는 문제 없이 사용할 수 있습니다.

타잔의 알고리즘(Tarjan’s Algorithm)

타잔의 알고리즘은 다음과 같이 동작합니다.

방향 그래프 G, 빈 스택 S, 각 정점의 방문 순서를 저장할 배열 index, 각 정점에서 도달 가능한 정점을 저장할 배열 lowlink를 준비합니다.
아직 방문되지 않은 정점 v에서 DFS를 시작합니다.
v를 S에 쌓고, index[v]에 방문 순서를 저장합니다.
lowlink[v] = index[v]
v의 이웃 정점 u에 대해:
u를 아직 방문하지 않았다면 u에 대해 DFS를 시행하고, lowlink[u]가 lowlink[v]보다 작은 경우 lowlink[v]를 갱신합니다.
u가 스택에 들어있고, index[u]가 lowlink[v]보다 작은 경우 lowlink[v]를 갱신합니다.
lowlink[v]와 index[v]가 동일하다면, v를 포함해 v 이후로 S에 쌓인 정점들을 새로운 SCC 컴포넌트로 묶습니다.

타잔의 알고리즘은 각각의 SCC가 DFS 트리에서 서브트리를 이룬다는 점을 이용한 알고리즘입니다. 임의의 정점 v에 대한 탐색이 종료된 시점에서, v 이전에 스택에 쌓인 정점에 대한 경로가 존재하는 경우에만 v가 스택에 남아 있을 수 있습니다. 그렇지 않은 경우 v는 v 이전에 스택에 쌓인 정점들과 같은 SCC에 속할 수 없기 때문에 v가 SCC의 경계가 되어 현재 스택에 쌓인 정점들과 SCC를 구성합니다.

Tarjan's Algorithm Code

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;
const int MAX = 10020;

int V, E;
vector < int > from[MAX];

void input() {
    scanf("%d%d", &V, &E);

    // 그래프 초기화
    for (int i = 0; i < E; i++) {
        int f, s;
        scanf("%d%d", &f, &s);
        from[f].push_back(s);
    }
}

int stack[MAX], top, id[MAX], currentId, groupId[MAX];
vector < vector < int > > sccGroup;

int traverse(int node) {
    id[node] = ++currentId;
    stack[top++] = node;

    // lowlink를 return 값으로 사용
    int lowlink = id[node];
    for (auto next : from[node]) {
        if (id[next] == 0) {
            // 방문하지 않은 정점
            lowlink = min(lowlink, traverse(next));
        } else if (groupId[next] == 0) {
            // 이미 스택에 들어 있는 정점
            lowlink = min(lowlink, id[next]);
        }
    }

    if (lowlink == id[node]) {
        // 그룹 추가
        sccGroup.push_back(vector < int >());
        while (1) {
            int now = stack[top-1];
            top--;

            // node 하위의 서브트리를 SCC 그룹으로 묶기
            groupId[now] = sccGroup.size();
            sccGroup[groupId[now]-1].push_back(now);

            if (now == node) break;
        }
    }

    return lowlink;
}

void solve() {
    for (int v = 1; v <= V; v++) {
        if (id[v] == 0) {
            traverse(v);
        }
    }

    // 문제 요구 조건대로 정렬
    for (auto &vec : sccGroup)
        sort(vec.begin(), vec.end());
    sort(sccGroup.begin(), sccGroup.end());

    // 출력
    printf("%dn", sccGroup.size());
    for (auto &vec : sccGroup) {
        for (auto elem : vec) {
            printf("%d ", elem);
        }
        puts("-1");
    }
}

int main() {
    input();

    solve();

    return 0;
}

타잔의 알고리즘은 기억해야 할 조건들이 코사라주의 알고리즘에 비해 헷갈리는 편이지만, DFS를 한 번만 작성해도 된다는 점에서 타잔의 알고리즘을 더 쉽다고 평가하는 의견도 있습니다. 둘 모두 시간복잡도는 동일하기 때문에 문제를 풀 때는 일반적으로 어떤 알고리즘을 사용해도 괜찮습니다.

2-SAT

SCC 알고리즘의 응용 사례 중 유명한 것으로 2-SAT 문제가 있습니다. SAT 문제는 논리 변수와 논리식이 주어질 때 논리식을 참으로 만드는 논리 변수 조합이 존재하는지를 찾는 문제입니다. 2-SAT은 SAT 문제들 중 특수한 형태의 문제로, 다음 예시에서 볼 수 있듯이 두 개의 변수의 or 연산들이 and 연산으로 결합된 형태의 논리식을 다루는 문제입니다. 이런 형태의 식을 2-CNF 또는 Krom formulas라고 부릅니다.

$(neg x_1 vee x_3) wedge (neg x_2 vee neg x_3) wedge (x_1 vee x_2) wedge (neg x_1 vee x_4) wedge (x_2 vee neg x_4)$

이제 논리식을 그래프로 바꾸는 방법을 알아봅시다.

각각의 논리 변수 $x$ 에 대해 두 개의 정점 $x, ~neg x$ 을 생성합니다.
논리식에 포함된 각각의 $A vee B$ 에 대해, $neg A rightarrow B$ 간선과 $neg B rightarrow A$ 간선을 생성합니다.

위의 예시에서 보여드린 식을 그래프로 바꾸면 다음과 같습니다.

이렇게 그래프를 생성하면 or로 묶인 두 개의 변수 중 적어도 하나는 참이어야 하기 때문에, A에서 B로 가는 간선은 A가 참이라면 B도 반드시 참이라는 것을 의미하게 됩니다. 이제 이 그래프에 SCC 알고리즘을 적용해서 정점들을 컴포넌트로 묶은 이후를 생각해봅시다. SCC의 정의와 간선을 그은 조건 때문에, 컴포넌트 내에 하나의 정점이라도 참이라면 그 컴포넌트는 모두 참이 됩니다. 따라서 같은 컴포넌트에 속한 정점들은 전부 참이거나 전부 거짓이라는 것을 알 수 있습니다.

$x$ 와 $neg x$ 는 다음 세 가지 중 한 가지 관계를 가집니다.

$x$ 와 $neg x$ 가 같은 컴포넌트에 속하는 경우
$x$ 에서 $neg x$ 로 가는 경로(또는 $neg x$ 에서 $x$ 로 가는 경로)만 존재하는 경우
$x$ 와 $neg x$ 간에 경로가 존재하지 않는 경우

첫 번째는 답이 존재하지 않는 경우입니다. 주어진 논리식을 참으로 만드는 논리 변수 조합이 존재하는 것과, 논리 변수 $forall x$ 에 대해 $x$ 와 $neg x$ 정점이 같은 컴포넌트에 속하지 않는 것이 필요충분조건임이 증명되어 있습니다.

두 번째는 위상정렬 했을 때 더 뒤쪽에 존재하는 정점만이 참입니다. 세 번째는 둘 중 어느 것을 참으로 결정해도 상관 없습니다.

그래프가 skew-symmetric하기 때문에 $A, ~B$ 가 같은 컴포넌트에 속한다면 $neg A, ~neg B$ 또한 같은 컴포넌트에 속하고, 이 특징을 이용해 위의 성질들을 증명할 수 있습니다.

위의 성질들을 이용해 각 논리 변수의 값을 다음 방법으로 찾을 수 있습니다.

논리식에서 그래프를 생성합니다.
생성된 그래프에 SCC 알고리즘을 적용합니다.
만약 $x$ 와 $neg x$ 의 SCC 번호가 같은 정점이 존재한다면 주어진 논리식을 만족하는 조합은 존재하지 않습니다.
아니라면, $x$ 의 SCC 번호가 $neg x$ 의 SCC 번호보다 작은 경우 $x$ 가 참입니다.

아래는 구현 코드입니다. BOJ의 2-SAT – 4 문제를 기준으로 작성했습니다.

2-SAT

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;
const int MAX = 20020;

int N, M;
vector < int > from[MAX];

inline int neg(int x) {
    if (x > N) return x - N;
    else return x + N;
}

void input() {
    scanf("%d%d", &N, &M);

    // 그래프 초기화
    for (int i = 0; i < M; i++) {
        int f, s;
        scanf("%d%d", &f, &s);

        // ~X는 N+X로 표현
        if (f < 0) f = -f + N;
        if (s < 0) s = -s + N;

        from[neg(f)].push_back(s);
        from[neg(s)].push_back(f);
    }
}

int stack[MAX], top, id[MAX], currentId, groupId[MAX];
vector < vector < int > > sccGroup;

int traverse(int node) {
    id[node] = ++currentId;
    stack[top++] = node;

    // lowlink를 return 값으로 사용
    int lowlink = id[node];
    for (auto next : from[node]) {
        if (id[next] == 0) {
            // 방문하지 않은 정점
            lowlink = min(lowlink, traverse(next));
        } else if (groupId[next] == 0) {
            // 이미 스택에 들어 있는 정점
            lowlink = min(lowlink, id[next]);
        }
    }

    if (lowlink == id[node]) {
        // 그룹 추가
        sccGroup.push_back(vector < int >());
        while (1) {
            int now = stack[top-1];
            top--;

            // node 하위의 서브트리를 SCC 그룹으로 묶기
            groupId[now] = sccGroup.size();
            sccGroup[groupId[now]-1].push_back(now);

            if (now == node) break;
        }
    }

    return lowlink;
}

void solve() {
    for (int v = 1; v <= 2*N; v++) {
        if (id[v] == 0) {
            traverse(v);
        }
    }

    // x와 ~x가 같은 컴포넌트 안에 속하면 답 없음
    for (int v = 1; v <= N; v++) {
        if (groupId[v] == groupId[neg(v)]) {
            puts("0");
            return;
        }
    }

    // x가 ~x보다 컴포넌트 번호가 작은 경우(그래프 상에서 뒤에 있는 경우) x는 참
    puts("1");
    for (int v = 1; v <= N; v++) {
        printf("%d ", groupId[v] < groupId[neg(v)]);
    }
    puts("");
}

int main() {
    input();

    solve();

    return 0;
}

USACO Contest 2015 12월

2015년 12월 15일 글쓴이 Qwaz·0개의 댓글

USACO Gold랑 Platinum을 쳤다. 나쁘지 않지만 약간 아쉬운 결과. Gold는 1시간컷, Platinum은 A, C 풀고 B 짜다가 시간 종료.

Gold는 특별히 언급할만한건 없다. C가 구현이 좀 귀찮은 편이었지만 전체적인 난이도는 예전 실버급. 오랜만에 USACO 풀어서 파일 입출력을 안 하기도 하고, 정렬을 begin부터 begin까지 하는 등 멍청한 실수를 많이 했다.

Platinum은 칠까 말까 고민했는데 주변에서 들리는 2시간컷 가능하다는 말에 속아서 쳤다. 저 ‘주변’에 속하는 인물들이 다 갓들이라 나는 시간 내에 다 풀지 못했다. ~~시험공부 해야 하는데 흑흑~~ 여기서는 전형적인 문제들이 많이 나왔다. A는 전형적인 트리 DP, C는 전형적인 Lazy Propagation 문제였다. B는 익숙한 개념을 한 번 꼬아서 낸 좋은 문제였지만 풀이를 찾고 시간 내에 코드를 작성하지 못했다. C에서 코딩이 말려서 오래 걸렸던 것이 원인이라 생각되지만 그걸 빼고 생각해도 약간 어려운 수준의 문제라고 평가된다.

나중에 시험이 끝나거나 해서 시간이 좀 많아졌을 때 B를 다시 풀어보는걸로 하고 오늘은 이걸로 마무리!

코드포스 #335

2015년 12월 10일 글쓴이 Qwaz·0개의 댓글

코드포스 #335 div. 1

3개월만에 코드포스를 쳤다. ~~시험기간이라~~ 요 며칠 사이에 백준에서 쉬운 문제들 몇 개 깔짝대고 있었는데, 마침 코드포스가 아침 8시라 시간이 괜찮아서 오랜만에 쳤다. 원래는 잠을 좀 자고 7시쯤 일어나서 씻고 칠 예정이었는데 3시간 반 넘게 누워 있었는데 잠에 들지 못해서 그냥 일어나서 문제 풀면서 손을 풀면서 아침을 맞았다. 잠을 못 잔 덕분에 대회 때 잠기운이 약간 있긴 했지만 다행히 크게 방해되지는 않았다.

대회 시작 즈음에는 ABC 풀면 레드 갈 줄 알았는데, 예상한대로 풀었지만 여기저기 실수하는 바람에 감점을 받아 레이팅 변화는 거의 없을 것 같다. 이번에도 그냥저냥 실력만큼 본 것 같은데, 예전에 실력대로만 보면 되는 시험들에서 망한 경험이 너무 많아서 이런 사소한 사실에도 만족감을 느끼고 있다. 최종 순위는 127위.

A

문제를 대충 읽다가 틀렸다. 기차를 뽑아서 맨 앞이나 맨 뒤에만 넣을 수 있는데, 뽑아서 아무데나 넣을 수 있을 때 최소 정렬횟수를 구하는 게 잘 알려진 문제라 왜 이런 유명한 걸 냈냐고 투덜대면서 풀었다가 Hack 당했다. 저렇게 짜도 pretest 통과하게 해 놓은데서 출제진의 악랄함을 느낄 수 있다. 내가 착각한 문제와 풀이가 크게 다르지 않고, 번호가 연속하는 LIS 중 가장 긴 것을 찾으면 된다.

#include <cstdio>

const int MAX = 100020;

int n, len[MAX];

int main() {
    scanf("%d", &n);

    int maxLen = 1;
    for (int i = 0; i < n; i++) {
        int t;
        scanf("%d", &t);
        if (len[t-1] != 0) {
            len[t] = len[t-1]+1;
            if (maxLen < len[t])
                maxLen = len[t];
        }  else len[t] = 1;
    }

    printf("%d\n", n - maxLen);

    return 0;
}

B

ABC 중 가장 마음에 드는 문제였다. 트리의 간선 길이와 그 간선이 최소신장트리에 포함되는지 여부가 주어지면 그래프를 알아서 잘 구성하면 되는 문제다. 크루스칼 알고리즘으로 MST를 찾을 때, 간선을 길이 순으로 정렬했을 때 특정 간선이 포함되지 않는 경우는 이전의 간선들과 사이클을 이룰 때라는 사실을 적절히 이용하면 된다.

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 100020;

struct Edge {
    int id, len;
    bool used;

    Edge() {}
    Edge(int id, int len, bool used) : id(id), len(len), used(used) {}
};

bool compareLen(const Edge &f, const Edge &s) {
    if (f.len == s.len) return f.used > s.used;
    return f.len < s.len;
}

int n, m;
Edge edge[MAX];

void input() {
    scanf("%d%d", &n, &m);

    for (int i = 0; i < m; i++) {
        int len, used;
        scanf("%d%d", &len, &used);
        edge[i] = Edge(i, len, used);
    }

    sort(edge, edge+m, compareLen);
}

int from[MAX], to[MAX];

bool solve() {
    int last = 1, now = 3, remain = 1;
    for (int i = 0; i < m; i++) {
        Edge &cur = edge[i];
        if (cur.used) {
            from[cur.id] = last;
            to[cur.id] = last+1;
            last++;
        } else {
            if (last < now) return 0;
            from[cur.id] = now;
            to[cur.id] = remain;
            remain--;
            if (remain == 0) {
                now++;
                remain = now-2;
            }
        }
    }
    return 1;
}

void print() {
    for (int i = 0; i < m; i++)
        printf("%d %d\n", from[i], to[i]);
}

int main() {
    input();

    if (solve()) print();
    else puts("-1");

    return 0;
}

C

2015 구글 코드잼 R2 B Kiddie Pool과 굉장히 유사한 문제였다. 코드잼 칠 때는 시간 내에 풀이를 못 떠올렸는데 이번 라운드에서는 풀이 찾는건 금방 성공했다. 하지만 코딩에서 잔실수를 너무 많이 해서 3번이나 WA를 받고 통과할 수 있었다. 말도 안 되는 코드를 짜서 냈는데 pretest에서 걸려서 다행이었다.

문제는 전혀 기하처럼 생기지 않았지만 2차원 벡터로 생각해서 컨벡스헐을 구한 뒤 교차점을 통해 값을 계산하는 문제다. 선분 교차지점 구하는 코드는 안 졸렸으면 금방 유도했을텐데 졸려서 계산하기 싫은 마음에 그냥 StackOverflow에서 가져다 붙였다.

#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;
typedef pair < ll, ll > pll;

#define x first
#define y second

const int MAX = 100020;

int n, targetExp, targetMoney;
pll target, point[MAX];

void input() {
    scanf("%d%d%d", &n, &targetExp, &targetMoney);
    target = pll(targetExp, targetMoney);

    for (int i = 0; i < n; i++) {
        int exp, money;
        scanf("%d%d", &exp, &money);
        point[i] = pll(exp, money);
    }
}

ll ccw(pll a, pll b, pll c) {
    return a.x*b.y + b.x*c.y + c.x*a.y - a.y*b.x - b.y*c.x - c.y*a.x;
}

pll origin = pll(0, 0);
bool compare(const pll &f, const pll &s) {
    return ccw(origin, f, s) > 0;
}

pll stack[MAX];
int top;

void solve() {
    sort(point, point + n, compare);

    stack[top++] = point[0];
    for (int i = 1; i < n; i++) {
        if (top && ccw(origin, stack[top-1], point[i]) == 0) {
            if (stack[top-1].x <= point[i].x) {
                top--;
                while (top >= 2 && ccw(stack[top-2], stack[top-1], point[i]) <= 0) top--;
                stack[top++] = point[i];
            }
        } else {
            while (top >= 2 && ccw(stack[top-2], stack[top-1], point[i]) <= 0) top--;
            stack[top++] = point[i];
        }
    }

    int start = 0, end = top-1;
    while (start != top-1 && stack[start].x <= stack[start+1].x) start++;
    while (end != start && stack[end].y <= stack[end-1].y) end--;

    if (start == end || ccw(origin, stack[start], target) <= 0 || ccw(origin, stack[end], target) >= 0) {
        printf("%.10lf\n", max((double)target.y / stack[end].y, (double)target.x / stack[start].x));
    } else {
        for (int i = start; i < end; i++) {
            double p0_x = 0, p0_y = 0, p1_x = target.x, p1_y = target.y,
                p2_x = stack[i].x, p2_y = stack[i].y, p3_x = stack[i+1].x, p3_y = stack[i+1].y;

            double s1_x, s1_y, s2_x, s2_y;
            s1_x = p1_x - p0_x;     s1_y = p1_y - p0_y;
            s2_x = p3_x - p2_x;     s2_y = p3_y - p2_y;

            double s, t;
            s = (-s1_y * (p0_x - p2_x) + s1_x * (p0_y - p2_y)) / (-s2_x * s1_y + s1_x * s2_y);
            t = (s2_x * (p0_y - p2_y) - s2_y * (p0_x - p2_x)) / (-s2_x * s1_y + s1_x * s2_y);

            if (s >= 0 && s <= 1) {
                printf("%.10lf\n", target.x / (p0_x + (t * s1_x)));
                break;
            }
        }
    }
}

int main() {
    input();

    solve();

    return 0;
}

QwazLab

[카테고리:] Problem Solving

GCJ 2016 R1B

A

C

B

SCC와 2-SAT

SCC

코사라주의 알고리즘(Kosaraju’s Algorithm)

타잔의 알고리즘(Tarjan’s Algorithm)

2-SAT

USACO Contest 2015 12월

코드포스 #335

A

B

C