랜덤 마라톤 3주차

세 번째 마라톤이다. 앞 두 마라톤을 전부 풀었지만 문제의 난이도는 거의 비슷한 것 같다. P3보다 높은 난이도가 나오기를 기다리고 있는데, 아직은 때가 아닌 것 같다.

A. Поиски

다음 세 가지 케이스로 나눌 수 있다.

• $x>0$: 문자열에 L과 R이 둘 다 존재하거나, R의 개수가 $x$ 이하면 가능하다.
• $x < 0$: 문자열에 L과 R이 둘 다 존재하거나, L의 개수가 $-x$ 이하면 가능하다.
• $x=0$: 문자열에 L과 R이 둘 다 존재하면 가능하다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

string str;
int lc, rc;

int main(){
    cin >> str;
    for(char c: str){
        if(c=='L') lc++;
        else rc++;
    }
    int x;
    cin >> x;
    if((x < 0 && lc && (rc || lc<=-x)) || (x > 0 && rc && (lc || rc<=x)) || (x == 0 && lc && rc)) puts("YES");
    else puts("NO");
}

B. Minecraft

입력의 크기가 크지 않기 때문에, 직접 시뮬레이션을 해 봐도 된다. 실제로 격자판을 만들고, $H_{j,k} = R_{i, k} = C_{i, j} = 1$인 모든 $(i, j, k)$를 채워주자. 이제 이 해가 문제의 입력 조건을 만족하는지를 보면 된다. 생각을 더 하면 $O(n^2)$에 푸는 것이 가능할 것 같은데, 굳이 그렇게 하지는 않았다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
int A[102][102], B[102][102], C[102][102];
int board[102][102][102];

void imp(){
    puts("NO");
    exit(0);
}

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) scanf("%1d", &A[i][j]);
    for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) scanf("%1d", &B[i][j]);
    for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) scanf("%1d", &C[i][j]);
    for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) for(int k=1; k<=n; k++){
        if(A[j][k] && B[i][k] && C[i][j]) board[i][j][k] = 1;
    }
    for(int i=1; i<=n; i++) for(int j=1; j<=n; j++){
        bool a = 0;
        for(int k=1; k<=n; k++) a |= board[k][i][j];
        if(a != A[i][j]) imp();
        bool b = 0;
        for(int k=1; k<=n; k++) b |= board[i][k][j];
        if(b != B[i][j]) imp();
        bool c = 0;
        for(int k=1; k<=n; k++) c |= board[i][j][k];
        if(c != C[i][j]) imp();
    }
    puts("YES");
    for(int i=1; i<=n; i++) for(int j=1; j<=n; j++){
        for(int k=1; k<=n; k++) printf("%d", board[i][j][k]);
        puts("");
    }
}

C. Wiring

잘 생각해 보면, $N$단계가지 반복할 때 연결한 철사의 번호는 $\frac{N(N-1)}{2} \bmod N$이 되어 있을 것이다. $2N$단계까지 반복하면 철사의 번호는 $N(N-1) \bmod N = 0$이 되어 있을 것이다. 따라서 앞 $2N$단계까지만 고려하면 된다.

 

$2N$단계까지 중에서 철사의 길이가 $0$인 것을 빼면 총 $2(N-1)$개의 유효한 철사가 남는다. 이제 답이 만약 이것보다 작다면, 그 이유는 철사를 연결하는 여러 가지 방법이 겹쳤기 때문이다. 한편 철사의 길이를 생각해 보면, 이 길이는 순서대로 $1, 2, \cdots, N-1, 1, 2, \cdots, N-1$의 형태가 된다. 그런데 $\frac{N}{2}$를 기준으로는 길이를 짧은 쪽으로 생각할 수도 있기 때문에, 여기까지 고려하면 $N$의 홀짝성에 따라,

• $N$이 홀수인 경우: $1, 2, \cdots, \frac{N-1}{2}, \frac{N-1}{2}, \cdots, 2, 1, 2, \cdots, \frac{N-1}{2}, \frac{N-1}{2}, \cdots, 2, 1$
• $N$이 짝수인 경우: $1, 2, \cdots, \frac{N}{2}-1, \frac{N}{2}, \frac{N}{2}-1, \cdots, 2, 1, 2, \cdots, \frac{N}{2}-1, \frac{N}{2}, \frac{N}{2}-1, \cdots, 2, 1$

의 형태가 된다. 여기서 $N$이 홀수인 경우 답은 무조건 $\frac{N-1}{2}$가 되는데, 그 이유는 $\frac{N-1}{2}$번 단계 이후부터는 전 단계를 그대로 밟는 것을 반복하기 때문이다. $N$이 짝수인 경우는 일단 $N-1$단계까지는 정상적으로 진행하고, 그 이후 $\frac{N(N-1)}{2} \bmod N$에 도착한다. 이 값은 무조건 $\frac{N}{2}$이고, 여기서 다시 역방향으로 진행하므로 답은 $N-1$이 된다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll n;

int main(){
    cin >> n;
    if(n&1) cout << (n-1)/2;
    else cout << n-1;
}

D. Barking Dogs!

문제를 정리해 보면 다음과 같다.

• 총 $D$마리의 개가 있고, 시간 $0$에는 $1$번 개가 짖는다.
• $i$번 개는 시간 $t$에 잠, 기다림, 짖음 셋 중 하나의 상태이다.
  • 어떤 개 $i$가 짖을 때, 다른 개 $j$가 들을 수 있음을 나타내는 $F$쌍의 $(i, j)$ 관계가 있다.
  • 만약 시간 $t$에 $i$번 개가 자고 있는데 다른 개가 짖는 것을 듣는다면, 이 개는 시간 $t+1$부터 $t+w_i-1$까지 기다리고, $t+w_i$에 짖은 뒤 $t+w_i+1$부터 다시 잔다.
  • $i$번 개가 기다림 상태이거나 짖음 상태인 동안 다른 개가 짖는 것은 영향을 주지 않는다.
• 시간 $T$까지 각 개가 짖은 횟수를 구해야 한다.

저걸 그냥 나이브하게 시뮬레이션해도 $O(FT)$이기 때문에, 그냥 해 주면 된다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int INF = 1e9;

int n, m, T;
int w[1002];
vector<int> link[1002];
int nxtBark[1002];
int ans[1002];

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d", &w[i]);
    scanf("%d", &m);
    for(int i=1; i<=m; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        link[x].push_back(y);
    }
    scanf("%d", &T);

    nxtBark[1] = 0;
    for(int i=2; i<=n; i++) nxtBark[i] = INF;

    for(int t=0; t<=T; t++){
        for(int i=1; i<=n; i++){
            if(nxtBark[i] != t) continue;
            ans[i]++;
            for(int j: link[i]){
                if(nxtBark[j] == INF) nxtBark[j] = t+w[j];
            }
        }
        for(int i=1; i<=n; i++){
            if(nxtBark[i] == t) nxtBark[i] = INF;
        }
    }

    for(int i=1; i<=n; i++) printf("%d\n", ans[i]);
}

E. 문자열 압축하기

구간 병합 DP와 비슷한 방식으로 풀면 된다. 다음과 같은 상황을 고려하면 된다.

• $DP[i][j] = \min_{i \le k < j} (DP[i][k] + DP[k+1][j])$
• 단, $[i, j]$ 구간이 어떤 부분구간 $[i, k]$를 특정 횟수만큼 반복한 경우를 고려해 준다. $i \le k < j$에 대해 $k-i+1$이 $j-i+1$의 약수이고, $S[i \dots j]$가 $S[i\dots k]$를 $\frac{j-i+1}{k-i+1}$회 반복한 것이라면, $DP[i][j]$가 $DP[i][k]+2+d$가 될 수 있다. $d$는 반복 횟수의 자리수이다.

위를 그대로 구현하면 $O(N^4)$에 문제를 해결할 수 있다. 사실 모든 $k$가 다 가능한 건 아니라서 실제 시간 복잡도의 차수는 저것보다 작을 것이고, 상수도 작기 때문에 통과한다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int INF = 1e9;

inline int dig(int x){
    if(x<10) return 1;
    return dig(x/10) + 1;
}

int n;
char str[205];
int DP[205][205];

int main(){
    scanf("%s", str+1);
    n = strlen(str+1);
    for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) DP[i][j] = INF;
    for(int i=1; i<=n; i++) DP[i][i] = 1;
    for(int d=1; d<n; d++){
        for(int s=1; s+d<=n; s++){
            int e = s+d;
            for(int m=s; m<e; m++) DP[s][e] = min(DP[s][e], DP[s][m] + DP[m+1][e]);
            for(int m=s; m<e; m++){
                if((e-s+1)%(m-s+1)) continue;
                int len = m-s+1; bool good = 1;
                for(int i=s; i<=e-len; i++) if(str[i] != str[i+len]) {good = 0; break;}
                if(!good) continue;
                DP[s][e] = min(DP[s][e], DP[s][m] + 2 + dig((e-s+1) / len));
            }
        }
    }
    printf("%d", DP[1][n]);
}

F. King of Chairs

문제를 요약하면 다음과 같다.

• $N$개의 수가 있는데, $\frac{1}{2}$ 확률로 $A_i$가 되고, $\frac{1}{2}$ 확률로 $B_i$가 된다. $(A_i > B_i)$
• 수들을 적당히 재배치했을 때, inversion의 기댓값의 최댓값을 구하여라.

어떤 두 쌍 $(A, B)$와 $(C, D)$가 있다고 해 보자. $A>B$, $C>D$이다. 이때 어느 것을 더 앞에 놓는 것이 이득일까? 만약 $A>C$라면, $(A, B)$를 항상 앞에 놓는 것이 이득이다. 그 이유는,

• 만약 $B \ge D$라면, 당연히도 더 큰 수를 앞에 놓는 것이 inversion이 최적이므로 $(A, B)$를 놓는 것이 이득이고,
• 만약 $B<D$라면, 어느 쪽을 앞에 놓아도 두 수 사이 inversion이 생길 확률이 $\frac{1}{2}$이므로 상관이 없다.

마찬가지로, $A=C$라면 $B>D$인 경우 전자를, $B<D$인 경우 후자를 앞에 놓는 것이 이득이다. 따라서 최적의 배치는 $A$가 큰 순서, 만약 $A$가 같다면 $B$가 큰 순서이다. 이대로 정렬을 해둔 뒤 실제로 inversion이 생기는 경우의 수를 모두 더하고 $4$로 나누어주면 문제를 풀 수 있다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
pair<int, int> arr[3002];
double ans;

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d %d", &arr[i].second, &arr[i].first);
    sort(arr+1, arr+n+1);
    reverse(arr+1, arr+n+1);
    for(int i=1; i<=n; i++){
        for(int j=i+1; j<=n; j++){
            ans += arr[i].first > arr[j].first;
            ans += arr[i].second > arr[j].first;
            ans += arr[i].first > arr[j].second;
            ans += arr[i].second > arr[j].second;
        }
    }
    printf("%.4f", ans/4);
}

G. Hrvati

트리에서 정점이 하나씩 색칠될 때, 색칠되어 있는 노드 또는 색칠된 노드의 자식 노드가 총 몇 개인지 구해야 한다.

 

노드가 입력으로 하나씩 들어올 때, 아직 제거된 노드가 아니라면 단순히 DFS로 밑의 노드들을 전부 제거해 주고, 제거한 노드에 체크를 해 준다. 한 노드가 체크되는 횟수가 최대 $1$번이므로 전체 문제를 $O(N)$에 해결할 수 있다.

 

처음에 P4가 매겨져 있었는데, ETT를 사용해서 풀어서 그런 것 같다. 더 쉬운 풀이가 있으므로, 실제 난이도는 골드 정도로 추정된다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, q;
vector<int> link[200002];
bool chk[200002];
int ans;

void dfs(int x){
    chk[x] = 1, ans++;
    for(int y: link[x]){
        if(!chk[y]) dfs(y);
    }
}

int main(){
    scanf("%d %d", &n, &q);
    for(int i=1; i<n; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        link[x].push_back(y);
    }
    while(q--){
        int x;
        scanf("%d", &x);
        if(!chk[x]) dfs(x);
        printf("%d\n", ans);
    }
}

H. 도시 계획

먼저 SCC를 구하고, 같은 SCC 내에 있는 정점들은 최소 개수의 간선으로 연결하기 위해 큰 사이클 하나를 만든다. 이후 SCC를 기준으로 위상 정렬을 하고 SCC끼리 최소 간선으로 묶는 방법을 찾아야 한다.

 

편의상 위상 정렬한 뒤의 순서로 각 SCC에 번호에 붙이자. 만약 $i$번 SCC에서 $j$번 SCC까지 이동하는 방법이 $i \rightarrow j$ 간선을 타는 것 이외에 없다면, 간선을 추가한다. 이 과정을 모든 $(i, j)$ 쌍에 대해 반복하면 문제를 풀 수 있다. 다만 시간복잡도가 $O(N^3)$이 되는데, TC 개수가 많아서 시간 초과가 난다.

 

$O(N^2)$에 문제를 해결하기 위해서는 위 판별을 $i$별로 한꺼번에 해 주면 된다. 관건은 $(i, j)$ 쌍에 대해 통행하는 방법이 $(i, j)$ edge를 이용하는 한 가지뿐인지를 찾는 것인데, 이것은 $i$에서 dfs를 시작해 각 $j$별로 최대 두 번까지 방문하도록 DFS를 짤 때, 방법이 1가지였는지 2가지였는지를 보면 된다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int t;
int n;
int edge[302][302];
bool visited[302];

vector<int> vec;

void sccDfs1(int x){
    visited[x] = 1;
    for(int y=1; y<=n; y++){
        if(!edge[x][y] || visited[y]) continue;
        sccDfs1(y);
    }
    vec.push_back(x);
}

int sccNum[302], sccCnt;
vector<int> sccList[302];
int sccEdge[302][302];

void sccDfs2(int x, int g){
    visited[x] = 1, sccNum[x] = g;
    sccList[g].push_back(x);
    for(int y=1; y<=n; y++){
        if(!edge[y][x] || visited[y]) continue;
        sccDfs2(y, g);
    }
}

int cnt[302];

void dfs(int x){
    cnt[x]++;
    for(int y=1; y<=sccCnt; y++){
        if(!sccEdge[x][y] || cnt[y] >= 2) continue;
        dfs(y);
    }
}

int main(){
    scanf("%d", &t);
    while(t--){
        scanf("%d", &n);
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                scanf("%1d", &edge[i][j]);
            }
        }

        fill(visited+1, visited+n+1, 0);
        for(int i=1; i<=n; i++) if(!visited[i]) sccDfs1(i);

        fill(visited+1, visited+n+1, 0);
        sccCnt = 0;
        for(int i=1; i<=n; i++) sccList[i].clear();
        while(!vec.empty()){
            int x = vec.back(); vec.pop_back();
            if(visited[x]) continue;
            sccDfs2(x, ++sccCnt);
        }

        for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) sccEdge[i][j] = 0;

        vector<pair<int, int> > answer;
        for(int i=1; i<=n; i++) for(int j=1; j<=n; j++){
            if(!edge[i][j] || sccNum[i] == sccNum[j]) continue;
            sccEdge[sccNum[i]][sccNum[j]] = 1;
        }
        for(int i=1; i<=n; i++) for(int j=1; j<=n ;j++){
            if(sccNum[i] == sccNum[j]) continue;
            assert(sccEdge[sccNum[i]][sccNum[j]] == edge[i][j]);
        }

        for(int i=1; i<=sccCnt; i++){
            if((int)sccList[i].size() == 1) continue;
            int s = (int)sccList[i].size();
            for(int j=0; j<s; j++) answer.push_back(make_pair(sccList[i][j], sccList[i][(j+1)%s]));
        }

        for(int i=1; i<=sccCnt; i++){
            fill(cnt+1, cnt+n+1, 0);
            dfs(i);
            for(int j=1; j<=sccCnt; j++){
                if(sccEdge[i][j] && cnt[j] == 1) answer.push_back(make_pair(sccList[i][0], sccList[j][0]));
            }
        }

        printf("%d\n", (int)answer.size());
        for(auto [x, y]: answer){
            printf("%d %d\n", x, y);
        }
        puts("");
    }
}