2020 UCPC 예선 대비 개인 연습 (3)

UCPC 2018 예선

굳이 풀이를 적지 않은 문제 중 A, B, F (+ J?) 정도는 현재의 내가 별 다른 무리 없이 해결 가능하다고 생각한다. (J의 경우는 대회 때 제출이 불가능해진 이후에 그럴싸한 선형 풀이를 찾았던지라, 내 답이 맞는지 모르지만..)

문제 풀이

문제 링크

C. 대회

형섭이의 최적 전략이 EDF(earlist deadline first) 형태의 그리디 전략임을 알 수 있다. 형섭이의 전략이 고정되어 있으므로, 다른 참가자들의 전략을 simulation해주면 되는데, 이 또한 형섭이의 전략과 유사하다.

 

대회들을 종료 시점이 빠른 순으로 정렬하고, 하나씩 보되,

• 형섭이가 참여 중인 대회와 시간대가 겹치면 건너뛰고,
• 해당 대회에 참여할 수 있는 형섭이가 아닌 참가자가 있다면, 그 중 가장 "직전에 참여한 대회의 종료 시각"이 늦은 참가자를 참여시키면 된다.

이는 std::multiset을 사용하면 쉽게 구현할 수 있다. 나는 std::multiset을 사용해야 하는데, 생각 없이 std::set을 써서 몇 번 틀렸다.

D. 별다줄

Trie 자료구조의 좋은 연습문제라고 생각한다.

 

기본적으로는 DP를 활용하는데, $D[i]$를 $T[1:i]$를 만들 수 있는 방법의 수로 정의한다. ($D[0] = 1$)

 

DP를 구체적으로 계산하는 방법을 설명하겠다. 먼저, 주어지는 단어들을 전부 담고 있으며, 각 정점 마다 해당 정점을 prefix로 포함하는 문자열의 수를 저장한 Trie를 만들어주자. $T$를 앞에서 부터 차례로 보면서 DP값을 업데이트 해주는데, $T[i]$를 보는 시점에는 trie에 $T[i: N]$을 넣고 traverse 하면서 $i$에서 새로운 단어의 prefix가 시작하는 경우에 대한 DP값을 업데이트 해주면 된다. (참고로, 이 방법 대로 하면 $T[i]$를 보는 시점에는 $D[i-1]$까지 계산되어 있으므로, 정확성이 보장된다.)

 

설명이 다소 불친절하다 생각되는데, 아래 코드를 참고하는 것을 권장한다. (trie 뼈대 코드는 개인적으로 다른 분의 블로그에 있는게 가독성이 좋다고 생각해서, 이 코드를 기반으로 문제에 맞게 변형했다.)

 

struct Trie {
    bool finish;    //끝나는 지점을 표시해줌
    long long count;
    Trie* next[26];    //26가지 알파벳에 대한 트라이

    Trie() {
        finish = false;
        memset(next, 0, sizeof(next));
        count = 1;
    }

    ~Trie() {
        for (int i = 0; i < 26; i++)
            if (next[i]) delete next[i];
    }

    void insert(const char* key) {
        if (*key == '\0')
            finish = true;    //문자열이 끝나는 지점일 경우 표시
        else {
            int curr = *key - 'a';
            if (next[curr] == NULL) {
                next[curr] = new Trie();    //탐색이 처음되는 지점일 경우 동적할당
            }
            else (*next[curr]).count += 1;
            next[curr]->insert(key + 1);    //다음 문자 삽입
        }
    }

    Trie* find(const char* key, int cnt) {
        if (!cnt) return this;//문자열이 끝나는 위치를 반환
        int curr = *key - 'a';
        if (next[curr] == NULL) return NULL;//찾는 값이 존재하지 않음
        return next[curr]->find(key + 1, cnt - 1); //다음 문자를 탐색
    }

    void traverse(const char *key, int idx, int org){
        if (*key == '\0') return;
        if (idx != org) D[idx] = (D[idx] + count * D[org]) % mod;
        int curr = *key - 'a';
        if (next[curr] != NULL) next[curr] -> traverse(key+1, idx+1, org);
    }
};

I. 육각형 우리 속의 개미

간단한 완전탐색 문제이다. 사실 풀이를 안 적으려 했는데, 내가 이 문제를 해결하며 사용한 모델링이 마음에 들어서 코드만 간단히 기록해둔다. 나는 육각형의 각 정점을 정육면체의 꼭짓점으로 모델링해서 풀었다.

 

struct Point{
    int x, y, z;

    Point(int a, int b, int c){
        x = a; y = b; z = c;
    }
    bool parity(){
        return (x + y + z) % 2;
    }
    bool operator == (const Point &p) const {
        return x == p.x && y == p.y && z == p.z;
    }
};

뒷이야기

작년에 처음 치는 팀 대회로 UCPC 2018 예선 대회를 쳤다. 당시에는 실력도 모자라고, 팀연습도 안했어서 (+ 나의 의지와 관련 없는 사건도 있어서) 본선 대회에 진출하지 못했던 아쉬움이 있는데, 올해는 꼭 진출했으면..

Codeforces Round #652

문제 풀이

문제 링크

B. AccurateLee

손으로 직접 해보면서 규칙을 찾고 코딩하면 되는 문제이다. (증명도 쉽다.) 사실 풀이를 굳이 기록하지 않아도 되겠다는 생각이 들었지만, 이런 류의 쉬운 브레인 퍼즐(?) 문제를 개인적으로 좋아하는지라 간략히 기록해둔다.

 

예를 들어, 00110100101111이라는 문자열이 주어졌다고 생각해보자. 맨 앞의 0 2개와 맨 뒤의 1 4개는 연산을 적용하지 못하므로, 답에 그대로 남게 된다. 가운데의 11010010의 경우에는, 110 ->1, 100 -> 1, 10 -> 0 으로 연산을 적용하고 나면, 110이 되고, 110 -> 0 으로 연산을 적용하면 0 하나만 남는다. 결국 답은 0001111이 된다.

 

결국, 주어진 문자열을 (1) 맨 앞의 연속한 0, (2) 맨 뒤의 연속한 1, (3) 가운데 부분으로 분리해서 생각한다면, (3)이 empty string이라면 (1) + (2), 아니면 (1) + '0' + (2)가 문제의 답이 된다.

C. RationalLee

일단, 가장 큰 $k$개의 수들이 모두 문제의 답에 포함되면 이득임을 알 수 있다. 그러므로, 가장 큰 $k$개의 수들을 $k$명에게 하나씩 분배해주자. 이 때, 1개의 수만 받는 사람의 경우, 받는 수가 문제의 답에 2번 포함됨에 유의하자. 편하게 구현하는 방법은 받는 수의 수가 적은 사람일수록 큰 수를 주면 된다.

 

이후, 나머지 $n - k$개의 수들을 분배하는데, $n-k$개의 수들을 받는 수가 적은 사람부터 차례로 분배해준다. 말로 표현하니 깔끔하지 않은데, 코드를 참고하면 된다.

 

int st = 1;
// A[1] <= A[2] <= ...; 수들
// W[1] >= W[2] >= ...; 사람들
for (int i=1; i<=K; i++){
  ll mval = A[N-(K+1-i)+1];
  for (int j=1; j<=W[i]; j++){
    mval = min(mval, A[st++]);
  }
  ans += mval;
}

D. TediousLee

레벨 $n$인 트리의 자식이 0개인 노드의 수, 1개인 노드의 수, 3개인 노드의 수, 그리고 겹치지 않게 선택할 수 있는 claw의 수를 DP를 통해 관리하자. 각각 $A[n]$, $B[n]$, $C[n]$, $D[n]$이라 하자. $A$, $B$, $C$ 사이의 점화식은 문제에서 명시적으로 주어졌으므로 생략한다.

 

$D$에 대한 점화식을 찾자면, $D[n] = \color{red}{4 (C[n] - C[n-1])} + \color{blue}{D[n-3]}$이 되는데, 빨간 항의 경우 새로 생긴 자식이 3개인 노드를 루트로 하는 claw를 의미하고, 파란 항의 경우, 새로 만든 claw 들과 겹치지 않는 claw들 가운데 겹치지 않게 선택할 수 있는 최대 개수이다.

Flow 연습

Max Flow/Min Cost Max Flow 관련 문제들을 최근 열심히 풀었다. 모델링 하는 실력이 꽤 많이 늘었음을 스스로도 느낄 수 있었다.

구현체 이야기

물론, flow 알고리즘을 직접 공부하고, 직접 구현하면 좋겠지만, 과거 학교 수업에서 배운 flow 알고리즘들을 여럿 구현해본 경험에 의하면, 직접 flow 알고리즘을 효율적으로 구현하기는 쉽지 않았다. (특히 Min Cost Max Flow의 경우 더욱 그렇다.) 무엇보다, 내 지극히 개인적인 견해로는 flow 알고리즘을 구현하는 것 보다 flow에 맞게 모델링하는게 더 중요하다 생각된다.

 

그래서 좋은 구현체 몇 개를 구하고, 내 입맛대로 조금 변형해서(?) 사용하는 쪽으로 방향을 돌렸다. 기본적으로는 Please Open Testdata 팀의 팀노트 (감사하게도 공개되어 있다.) 의 구현체를 주로 활용하는데, 일부 문제의 경우 "헬조선 MCMF"로 널리 알려진 구현체를 활용하곤 한다. (여러 구현체 관련 정보를 알려주신(?) jhnah917님께 감사드립니다.)

문제 풀이

모두 BOJ의 문제 번호와 제목이다. 푼 문제가 너무 많아서 그 중 몇 개만 꼽아서 정리한다.

12918 정리정돈

어떤 물건에 대해 선대칭으로 만들기 위해 다음 두 가지 선택 중 하나를 할 수 있다:

• 다른 물건 하나와 짝지어서 두 물건의 수직 이등분선이 $y$축이 되게 한다.
• 물건을 $y$축 위로 옮긴다.

첫 번째의 경우, ${1 \over 2} \sqrt{(x_i + x_j)^2 + (y_i - y_j)^2}$ 만큼의 cost가 들고, 두 번째의 경우 $|x_i| = {1 \over 2} \sqrt{(x_i + x_i)^2 + (y_i - y_i)^2}$ 만큼의 cost가 든다.

 

따라서, 각 물건 $i$마다 정점 $L_i$와 $R_i$를 만들고, $L_i$와 $R_j$ 사이를 잇는 간선의 cost를 ${1 \over 2} \sqrt{(x_i + x_j)^2 + (y_i - y_j)^2}$로 하는 이분 그래프를 만들면, 최소 가중치 완전 매칭을 구하는 문제가 된다. 이는 MCMF를 이용하여 쉽게 해결할 수 있다.

 

여담. 내가 사용하는 구현체의 경우, 실수 자료형을 이용하면 무한 루프를 도는 문제점이 있어서, 모든 가중치를 $10^6$ 정도의 수를 곱한 후 round 해서 정수 연산만 사용했다.

3640 제독

 

그래프의 각 정점 $u$를 들어가는 정점 $in_u$와 나오는 정점 $out_u$ 2개로 나누어서 flow 그래프를 만들자. 다음과 같이 가중치와 용량을 배정하고 MCMF를 사용하면 된다.

• source - $in_1$: 가중치 0, 용량 2
• $out_n$ - sink: 가중치 0, 용량 2
• $in_k$ - $out_k$: $k = 1, n$ 이면 가중치 0, 용량 2. 아니면 가중치 0, 용량 1.
• $out_u$ - $in_v$ ($u v \in E$): 가중치 $w_{uv}$, 용량 1

13569 Rounding

LR circulation을 구하는 연습문제이다. Row에 해당하는 정점과 Column에 해당하는 정점을 만들고, $(i, j)$ cell에 해당하는 간선의 최소/최대 유량을 ($(i, j)$ cell의 값을 $a_{ij}$라 하면) $\lfloor a_{ij} \rfloor$과 $\lceil a_{ij} \rceil$로 해주면 된다.

17506 주때의 자소서 쓰기

대놓고 MCMF 문제임을 말하고 있는데, 각 문항에 한 개 이상의 스토리를 배정하는게 가장 골때리는 부분이다. 이것의 경우 가중치가 $-10^8$과 같이 매우 작고, 용량이 $3$인 source와 연결된 정점을 만들어 주고, 이 정점에서 각 문항으로 용량 1인 간선을 통해 유량을 흘려주면 된다.

 

가중치가 매우 작은 간선을 만들면, 해당 간선을 반드시 이용하게 된다는 점에 기반한 trick은 MCMF에서 자주 활용되는 것 같다. 유용한 아이디어니 알아두자.