NCPC 2022

어제랑 비슷하게 3인 팀 5시간 셋을 3시간 (2분) 동안 돌았다. 대회 당시 11솔이 최대였고, 나는 10솔로 4등을 했다. (페널티 1143) 한 문제를 못 풀었는데 남은 문제도 크게 어렵진 않아서, 올솔을 못한 게 조금 아쉽다.

A (6분)

가능한 게임 진행 방법이 $2^{21}$가지에 못 미친다는 것을 알 수 있다. 모든 경우에 대해서 가능한지 시도해 보면 된다. 이외에는 크게 언급할 점이 없다.

 

C (24분)

B에서 맞왜틀을 좀 당하다가 바로 C로 갔다. 풀이는 단순히 앞에서부터 가질 수 있는 커피 수를 계속 관리하면 쉽다.

 

D (28분)

$(r, 1)$이 유효한 답이다.

 

F (1시간 9분)

일단 각 팀명의 길이를 구해야 한다. 1번 팀의 팀명을 $x$로 두면 이후 팀들의 팀명을 $ax+b$꼴로 나타낼 수 있고, 방정식을 풀어서 $x$의 값을 구해 주면 된다. $n > 2$이면 $x$가 하나로 정해지거나, $x$로 가능한 값이 없거나 둘 중 한 가지가 된다. $n = 2$면 $x$ 구하는 게 좀 까다로운데, 이는 후술. $x$가 정해지면, 총 문자열 길이 합이 $10^6$ 이하이므로 단순히 하나씩 검사해 보면 된다.

 

$n=2$일 때 $x$를 정하는 게 까다롭다. 문자열 $A$를 몇 번 rotate해서 문자열 $B$가 될 수 있는지 구하는 식의 문제를 풀어야 한다. 문자열 알고리즘에 능하지 않아서 해싱으로 풀었는데, 좋은 풀이는 아니다. 두 문자열을 합치고 Suffix Array를 구한다든지 하는 등의 풀이가 존재할 것으로 보인다.

 

G (1시간 15분)

풀 문제 개수 $x$가 정해지면, $x$개의 문제를 고르는 것은 쉽다: 가장 맞힐 확률이 높은 문제를 고르면 된다. 따라서 $x$를 $1$부터 $N$까지 전부 시도해 보면 머리를 복잡하게 쓰지 않아도 풀릴 것이다.

 

먼저 문제를 확률 내림차순으로 정렬해 둔다. 이후 $DP[i][j]$를 앞 $i$개 문제를 풀었고 그 중 $j$개를 맞힐 확률이라고 하자. $DP[i-1][j]$와 $DP[i-1][j-1]$로부터 $DP[i][j]$를 구할 수 있다. 이제 점수에 대한 조건을 만족하는 칸에 대해 확률의 최댓값을 구하면 된다.

 

H (1시간 18분)

각 $i$에 대해, $A_j \le A_{j+1} \le \cdots \le A_i$가 되는 최소 $j$를 구할 수 있는데, 앞에서부터 DP를 돌려주면 된다. 마찬가지로 뒤에서부터 DP를 돌려 $A_i \ge A_{i+1} \ge \cdots \ge A_j$가 되는 최대 $j$도 구해 주고, 각 점이 최댓값일 때의 답을 쭉 구해준 뒤 그 중 최댓값을 구하면 된다.

 

B (1시간 36분)

풀이 자체는 생각할 만 하다. 트리 내에 길이 3의 경로가 있는 경우, 그 경로를 $A$ - $B$ - $C$ - $D$라고 하자. 처음에 이 네 점에 있는 개미들이 끝까지 뭉치지 않게 할 수 있음을 보이면, 문제가 해결된다. 먼저 $B$와 $A$를 각각 고르면 저 네 개미들은 모두 두 점 $A$와 $B$에 모일 것이다. 이후 남은 정점들을 dfs ordering 순서대로 방문해 주면 재밌는 일이 일어난다. 두 개미는 절대 합쳐질 일이 없다. 왜냐하면, 두 개미가 있는 정점이 항상 달라져도, 계속 간선으로 연결되어 있는 두 정점 위에 있고, 간선으로 연결된 두 정점 위에 있는 두 개미가 합쳐질 조건은 두 정점 중 하나에 쿼리가 날아가는 경우밖에 없는데, 잘 살펴보면 그런 쿼리가 주어질 일이 없다.

 

최대 길이가 2라는 것은, 그래프가 스타 그래프라는 것이며, 중심 정점을 고르는 순간 모든 개미가 하나로 합쳐지므로 불가능함이 자명하다.

 

일단 맞긴 맞았는데, 대체 어디를 잘못 구현해서 초반에 많이 틀린 건지 모르겠다. 고쳐서 틀린 게 맞을 부분을 고친 게 아닌데, 아마 뚫었을 가능성도 있다고 본다. 하지만 풀이 자체는 맞기 때문에 만족한다.

 

J (2시간 2분)

좋은 문제는 아니다. 그냥 단순히 각 로봇을 도착지로 옮겨주는 과정을 반복하면 되는데, 먼저 x좌표를 잘 맞춰주고, y좌표를 잘 맞춰주면 된다.

 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
int x[52], y[52];
bool done[52];
int px, py, tx, ty;

int find(int X, int Y){
    for(int i=1; i<=n; i++) if(!done[i] && x[i] == X && y[i] == Y) return i;
    return false;
}

void moveto(int nx, int ny){
    if(nx==px-1) puts("left");
    else if(nx==px+1) puts("right");
    else if(ny==py-1) puts("down");
    else puts("up");

    int dx = nx - px, dy = ny - py;
    px = nx, py = ny;
    int tmp = find(nx, ny);
    while(tmp){
        int ntmp = find(nx+dx, ny+dy);
        x[tmp] += dx, y[tmp] += dy;
        if(x[tmp] == tx && y[tmp] == ty) done[tmp] = 1;
        nx += dx, ny += dy;
        tmp = ntmp;
    }
}

int main(){
    scanf("%d", &n);
    scanf("%d %d %d %d", &px, &py, &tx, &ty);
    for(int i=1; i<=n; i++){
        scanf("%d %d", &x[i], &y[i]);
    }

    for(int i=1; i<=n; i++){
        if(done[i]) continue;
        /// go to (100, 100) or more
        while(px <= 100){
            if(!find(px+1, py) || find(px, py+1)) moveto(px+1, py);
            else moveto(px, py+1);
        }
        while(py <= 100) moveto(px, py+1);

        if(x[i] < tx){
            while(px > -100) moveto(px-1, py);
            while(py > y[i]) moveto(px, py-1);
            while(x[i] < tx) moveto(px+1, py);
            while(px > -100) moveto(px-1, py);
            while(py <= 100) moveto(px, py+1);
            while(px <= 100) moveto(px+1, py);
        }
        if(x[i] > tx){
            while(py > y[i]) moveto(px, py-1);
            while(x[i] > tx) moveto(px-1, py);
            while(px <= 100) moveto(px+1, py);
            while(py <= 100) moveto(px, py+1);
        }

        if(y[i] < ty){
            while(py > -100) moveto(px, py-1);
            while(px > x[i]) moveto(px-1, py);
            while(y[i] < ty) moveto(px, py+1);
            while(py > -100) moveto(px, py-1);
            while(px <= 100) moveto(px+1, py);
            while(py <= 100) moveto(px, py+1);
        }
        if(y[i] > ty){
            while(px > x[i]) moveto(px-1, py);
            while(y[i] > ty) moveto(px, py-1);
            while(py <= 100) moveto(px, py+1);
            while(px <= 100) moveto(px+1, py);
        }
    }

    for(int i=1; i<=n; i++) assert(done[i]);

    return 0;
}

 

E (2시간 23분)

먼저 최소 사이클 길이를 구한다. 각 정점에서 차례로 bfs를 해 보면서, 최단길이로 가는 방법이 2가지 이상인 정점이나 같은 최단거리를 가지는 두 정점이 연결된 경우를 살펴보면 된다. (각각 길이 2d, 2d+1의 사이클이 된다. d는 그 정점에서 시작점까지의 거리)

 

이제 앞과 비슷한 방법으로 각 정점에서 다시 bfs를 돌리면서, 사이클의 개수를 셀 수 있다.

 

I (3시간 2분)

어디서 본 문제 같았는데, 풀이가 잘 생각이 안 나서 다시 풀었다. 기본적인 접근은 시작 서열(차례로 모두 연결됨)과 도착 서열(차례로 모두 연결되어 있지 않음)을 관리하는 것이다. 즉, 어떤 시점에 문제풀이 상태를 보면, 연결된 서열 $A_1 - A_2 - \cdots - A_{k'}$와 연결되지 않은 서열 $B_1 - B_2 - \cdots - B_k$가 있을 것이다. $A_i$와 $A_{i+1}$ 사이에는 모두 간선이 있고, $B_i$와 $B_{i+1}$ 사이에는 모두 간선이 없다. 일단 지금은 $A_1 = 1$이라고 생각하자.

 

이제 새 정점 $x$를 추가한다. $x$가 $A_k$와 연결되거나 $B_{k'}$와 연결되지 않았다면 그냥 끝에 붙여주면 된다. 만약 둘 다 아니라면 상황이 조금 복잡해지는데, $A_k$와 $B_{k'}$가 연결되어 있다면 $B_{k'}$를 $A$ 끝쪽으로 옮겨 주고, $A$의 그 뒤쪽에 $x$를 붙여서 해결한다. ($B$의 사이즈가 1일 때에 관한 예외처리가 있는데, 그냥 아무거나 다시 $B$로 넣어주면 해결된다.) 만약 그 반대라면 비슷한 방식으로 대칭적으로 해주면 되는데, 이 경우에는 예외처리가 많이 힘들다. 1번 정점이 시작점이어야 한다는 조건이 있기 때문이다. 그래서 이때는 1번 정점을 $B$의 시작점으로 설정해 줘야 한다. 지금까지 본 모든 정점들을 다 $B$ 안에 집어넣고, $A$에는 $x$ 하나만 넣어주면 된다.

 

위에서 본 것들을 전부 하기 위해서는 처리해야 할 연산이 많다. 연결 리스트를 짜는데, 앞뒤 추가 / 뒤집기 / 연결 리스트끼리 swap 등을 할 수 있어야 한다. 다행히도 std::deque 두 개를 들고 다니면 이게 가능하다. (deque를 두 개 관리하는데, 하나는 정순, 하나는 역순으로 관리)

 

K (Unsolved)

추후 풀이 후 추가 예정