Codeforces Round 864 (Div. 2) 풀이

Problems

Submissions

Standing

 

 

A. Li Hua and Maze

Problem

A. Li Hua and Maze

Problem - A - Codeforces

 n*m 크기의 직사각형 미로가 있다. (r, c)를 위에서부터 r번째 행, 왼쪽부터 c번째 열이라고 하자. 두 칸이 변을 공유하고 있다면 그 두 칸은 인접하다고 부른다. 길은 인접한 빈칸들의 수열이다.

 

 각 칸들은 초기에 모두 비어 있다. Li Hua는 ($(x_1, y_1)$과 $(x_2, y_2)$를 제외하고) 몇 개의 칸들을 고를 수 있다. 그리고 그 칸들에 장애물을 설치한다. 그는 $(x_1, y_1)$에서 $(x_2, y_2)$까지 가는 길이 없도록 하기 위해 설치해야 하는 장애물의 최소 개수를 알고 싶어 한다.

 

 당신이 Li Hua라고 가정하고, 이 문제를 풀어라.

 

Input

 첫째 줄에는 테스트 케이스의 수를 나타내는 하나의 정수 $t(1 \leq t \leq 500)$가 주어진다.

 

 각 테스트 케이스의 첫 번째 줄에는 미로의 크기를 나타내는 두 정수 $n, m(4 \leq n, m \leq 10^9)$이 주어진다.

 

 각 테스트 케이스의 두 번째 줄에는 시작점과 끝점의 좌표를 나타내는 4개의 정수 $x_1, y_1, x_2, y_2 (1 \leq x_1, x_2 \leq n, 1 \leq y_1, y_2 \leq m)$가 주어진다.

 

 $|x_1 - x_2| + |y_1 - y_2| \geq 2$임이 보장된다.

 

Output

 각 테스트케이스에 대하여 $(x_1, y_1)$에서 $(x_2, y_2)$로 가는 길이 없도록 놓어야 하는 장애물의 최소 개수를 출력하여라.

 

Example

input	output
3 4 4 2 2 3 3 6 7 1 1 2 3 9 9 5 1 3 6	4 2 3

 

Note

 테스트 케이스 1에서, (1, 3), (2, 3), (3, 2), (4, 2)에 장애물을 놓을 수 있다. 그러면 (2, 2)에서 (3, 3)으로 가는 길은 존재하지 않는다.

A. Li Hua and Maze - test case 1

 

Tutorial

 이 문제의 핵심은 시작 칸 혹은 끝 칸의 인접한 4칸에 장애물을 두면 길을 없앨 수 있다는 사실이다. 즉, 우리는 문제의 답이 최대 4가 됨을 알 수 있다. 추가로 생각해주어야 할 점은 시작 칸과 끝 칸 사이에 가로 혹은 세로로 장애물을 둬도 길을 없앨 수 있고, 이 경우 필요한 장애물이 더 적을 수도 있다는 것이다. 그러나 다행히도 미로의 가로와 세로의 크기는 4 이상이기에 이 경우가 더 작은 답을 도출해 낼 일은 없다.

 

 이제 우리는 답이 4 이하인 경우가 존재하는지 확인해 주면 된다. 입력으로 주어지는 칸은 3가지 경우로 나눌 수가 있다. 모서리에 있는 경우, 모서리가 아닌 변에 있는 경우, 모서리와 변이 아닌 다른 칸에 있는 경우이다. 각각 인접한 칸이 2, 3, 4칸이므로 시작 칸과 끝 칸이 모서리 혹은 변에 있는 칸인지만 확인해 주면 문제를 쉽게 풀 수 있다.

 

Solution

#include <iostream>

using namespace std;

bool check_corner(int x, int y, int n, int m)
{
    if(x == 1 && y == 1) return true;
    if(x == 1 && y == m) return true;
    if(x == n && y == 1) return true;
    if(x == n && y == m) return true;
    return false;
}

bool check_edge(int x, int y, int n, int m)
{
    if(x == 1 || x == n || y == 1 || y == m) return true;
    return false;
}

int main()
{
    int t, n, m, x1, y1, x2, y2;

    cin >> t;
    while(t--){
        cin >> n >> m;
        cin >> x1 >> y1 >> x2 >> y2;

        if(check_corner(x1, y1, n, m) || check_corner(x2, y2, n, m)) cout << 2 << '\n';
        else if(check_edge(x1, y1, n, m) || check_edge(x2, y2, n, m)) cout << 3 << '\n';
        else cout << 4 << '\n';
    }
    return 0;
}

 

 

B. Li Hua and Pattern

Problem

 

B. Li Hua and Pattern

Problem - B - Codeforces

 Li Hua는 각 칸이 파란색 혹은 빨간색인, n*n 크기의 패턴을 가지고 있다. 그는 정확히 k번의 작업을 수행할 수 있다. 각 작업에서, 그는 하나의 칸을 고르고, 그 칸의 색을 빨간색에서 파란색으로 혹은 파란색에서 빨간색으로 바꿀 수 있다. 원한다면 각 칸은 여러 번 선택될 수 있다. $180^{\circ}$ 돌려도 같은 패턴을 만드는 것이 가능할까?

 

 당신이 Li Hua라고 가정하고, 이 문제를 풀어라.

 

Input

 첫째 줄에는 테스트 케이스의 수를 나타내는 하나의 정수 $t(1 \leq t \leq 100)$가 주어진다.

 

 각 테스트 케이스의 첫째 줄에는 패턴의 크기와 작업의 수를 나타내는 2개의 정수 $n, k(1 \leq n \leq 10^3, 0 \leq k \leq 10^9)$가 주어진다.

 

 다음 n개의 줄에는 파란색은 0, 빨간색은 1로 초기 칸의 색에 대한 정보를 나타내는 n개의 정수 $a_{i, j}(a_{i, j} \in \{0, 1\})$가 주어진다.

 

 모든 테스트 케이스에 대하여 n의 합이 $10^3$을 넘지 않음이 보장된다.

 

Output

 각 입력에 대하여, 정확히 k번의 작업 후에 $180^{\circ}$ 돌려도 같은 패턴을 만드는 것이 가능하면 "YES"를 그렇지 않으면 "NO"를 출력하여라.

 

 어떠한 대소문자로도 출력이 가능하다. 예를 들어, "yEs", "yes", "Yes", "YES" 들이 답이 될 수 있다.

 

Example

input	output
3 4 0 1 1 1 1 0 0 0 1 1 0 1 0 1 1 1 1 4 3 1 0 1 1 1 0 0 0 0 1 0 1 1 1 0 1 5 4 0 0 0 0 0 0 1 1 1 1 0 1 0 0 0 1 1 1 1 1 0 0 0 0 0	NO YES YES

 

Note

 테스트 케이스 1에서, 당신은 아무런 작업을 할 수 없다. 패턴을 돌리면 오른쪽과 같다.

B. Li Hua and Pattern - test case 1

 테스트 케이스 2에서, (2, 1), (3, 2), (3, 4)에 대하여 작업을 수행할 수 있다. 가운데 그림은 작업 수행 후 패턴이고, 오른쪽 그림은 그 패턴을 돌린 패턴이다.

B. Li Hua and Pattern - test case 2

 

Tutorial

 돌려도 같은 패턴이 되기 위해 필요한 최소 작업 횟수를 먼저 구할 수 있다면 문제를 쉽게 풀 수 있다. 그렇다면 필요한 최소 작업 횟수는 어떻게 구할까? 모든 (i, j) 칸에 대하여 (n-i-1, n-j-1) 칸과 색이 다른 칸의 개수를 세어주면 된다.(0-based 기준이다.) 돌렸을 때 매칭되는 두 칸의 색이 같다면 굳이 색을 바꿀 필요가 없으며, 두 칸의 색이 달라도 둘 중 아무 칸이나 색을 바꿔주면 돌렸을 때 색이 같아지기 때문이다. 여기서 구현 시 팁은 정말 모든 (i, j) 칸에 대하여 (n-i-1, n-j-1) 칸과 비교하는 것이다. 그렇게 되면 돌렸을 때 매칭되는 모든 쌍들을 2번씩 살펴보게 되는데, 이는 색이 다른 칸의 개수를 2로 나눠줌으로써 해결할 수 있다.

 

 이제 우리는 돌려도 같은 패턴이 되기 위해 필요한 작업의 최소 횟수를 구했다. 즉, k는 무조건 앞에서 구한 작업의 최소 횟수보다는 같거나 커야 한다는 것이다. k가 최소 횟수보다 작은 경우는 제쳐두고, 그렇다면 우리는 (k - 필요한 작업의 최소 횟수)만큼의 작업을 더 수행해 주어야 한다. 이 잉여 작업들을 어떻게 처리해 주어야 할까? 우리는 같은 칸을 여러 번 선택해도 된다. 그리고 같은 칸을 2번 선택하면 그 칸의 색은 바뀌지 않는다. 즉, (k - 필요한 작업의 최소 횟수)가 짝수이면 돌려도 같은 패턴을 만들 수 있다. 그리고 하나의 경우가 더 있다. (처음에 이걸 생각 못해 한 번 틀렸다 ㅜㅜ) 바로 n이 홀수인 경우다. 이 경우 정가운데에 칸이 하나 있고 이는 무슨 색이든 돌렸을 때 패턴에 영향을 주지 않는다. 즉, n이 홀수인 경우엔 잉여 작업 횟수가 얼마든 정가운데 칸에 대해 작업을 수행하면 돌려도 같은 패턴이 된다.

 정리하면 아래와 같다.

• k < 필요한 최소 작업 횟수 : NO
• (k - 필요한 최소 작업 횟수) == 짝수 or n이 홀수 : YES
• else : NO

 

Solution

#include <iostream>

using namespace std;

int arr[1010][1010];

int main()
{
    int t, n, k, i, j, cnt;

    cin >> t;
    while(t--){
        cin >> n >> k;
        for(i=0; i<n; i++){
            for(j=0; j<n; j++){
                cin >> arr[i][j];
            }
        }

        cnt = 0;
        for(i=0; i<n; i++){
            for(j=0; j<n; j++){
                cnt += arr[i][j] ^ arr[n-i-1][n-j-1];
            }
        }
        cnt /= 2;

        if(k < cnt) cout << "NO\n";
        else if(n%2 == 1 || (k-cnt)%2 == 0) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}

 

 

C. Li Hua and Chess

Problem

C. Li Hua and Chess

Problem - C - Codeforces

 이 문제는 상호작용 문제이다.

 

 Li Ming과 Li Hua는 게임을 하고 있다. Li Hua는 n*m 크기의 체스판을 가지고 있다. $(r, c) (1 \leq r \leq n, 1 \leq c \leq m)$을 위에서부터 r행, 왼쪽에서부터 c열의 칸이라고 하자. Li Ming은 체스판에 킹을 올려두고, Li Hua는 킹의 위치를 맞춰야 한다.

 

 Li Hua는 3번 이하로 질문할 수 있다. 각 질문에서 그는 하나의 칸을 고르고 킹이 선택한 칸까지 가기 위해 최소 몇 번 움직여야 하는지를 물어본다. 각 질문은 독립적이다. 이는 킹이 실제로는 움직이지 않는다는 것을 의미한다.

 

 킹은 $max\{|x-x'|, |y-y'|\} = 1$인 경우에만 $(x, y)$에서 $(x', y')$으로 움직일 수 있다. (아래의 그림을 참고하여라.)

C. Li Hua and Chess - movement of king

 킹의 위치는 상호작용이 일어나기 전에 결정된다.

 

 당신이 Li Hua라고 가정하고, 이 문제를 풀어라.

 

 

Interaction

 첫째 줄에는 테스트 케이스의 수를 나타내는 하나의 정수 $t(1 \leq t \leq 10^3)$가 주어진다.

 

 각 테스트 케이스의 첫째 줄에는 체스판의 크기를 나타내는 두 정수 $n, m(1 \leq n, m \leq 10^9)$이 주어진다. 이후 상호작용이 시작된다.

 

 질문을 하기 위해서는 "? r c" (큰따옴표 제외, $1 \leq r \leq n, 1 \leq c \leq m$)을 출력하여라. 그러면 킹이 선택한 칸까지 가기 위해 필요한 최소 움직임에 대한 답변이 표준 입력으로 입력된다.

 

 만약 당신의 프로그램이 잘못된 질문을 한다면, 채점 시스템은 즉시 프로그램을 종료하고 당신의 프로그램을 Wrong answer로 판단한다.

 

 답을 맞히기 위해선 "! r c" (큰따옴표 제외, (r, c)는 초기 킹의 좌표)로 출력하여라. 답을 맞히는 것은 3번의 질문 제한에 포함되지 않는다는 것에 유의하여라.

 

 출력 후에 flush 하는 것을 잊지 마라. 그렇지 않으면 Idleness limit exceeded를 받을 수도 있다. flush를 하기 위해선 다음을 사용하여라:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• see the documentation for other languages.

 

Example

input	output
2 3 4 1 2 5 3 3 1 2	? 2 3 ? 2 4 ! 2 2 ? 2 2 ? 5 2 ? 5 3 ! 5 1

 

Note

 테스트 케이스 1에서, 킹은 (2, 2)에 있다. (2, 3)까지 가기 위해 1번의 움직임이, (2, 4)까지 가기 위해서는 2번의 움직임이 필요하다.

C. Li Hua and Chess - test case 1

 예제의 질문들이 합리적이지 않을 수 있다는 점에 유의하여라. 단지 질문의 예를 나타낸 것이다.

 

Tutorial

 이 문제를 처음 봤을 때 2차원 좌표평면에서 서로 다른 두 점 $(x_1, y_1), (x_2, y_2)$와의 거리가 각각 $d_1, d_2$인 점을 찾는 수학적 문제가 생각났다. 이 문제는 어떻게 풀지? 이 문제는 각각 중심이 $(x_1, y_1), (x_2, y_2)$이고 반지름이 $d_1, d_2$인 두 원을 그려 교점을 찾아주면 된다.

 

 위와 같은 방법으로 문제를 접근하면 될 거라 생각하였고, 처음 두 점을 (1,1)과 (1, m)으로 잡았다. 그러나 문제가 발생하였다. 위의 수학문제와 다르게 특정 점과 d만큼 떨어진 칸들이 원이 아니라 정사각형 모양의 형태를 띤다는 것이었다. 이렇게 되면 만약 그려진 두 정사각형이 변을 공유하는 경우 겹치는 칸이 1개 혹은 2개가 아니라 3개 이상이 될 수도 있는 것이었다. 처음에는 그렇기 때문에 3번째 질문이 있구나 싶었지만 이내 (1,1)과 (1, m)으로 질문하면 두 답변이 (n-1)/2인 경우 답으로 가능한 칸들이 한 줄로 표현되지 않는다는 것을 깨달았다.

 

 위의 해결 방안으로 (1,1) 칸과 (n, m) 칸을 처음 두 질문으로 하였다. 물론 이 경우에도 그려지는 두 정사각형이 한 변을 공유할 수도 있다. 그러나 교점이 하나 혹은 두 개가 나오거나 한 줄로만 나타난다는 것은 보장이 된다. 교점이 하나면 그게 바로 답이 되고, 두 개인 경우는 그중 하나를 질문하여 거리가 0이면 그 칸이 답, 그렇지 않으면 다른 칸이 답이 된다. 그려지는 두 정사각형이 한 변을 공유하여 교점이 한 줄로 나타나는 경우엔 공유하는 칸들 중 끝점을 질문하면 그 점으로부터 답변받은 거리만큼 떨어진 칸이 답이 된다는 것을 알 수 있다.

 

 그리고 추가로 주의해야 할 점은 교점이 되는 칸들이 체스판 범위를 벗어날 수도 있다. 이 경우 다른 적절한 점을 질문하는 코드를 추가로 작성해 주어야 한다. (처음에 이를 생각하지 못하고 제출했다 제출 횟수를 한번 날렸다. ㅜㅜ)

Solution

#include <iostream>

using namespace std;

int main()
{
    int t, n, m, d1, d2, d3, r, c;

    cin >> t;
    while(t--){
        cin >> n >> m;

        r = c = -1;

        cout << "? 1 1\n";
        cout.flush();
        cin >> d1;

        cout << "? " << n << ' ' << m << '\n';
        cout.flush();
        cin >> d2;

        if(d1 + d2 == n-1) r = d1+1;
        if(d1 + d2 == m-1) c = d1+1;

        if(r == -1 && c == -1){
            if(d1+1 <= n && m-d2 >= 1){
                cout << "? " << d1+1 << ' ' << m-d2 << '\n';
                cout.flush();
                cin >> d3;

                if(d3 == 0){
                    r = d1+1;
                    c = m-d2;
                }
                else{
                    r = n-d2;
                    c = d1+1;
                }
            }
            else{
                r = n-d2;
                c = d1+1;
            }
        }
        if(r == -1){
            r = min(d1+1, n);
            cout << "? " << r << ' ' << c << '\n';
            cout.flush();
            cin >> d3;

            r -= d3;
        }
        if(c == -1){
            c = min(d1+1, m);
            cout << "? " << r << ' ' << c << '\n';
            cout.flush();
            cin >> d3;

            c -= d3;
        }

        cout << "! " << r << ' ' << c << '\n';
        cout.flush();
    }
    return 0;
}

 

 

D. Li Hua and Tree

Problem

D. Li Hua and Tree

Problem - D - Codeforces

 Li Hua는 n개의 정점과 n-1개의 간선으로 이루어진 트리를 가지고 있다. 트리의 루트는 1번 정점이다. 정점 i는 $a_i$의 중요도를 가지고 있다. 서브트리의 크기는 서브트리에 있는 정점의 개수로 정의하며, 서브트리의 중요도는 서브트리에 있는 정점들의 중요도 합으로 정의된다. 말단이 아닌 정점의 무거운 자식은 가장 큰 크기의 서브트리를 가진 자식이다. 만약 그러한 자식이 여러 개 존재한다면, 무거운 자식은 번호가 가장 작은 정점이 된다.

 

 Li Hua는 m개의 작업을 수행하기를 원한다:

• "1 x" $(1 \leq x \leq n) - 정점 x를 루트로 하는 서브트리의 중요도를 계산한다.
• "2 x" $(2 \leq x \leq n) - 정점 x의 무거운 자식을 위로 올린다. 공식화하자면, $son_x$를 정점 x의 무거운 자식, $fa_x$를 정점 x의 부모 정점으로 나타내자. 그는 x와 $fa_x$ 사이의 간선을 제거하고 $son_x$와 $fa_x$ 사이에 간선을 추가하고자 한다. x가 루트가 아님이 보장되지만 x가 말단이 아니라는 것은 보장되지 않는다. 만약 x가 말단이라면 이 작업을 무시하여라.

 

 당신이 Li Hua라고 가정하고, 이 문제를 해결하여라.

 

 

Input

 첫째 줄에는 트리의 정점 개수와 작업의 수를 나타내는 2개의 정수 $n, m(2 \leq n \leq 10^5, 1 \leq m \leq 10^5)$이 주어진다.

 

 둘째 줄에는 각 정점들의 중요도를 나타내는 n개의 정수 $a_1, a_2, ... , a_n (-10^9 \leq a_i \leq 10^9)$이 주어진다.

 

다음 n-1개의 줄에는 트리의 간선들이 주어진다. i번째 줄에는 간선의 양 끝을 나타내는 두 정수 $u_i, v_i (1 \leq u_i, v_i \leq n, u_i \neq v_i)$가 주어진다.

 

 다음 m개의 줄에는 작업들이 주어진다. j번째 작업은 두 정수 $t_j, x_j (t_j \in \{1, 2\}, 1 \leq x_j \leq n, x_j \neq 1$ if $t_j = 2)$로 이루어져 있다.

 

Output

 각 "1 x" 질문에 대하여, 답을 한 줄씩 출력하여라.

 

Example

input	output
7 4 1 1 1 1 1 1 1 1 2 1 3 2 4 2 5 3 6 6 7 1 6 2 3 1 6 1 2	2 3 3
10 14 -160016413 -90133231 -671446275 -314847579 -910548234 121155052 -359359950 83112406 -704889624 145489303 1 6 1 10 10 8 1 4 3 4 2 7 2 5 3 2 9 8 1 4 2 2 2 4 1 4 1 10 2 10 1 9 1 6 2 8 2 10 1 5 1 8 1 1 2 5	-2346335269 -314847579 -476287915 -704889624 121155052 -1360041415 228601709 -2861484545

 

Note

 첫 번째 예제에서:

 초기 트리는 다음과 같다:

D. Li Hua and Tree - initial tree of first example

 6의 서브트리의 중요도는 $a_6 + a_7 = 2$이다.

 3의 무거운 자식(6)을 올린 후의 트리는 다음과 같다:

D. Li Hua and Tree - rotated tree of first example

 6의 서브트리의 중요도는 $a_6 + a_3 + a_7 = 3$이다.

 2의 서브트리의 중요도는 $a_2 + a_4 + a_4 = 3$이다.

 

 

Tutorial

 개인적으로 그리 좋은 문제라고 생각하지는 않는다. 아이디어 문제라기엔 구현 문제에 가까웠다고 생각하기 때문이다. (물론 그렇다고 풀이가 쉽다는 것은 아니다.)

 

 n과 m 범위를 보면 알 수 있듯이 당연히 매 작업마다 서브트리의 중요도를 정직하게 구하면 시간초과가 난다. 그렇다면 매 작업마다 중요도를 효율적으로 구해줘야 한다는 것인데... 사실 특별한 알고리즘이 필요한 건 아니고 미리 구해놓은 중요도를 출력해주기만 하면 된다. 오히려 무거운 자식을 올릴 때 이 작업을 전부 처리한다. 그러나 그 작업 또한 엄청난 아이디어를 요구하지는 않는다.

 

 처음에는 어려워 보였으나 자식들을 pair set을 이용하여 관리하면 문제가 쉽게 해결된다. 무거운 자식 정의 자체가 크기가 제일 큰 서브트리이기에 pair의 first를 자식 서브트리의 크기, second를 그 자식의 번호로 저장해 두면 빠르게 무거운 자식을 찾을 수 있다. 무거운 자식을 올리는 과정에서 자식 set과 각 노드의 크기 및 중요도를 수정하는 작업이 조금 귀찮을 수는 있지만 어떻게 바뀌는지 차근차근 생각해 보면 그리 어렵지는 않다. (set에 begin, find, erase 함수가 있어 정말 차근차근하면 된다.)

 

Solution

#include <iostream>
#include <vector>
#include <set>

#define pii pair<long long, long long>

#define MAXN 100010

using namespace std;

long long a[MAXN], sum[MAXN], sz[MAXN], f[MAXN];
vector<int> edge[MAXN];
set<pii> son[MAXN];

void dfs(int v, int p)
{
    int i, u;

    sum[v] = a[v];
    sz[v] = 1;
    f[v] = p;

    for(i=0; i<edge[v].size(); i++){
        u = edge[v][i];
        if(u == p) continue;
        dfs(u, v);

        sum[v] += sum[u];
        sz[v] += sz[u];
        son[v].insert({-sz[u],u});
    }
}
int main()
{
    int n, m, i, u, v, x, z, y, p;

    cin >> n >> m;
    for(i=1; i<=n; i++) cin >> a[i];
    for(i=0; i<n-1; i++){
        cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }

    dfs(1, 0);

    while(m--){
        cin >> z >> x;
        if(z == 1){
            cout << sum[x] << '\n';
        }
        else{
            if(son[x].size() == 0) continue;
            auto it = son[x].begin();
            y = (*it).second;
            p = f[x];

            auto fit = son[p].find({-sz[x],x});
            son[p].erase(fit);
            
            sum[x] -= sum[y];
            sz[x] -= sz[y];
            f[x] = y;
            son[x].erase(it);

            sum[y] += sum[x];
            sz[y] += sz[x];
            f[y] = p;
            son[y].insert({-sz[x],x});

            son[p].insert({-sz[y],y});
        }
    }

    return 0;
}

 

 

마치며...

 작년부터 올해 초까지 영어 성적이 나오지 않아 다른 일들을 하지 못했다. 그러다 저번주에 극적으로 목표 점수를 달성해 여유가 생기기 시작했고, 오랜만에 Codeforces를 풀게 되었다. 앞 문제들을 빨리 풀지 못하기도 하였고, D번이 아이디어 문제가 아닌 구현 문제였기에 만족스러운 대회는 아니었지만, 발목을 잡고 있던 영어를 떨쳐내고 본업으로 돌아왔다는 느낌을 주는 즐거운 대회였다.