랜덤 마라톤 · 코스 93

작성일 | In

랜덤 마라톤 완주

A. Scrolling Sign

실버 V 실버 V

이전 단어의 접미사와 다음 단어의 접두사가 겹치는 경우는 추가적인 문자가 필요하지 않습니다. 해당 부분만 제외하고 세주면 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def solve():
    k, w = map(int, input().split())

    ans = 0
    prev_word = ""

    for _ in range(w):
        word = input()

        overlap = 0
        for i in range(k):
            if prev_word[-i - 1 :] != word[: i + 1]:
                continue

            overlap = max(overlap, i + 1)

        prev_word = word

        ans += k - overlap

    print(ans)


def main():
    n = int(input())
    for _ in range(n):
        solve()


main()

B. Special Christmas Tree

골드 IV 골드 IV

리프 노드가 $L$개인 완전 이진 트리에서 리프 노드와 그 부모 사이에 노드를 끼워넣는 방법이 최선입니다.

리프 노드 중 깊이가 최대가 아닌 것들($2^{\lfloor \log_2 L \rfloor + 1}$개)에 먼저 노드를 끼워넣어 최대로 만들어 준 다음 나머지를 계산하면 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from math import log2, floor


def solve(case: int):
    H, L = map(int, input().split())

    answer = 2 * L - 1

    if (1 << floor(log2(L))) != L:
        answer += 2 * (1 << floor(log2(L))) - L
        H -= 1
    H -= floor(log2(L))

    answer += H * L

    print(f"Case {case}: {answer}")


def main():
    T = int(input())
    for i in range(1, T + 1):
        solve(i)


main()

C. 이분 그래프

골드 IV 골드 IV

정점마다 빨간색 혹은 파란색으로 칠해 줍시다. 임의의 정점을 빨간색으로 잡은 뒤 인접한 정점을 모두 파란색으로 칠합니다. 파란색으로 칠한 정점을 기준으로 인접한 정점을 모두 빨간색으로 칠합니다.

만약 인접한데 같은 정점인 경우가 있다면 이분 그래프가 아닙니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
import sys

sys.setrecursionlimit(10**6)

input = lambda: sys.stdin.readline().rstrip()


def solve():
    # input
    V, E = map(int, input().split())
    adj = [[] for _ in range(V + 1)]

    for _ in range(E):
        u, v = map(int, input().split())
        adj[u].append(v)
        adj[v].append(u)

    # determine whether the graph is bipartite
    def is_bipartite() -> bool:
        color = [-1] * (V + 1)
        # the colors of adjacent vertices must be different

        ret = True

        def dfs(cur: int) -> None:
            nonlocal ret

            for nxt in adj[cur]:
                if color[nxt] != -1:
                    if color[nxt] == color[cur]:
                        ret = False
                    continue

                color[nxt] = color[cur] ^ 1
                dfs(nxt)

        for i in range(1, V + 1):
            if color[i] != -1:
                continue
            color[i] = 0
            dfs(i)

        return ret

    print("YES" if is_bipartite() else "NO")


def main():
    K = int(input())
    for _ in range(K):
        solve()


main()

D. 폴리큐브의 겉넓이

골드 III 골드 III

인접한 정육면체를 간선으로 이어 컴포넌트의 개수가 1이어야 하고(연결 그래프여야 하고), 중복되는 큐브가 없으면 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
import sys

input = lambda: sys.stdin.readline().rstrip()


dx = [1, -1, 0, 0, 0, 0]
dy = [0, 0, 1, -1, 0, 0]
dz = [0, 0, 0, 0, 1, -1]


def is_invalid_coord(x: int, y: int, z: int):
    return x < 0 or y < 0 or z < 0 or x > 4 or y > 4 or z > 4


def solve():
    P = int(input())
    is_center = [[[False] * 5 for _ in range(5)] for _ in range(5)]
    coords = []

    while len(coords) < P:
        for coord_str in input().split():
            coord = tuple(map(int, coord_str.split(",")))
            coords.append(coord)

            x, y, z = coord
            if is_center[x][y][z]:
                print("NO", len(coords))
                return
            is_center[x][y][z] = True

    surface_cnt = P * 6
    visited = [[[False] * 5 for _ in range(5)] for _ in range(5)]

    def visit_component(x: int, y: int, z: int):
        nonlocal surface_cnt

        visited[x][y][z] = True

        for k in range(len(dx)):
            nx = x + dx[k]
            ny = y + dy[k]
            nz = z + dz[k]

            if is_invalid_coord(nx, ny, nz) or not is_center[nx][ny][nz]:
                continue

            surface_cnt -= 1

            if visited[nx][ny][nz]:
                continue

            visit_component(nx, ny, nz)

    visit_component(*coords[0])
    for i in range(P):
        x, y, z = coords[i]
        if not visited[x][y][z]:
            print("NO", i + 1)
            return

    print(surface_cnt)


def main():
    T = int(input())
    for _ in range(T):
        solve()


main()

E. Movers

플래티넘 V 플래티넘 V

어떤 정점 $v$와 연결된 다른 정점의 수를 $v$의 차수라고 합시다.

차수가 $\sqrt M$을 넘지 않는 정점은 인접한 정점에 바로 값을 더해 줍니다.

차수가 $\sqrt M$을 넘는 정점은 일단 자신에게만 더한 다음 2번 쿼리를 처리할 때 차수가 $\sqrt M$이상인 정점끼리 그래프를 만들어서 처리하면 됩니다.

해당 알고리즘의 시간 복잡도가 $O(Q\sqrt M)$임을 증명해 보겠습니다.

1번 쿼리의 경우 시간 복잡도가 $O(\sqrt M)$이 자명하므로 2번 쿼리에 대해서만 생각해 봅시다.

간선의 개수가 $M$이므로 모든 정점의 차수의 합은 $2M$입니다.

차수가 $\sqrt M$을 넘는 것 중 차수가 가장 큰 정점을 $v$라 하고 그 차수를 $D$라 합시다.

차수가 $\sqrt M$을 넘는 것들로만 이루어진 그래프에서 $v$와 인접한 $D$개의 정점들의 차수는 최소 $\sqrt M$입니다. 따라서 $v$, 그리고 $v$와 인접한 정점들의 차수를 모두 합하면 최소 $\sqrt M (D + 1)$ 입니다. 이는 $2M$보다 작거나 같아야 하므로 $\sqrt M (D + 1) \le 2M$, 따라서 $D < 2\sqrt M$이고 2번 쿼리를 $O(\sqrt M)$에 처리할 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
import sys

input = lambda: sys.stdin.readline().rstrip()


def main():
    N, M, Q = map(int, input().split())

    value = [0] * (N + 1)
    for i, d in enumerate(map(int, input().split()), 1):
        value[i] -= d
    for i, e in enumerate(map(int, input().split()), 1):
        value[i] += e
    added_value = [0] * (N + 1)

    rt = int(M ** (1 / 2))

    adj = [[] for _ in range(N + 1)]
    degree = [0] * (N + 1)

    for _ in range(M):
        u, v = map(int, input().split())

        adj[u].append(v)
        adj[v].append(u)

        degree[u] += 1
        degree[v] += 1

    for i in range(1, N + 1):
        adj[i].sort(key=lambda v: -degree[v])

    for i in range(1, N + 1):
        if degree[i] > rt:
            continue
        for neighbor in adj[i]:
            added_value[neighbor] += value[i]

    for _ in range(Q):
        tp, *args = input().split()

        if tp == "add":
            count = int(args[0])
            if args[1] == "desk":
                count = -count
            label = int(args[2])

            value[label] += count
            if degree[label] > rt:
                continue

            for neighbor in adj[label]:
                added_value[neighbor] += count
        else:
            label = int(args[0])

            v = value[label] + added_value[label]
            for neighbor in adj[label]:
                if degree[neighbor] <= rt:
                    break
                v += value[neighbor]

            if v < 0:
                print("desks")
            elif v > 0:
                print("monitors")
            else:
                print("same")


main()

F. Diamond Collector (Silver)

골드 I 골드 I

투 포인터 알고리즘과 DP를 이용해 구간 $(i, N]$에서 한 케이스에 담을 수 있는 다이아몬드의 개수를 구해 줍시다.

이후 앞에서부터 투 포인터 알고리즘을 이용해 구간 $[1, i]$에서 한 케이스에 담을 수 있는 다이아몬드의 개수와 $(i, N]$에서 한 케이스에 담을 수 있는 다이아몬드의 개수 합의 최댓값을 출력하면 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#define ASSERT(x) assert(x)
#else
#define ASSERT(_) ((void)0)
#endif
using namespace std;

int sz[50505];
int maxCntAfter[50505];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    cin >> N >> K;

    for (int i = 1; i <= N; i++)
        cin >> sz[i];
    sort(sz, sz + N + 1);

    int lo, hi;
    lo = hi = N;
    for (int i = N - 1; i >= 0; i--) {
        maxCntAfter[i] = maxCntAfter[i + 1];

        while (i < lo) {
            while (i < lo and sz[hi] - sz[lo] <= K)
                lo--;
            maxCntAfter[i] = max(maxCntAfter[i], hi - lo);
            if (i < lo)
                hi--;
        }
    }

    int answer = 0;
    lo = hi = 1;
    while (hi <= N) {
        while (hi <= N and sz[hi] - sz[lo] <= K) {
            hi++;
            answer = max(answer, hi - lo + maxCntAfter[hi - 1]);
        }
        lo++;
    }

    println("{}", answer);

    return 0;
}

G. 이진수 XOR

플래티넘 IV 플래티넘 IV

$DP[i][j]$를 $i$번째 수 까지만 이용해서 $j$를 만드는데 필요한 최소 xor횟수로 두고 비트필드를 이용한 다이나믹 프로그래밍으로 구해주면 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#define ASSERT(x) assert(x)
#else
#define ASSERT(_) ((void)0)
#endif
using namespace std;

constexpr int INF = 1e9;

int xorCount[111][1 << 18];
int nums[111];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int B, E;
    cin >> B >> E;

    string targetStr;
    cin >> targetStr;
    int target = stoi(targetStr, nullptr, 2);

    for (int i = 0; i < E; i++) {
        string numStr;
        cin >> numStr;
        nums[i] = stoi(numStr, nullptr, 2);
    }

    fill(&xorCount[0][0], &xorCount[E][1 << B], INF);
    xorCount[0][0] = 1;
    xorCount[0][nums[0]] = 2;

    for (int i = 1; i < E; i++) {
        xorCount[i][nums[i]] = 2;
        for (int j = 0; j < i; j++)
            xorCount[i][nums[i] ^ nums[j]] = 1;

        for (int j = 0; j < (1 << B); j++) {
            int k = j ^ nums[i];

            xorCount[i][j] = min(
                {xorCount[i][j], xorCount[i - 1][j], xorCount[i - 1][k] + 1});
        }
    }

    int answer = 0;
    int ansDiffCnt = INF;
    for (int k = 0; k < (1 << B); k++) {
        if (xorCount[E - 1][k] == INF)
            continue;

        int diffCount = 0;
        for (int i = 0; i < B; i++) {
            if ((k & (1 << i)) != (target & (1 << i)))
                diffCount++;
        }

        if (diffCount < ansDiffCnt or
            (diffCount == ansDiffCnt and
             xorCount[E - 1][k] < xorCount[E - 1][answer])) {
            answer = k;
            ansDiffCnt = diffCount;
        }
    }

    println("{}", xorCount[E - 1][answer]);
    for (int i = B - 1; i >= 0; i--) {
        if (answer & (1 << i))
            print("1");
        else
            print("0");
    }

    return 0;
}

H. Oreperations Research

플래티넘 III 플래티넘 III

$DP[i][j][k]$를 $i$번째 광차를 큐 $A$의 시작 인덱스가 $j$이고 큐 $B$의 시작 인덱스가 $k$인 상태가 되도록 하면서 광석을 전부 담을 수 있는지로 둡시다.

5중 반복문 동적 계획법을 이용해서 답을 구할 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#define ASSERT(x) assert(x)
#else
#define ASSERT(_) ((void)0)
#endif
using namespace std;

int a[55], b[55], c[111];
bool isPossibleEnd[111][55][55];

constexpr int MAX_CART = 2'000'000;
bool isComposable[2'200'000];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int r, s, n;
    cin >> r >> s >> n;

    for (int i = 1; i <= r; i++) {
        cin >> a[i];
        a[i] += a[i - 1];
    }
    for (int i = 1; i <= s; i++) {
        cin >> b[i];
        b[i] += b[i - 1];
    }
    for (int i = 1; i <= n; i++)
        cin >> c[i];

    isComposable[0] = true;
    for (int i = 0; i <= MAX_CART; i++) {
        if (i - a[r] >= 0 and isComposable[i - a[r]])
            isComposable[i] = true;
        if (i - b[s] >= 0 and isComposable[i - b[s]])
            isComposable[i] = true;
    }

    isPossibleEnd[0][1][1] = true;
    for (int i = 1; i <= n; i++) {
        for (int x = 1; x <= r; x++) {
            for (int y = 1; y <= s; y++) {
                if (not isPossibleEnd[i - 1][x][y])
                    continue;

                for (int j = 1; j <= r; j++) {
                    for (int k = 1; k <= s; k++) {
                        int sum = a[j - 1] - a[x - 1] + b[k - 1] - b[y - 1];
                        if (j < x)
                            sum += a[r];
                        if (k < y)
                            sum += b[s];

                        if (sum > c[i])
                            continue;

                        if (isComposable[c[i] - sum])
                            isPossibleEnd[i][j][k] = true;
                    }
                }
            }
        }
    }

    for (int x = 1; x <= r; x++) {
        for (int y = 1; y <= s; y++) {
            if (isPossibleEnd[n][x][y]) {
                println("Yes");
                return 0;
            }
        }
    }

    println("No");

    return 0;
}

랜덤 마라톤 · 코스 93