랜덤 마라톤 · 코스 71

작성일 | In

랜덤 마라톤 결과

A. 아이그루스와 화장실

브론즈 III 브론즈 III

안뇽이는 $K$가 홀수이면 $K$층, 짝수이면 $K - 1$층으로 가면 됩니다.

인덕이는 $K$가 짝수이면 $K$층, $K = 1$이면 $2$층, 아니면 $K - 1$층으로 가면 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def solve():
    N = int(input())
    mascot = input()
    K = int(input())

    ans = 0
    if mascot == "annyong":
        if K & 1:
            ans = K
        else:
            ans = K - 1
    else:
        if ~K & 1:
            ans = K
        elif K == 1:
            ans = 2
        else:
            ans = K - 1

    print(ans)


solve()

B. 중복된 숫자

실버 V 실버 V

$1$부터 $N - 1$까지의 합에 $A$의 원소를 모두 빼면 중복되는 수와 부호가 반대인 수가 됨을 알 수 있습니다.

파이썬에서 정수들을 한 줄에 한번에 입력받으면 메모리 초과를 받으므로 sys.stdin.read를 이용해서 정수를 하나씩 읽어 메모리를 절약했습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import sys

def read_int():
    ret = 0
    c = sys.stdin.read(1)
    while not c.isspace():
        ret *= 10
        ret += ord(c) - ord("0")
        c = sys.stdin.read(1)

    return ret


N = read_int()

total = N * (N - 1) // 2

for i in range(N):
    total -= read_int()

print(-total)

C. The primes contain arbitrarily long arithmetic progressions

실버 V 실버 V

초항이 $2$고 공차가 $0$인 등차수열을 출력하면 됩니다.

1
2
n = int(input())
print("2 " * n)

D. 어두운 굴다리

실버 IV 실버 IV

가로등의 높이는 최소 $\max(x_1, N - x_M)$이어야 합니다.

임의의 두 가로등 사이에 비춰지지 않는 곳이 존재하면 안 되므로 $i = 1$부터 $N - 1$까지 $i$번째 가로등과 $i + 1$번째 가로등 사이가 모두 비춰질 때 까지 가로등을 높여줍시다.

가로등의 높이가 $N$이 되면 모두 비출 수 있으므로 가로등의 높이는 최대 $N$번 증가하고 따라서 시간 복잡도 $\mathcal{O}(N)$에 해결할 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def solve():
    N = int(input())
    M = int(input())
    x = list(map(int, input().split()))

    height = x[0]
    lightBound = x[0] + height
    for i in range(1, M):
        while lightBound < x[i] - height:
            height += 1
            lightBound += 1
        lightBound = x[i] + height

    if x[-1] + height < N:
        height = N - x[-1]

    print(height)


solve()

E. 서바이벌

실버 III 실버 III

선분들이 단순다각형을 이루려면 $s_{i + 1}$번 학생이 $s_i$번 학생에게 총을 쏘면 안 되므로 $s_i$와 $s_{i + 1}$ 사이의 거리보다 $s_{i + 1}$과 $s_{i + 2}$ 사이의 거리가 더 짧거나 같아야 합니다.

그렇다면 $s_1$와 $s_2$ 사이의 거리보다 $s_M$과 $s_1$ 사이의 거리가 더 짧거나 같아야 합니다. 만약 더 짧다면 $s_1$번 학생이 $s_2$번 학생에게 총을 쏘았다는 것에 모순되므로 모든 선분의 길이는 같아야 합니다.

그러나 거리가 같은 경우 번호가 큰 학생에게 총을 쏘아야 하므로 번호가 단조 증가/감소해야 합니다. 이때 규칙에 따라 $s_i$가 최대인 학생에게 총을 쏘는 학생이 정확하게 두 명 존재해야 하고, $s_i$가 최대인 학생은 그 두 학생 중 하나에게 총을 쏘아야 하므로 선분이 겹치게 되고 이는 각 총알의 경로가 양 끝점 이외의 다른 점에서 다른 경로와 만나지 않는다는 것과 모순입니다.

따라서 단순다각형을 이루도록 하는 입력은 존재하지 않습니다.

1
print(-1)

F. 도어맨

실버 II 실버 II

남자와 여자의 수 차이가 줄어든다면 두 번째 사람을 먼저 입장시키는 것이 이득이고, 그렇지 않으면 어떤 사람을 먼저 입장시키든 상관 없습니다.

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
WOMAN = 0
MAN = 1


def charToGender(c: str):
    if c == "W":
        return WOMAN
    else:
        return MAN


def solve():
    X = int(input())
    line = list(map(charToGender, input()))

    count = [0, 0]

    i = 0
    while i < len(line):
        now = line[i]
        i += 1

        while i < len(line) and count[line[i]] < count[line[i] ^ 1]:
            count[line[i]] += 1
            i += 1

        count[now] += 1

        if abs(count[0] - count[1]) > X:
            i -= 1
            break

    print(i)


solve()

G. 레벨 햄버거

골드 V 골드 V

레벨-$N$ 버거에 들어있는 패티의 개수를 $P_N$이라 하면 $P_N = 2P_{N - 1} + 1$입니다.

레벨-$N$ 버거의 레이어의 수를 $L_N$이라 하면 $L_N = 2L_{N - 1} + 3$입니다.

동적 계획법을 이용해서 $P_N$과 $L_N$을 전처리해 두고 재귀적으로 레이어 개수 $X$이하인 부분의 패티의 개수를 구해주면 됩니다.

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
def solve():
    N, X = map(int, input().split())

    # preprocesses powers of 2
    pattyCnt = [0] * (N + 1)
    pattyCnt[0] = 1
    for i in range(1, N + 1):
        pattyCnt[i] = pattyCnt[i - 1] << 1 | 1

    layerOfLv = [0] * (N + 1)
    layerOfLv[0] = 1
    for i in range(1, N + 1):
        layerOfLv[i] = (layerOfLv[i - 1] << 1) + 3

    def getPattyCnt(level: int, layer: int) -> int:
        if layer <= 0:
            return 0
        if level == 0:
            return 1

        ret = 0

        layer -= 1

        if layer >= layerOfLv[level - 1]:
            ret += pattyCnt[level - 1]
            layer -= layerOfLv[level - 1]
        else:
            return ret + getPattyCnt(level - 1, layer)

        if layer <= 0:
            return ret

        ret += 1
        layer -= 1

        if layer >= layerOfLv[level - 1]:
            ret += pattyCnt[level - 1]
        else:
            return ret + getPattyCnt(level - 1, layer)

        return ret

    print(getPattyCnt(N, X))


solve()

H. 그리드 게임

골드 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
31
32
33
34
35
36
37
38
39
40
41
42
43
from collections import deque


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

    queue: deque[tuple[int, int]] = deque()

    for i in range(N):
        line = input()
        for j in range(M):
            if line[j] == "o":
                queue.append((i, j))

    K = int(input())
    time = [[-1] * (M + 2 * K) for _ in range(N + 2 * K)]

    for i, j in queue:
        time[i][j] = 0

    ans = 0
    while queue:
        i, j = queue.popleft()
        ans += 1

        if time[i][j] == K:
            continue

        delta = [1, -1, 0, 0]
        for k in range(4):
            ni = i + delta[k]
            nj = j + delta[3 - k]

            if time[ni][nj] != -1:
                continue

            time[ni][nj] = time[i][j] + 1
            queue.append((ni, nj))

    print(ans)


solve()

랜덤 마라톤 · 코스 71