랜덤 마라톤 1주차

시즌 4가 시작된 뒤 처음으로 생긴 랜덤 마라톤이다. 이번 주에 걸린 문제들은 다음과 같다.

A. He is offside!

몇 년 전에 타 OJ에서 풀었던 문제가 여기에 다시 나올 거라고는 상상도 못했다…

지문에 쓰여 있는 것을 그대로 구현하면 된다. 수비수 중 두 번째로 골문에 가까운 사람과 공격수 중 가장 골문에 가까운 사람의 거리를 비교하면 된다. 정렬을 이용하면 구현이 편해진다.

B. Brain Fold (Hard)

IPSC 문제 역시 여기서 볼 거라고 생각하지 못했다. IPSC는 따지자면 외국에서 열리는 구데기컵 같은 개념이라, 랜덤 디펜스에서 만났을 때 썩 유쾌하지는 않다. (문제 자체가 구데기라기보다는, 뭔가 상당히 애드혹적인 느낌의 문제들도 많이 출제되는 것 같다.)

 

종이접기 문제들을 어느 정도 풀어봤다면, 종이접기를 한 뒤 종이를 잘랐을 때 그 잘린 선을 원래의 종이에 그리는 것이 어렵지 않을 것이다. 대충 다음과 같은 식으로 그리면 된다. 핵심은 접힌 선을 따라 대칭시키는 것이다.

따라서, 어떻게 접었는지의 문자열에서 필요한 정보는 다음과 같다.

• 좌우 / 상하로 각각 몇 번 접었는가?
• 마지막으로 남은 칸은 위 격자에서 몇 행 몇 열의 칸인가?

위 값들은 접은 방향을 역추적하면서 구할 수 있다. 여기까지 구하고 나면, 나머지는 casework이다. 총 격자의 크기가 $H \times W$이며, 그 중 현재 칸이 $(r, c)$라고 하자. 인덱스는 $0$부터 시작한다. 다음과 같은 세 가지 케이스가 있다.

• 자른 방향이 수평 방향일 경우: 답은 $H+1$이다.
• 자른 방향이 수직 방향일 경우: 답은 $W+1$이다.
• 자른 방향이 대각선인 경우
  • 이 경우는 네 가지 조합이 있는데, 모두 대칭적이므로 편의상 방향이 LT인 경우만 보자. (그렇지 않은 경우는 $r$과 $c$를 적당히 바꿔서 계산하면 된다.) 이때는 $(r, c)$와 행, 열 모두 기우성이 같은 격자점의 개수를 세고 거기에 1을 더하면 답이 된다.

결과적으로 문제를 $O(N)$에 풀 수 있다. 다만 조심해줘야 하는 부분이 상당히 많다. 답을 mod로 저장해야 하기 때문에 제한받는 부분이 꽤 있는데, 예를 들어 $2^n$을 구한 다음 $2^{n-1}$을 구하기 위해 2로 나눈다던가 하는 부분이 불가능하다. (곱셈 역원을 쓰지 않는다면…) 잔실수를 할 부분도 굉장히 많기 때문에 조심해야 한다.

C. Сумма

이 문제는 굉장히 이상하고 더럽다. 아마 Random Defense가 아니라면 풀지 않았을 것 같다.

 

일단 주어진 문제를 보면, 세 정수 $A$, $B$, $C$ ($10^5$자리 이하)가 주어졌을 때 $10^n A + 10^m B = 10^k C$인 세 음이 아닌 정수 $(n, m, k)$가 존재하는지를 찾고, 존재한다면 출력해야 한다.

 

먼저 $A$, $B$, $C$를 $10^\alpha a$, $10^\beta b$, $10^\gamma c$꼴로 놓자. 이때 $a$, $b$, $c$는 모두 10의 배수가 아니라고 생각한다. 이제 우리는 $10^n a + 10^m b = 10^k c$인 세 음이 아닌 정수 $(n, m, k)$를 찾을 것이다. 이걸 찾으면 답을 찾는 건 쉽다. 다음과 같이 케이스워크를 할 수 있다.

• $n$과 $m$이 모두 $0$인 경우 - 그냥 해 보면 된다.
• $n$과 $m$이 모두 $0$이 아닌 경우 - 이런 경우가 존재할 수는 있지만, 두 수에서 $\min(n, m)$만큼 빼고 처리해도 같은 결과를 얻을 수 있으므로 고려해줄 필요가 없다.
• $n$이 0인 경우: $k$도 $0$이어야 한다. 이제 이 조건을 만족하는 $m$이 존재하는지를 찾아준다.
• $m$이 $0$인 경우: 위와 대칭적으로 풀면 된다.

수의 크기가 크기 때문에 Python으로 짜는 게 편하다. 여러 가지 판별을 하는 도중에 시간 초과가 나기 쉽고, 조심해야 할 부분도 많다. 내가 작성한 코드를 함께 첨부한다.

def decode(x):
    s = str(x)
    cnt = 0
    while cnt < len(s) and s[len(s) - cnt - 1] == '0':
        cnt += 1
    return (cnt, int(s[:len(s)-cnt]))

INF = 500000
A = int(input())
B = int(input())
C = int(input())

alpha, a = decode(A)
beta, b = decode(B)
gamma, c = decode(C)

def good(orig, small):
    if orig <= 0:
        return -1
    sa = str(orig)
    sb = str(small)
    if len(sa) < len(sb):
        return -1
    score = len(sa) - len(sb)
    sb += '0' * score
    if sa != sb:
        return -1
    return score

# n = m = 0
val = good(a+b, c)
if val != -1:
    print('YES')
    print(INF-alpha, INF-beta, INF-gamma+val)
    exit()

# n = 0
val = good(c-a, b)
if val != -1:
    print('YES')
    print(INF-alpha, INF-beta+val, INF-gamma)
    exit()

# m=0
val = good(c-b, a)
if val != -1:
    print('YES')
    print(INF-alpha+val, INF-beta, INF-gamma)
    exit()

print('NO')

D. 팰린드롬 만들기

typical한 DP 문제이다. 대략적인 발상 과정은 다음과 같다.

• 버려야 하는 카드 수의 최솟값을 찾는 것은, 팰린드롬의 최장 길이를 찾는 것과 같다.
• 문제에 등장할 수 있는 모든 팰린드롬의 길이는 홀수이다. 모든 $i$에 대해, $arr_i$가 중심이 되는 팰린드롬의 최장 길이를 $O(N^2)$에 찾아 보자.
• $DP[l][r]$을 다음과 같이 정의하자: $arr$의 $[1, l]$ 구간에서 적당히 수들을 뽑았을 때, $arr$의 $[r, N]$ 구간에서 수들을 적당히 뽑은 것의 reverse가 될 수 있는 최장 길이 수열의 길이.
  • 즉, $arr = { 1, 3, 2, 4, 2, 1, 3, 1 }$이고, $l = 3$, $r = 6$이라면, $[1, 3]$ 구간에 해당하는 수들 ${ 1, 3, 2}$에서 첫 번째와 두 번째 수를 뽑아 배열 ${1, 3}$을 만들면 이는 $[6, 8]$ 구간에 해당하는 수들 ${1, 3, 1}$에서 뽑은 마지막 두 수 ${3, 1}$과 reverse가 된다. 따라서 $DP[3][6] = 2$가 될 것이다.
  • $DP[l][r]$은 다음 세 값의 최댓값이다.
    • $DP[l-1][r]$
    • $DP[l][r+1]$
    • 만약 $arr[l] = arr[r]$인 경우 $DP[l-1][r+1] + 1$. 그렇지 않다면, 이 값은 무시한다.
• $DP[i][i]$를 통해 $i$를 중심으로 하는 팰린드롬의 최장 길이를 알 수 있다. 정확히는, 팰린드롬의 최장 길이는 $2 \times DP[i][i] - 1$이다. 이 값을 모두 전처리해 두었다면, 나중에 쿼리에 대한 답은 $n - (2 \times DP[i][i] - 1)$을 출력하는 것으로 가능하다.

따라서 문제를 $O(N^2)$에 해결할 수 있다.

E. Olympic Goodies

트리가 주어지고, 간선 위에 총 $P$개의 물품을 놓을 때, 한 경로 위에 있는 물품의 합의 최댓값을 최소화시키는 문제이다.

 

모든 물품을 리프 노드와 연결된 간선에 놓는 것이 최적이라는 것을 알 수 있다. 만약 이 사실을 그냥 믿는다면, 리프 노드의 개수를 센 뒤에 최대한 균일하게 분배하고, 가장 많이 놓인 두 간선의 개수 합이 답이 될 것이다. 리프 노드와 연결된 간선으로 놓는 게 항상 최적이라는 직관은 대략적으로 다음과 같이 얻을 수 있다.

• 만약 리프 노드가 아닌 어떤 간선 $(A, B)$에 물품을 놓는다면, 이것은 $A$의 서브트리 내의 경로나 $B$의 서브트리 내 경로 안에 이 물품이 포함되는 것을 막기 위함일 것이다.
• 만약 양쪽 중 한쪽 서브트리에 아직 여유가 있다면, 이쪽 서브트리로 물품을 보내도 상관없다.
• 만약 양쪽 서브트리에 모두 여유가 없다면, $A$쪽 서브트리의 리프 노드 하나와 $B$쪽 서브트리의 리프 노드 하나를 선택하는 경로 역시 최댓값일 것이므로, 이 간선에 물품을 놓을 이유가 사라진다.

F. 회전 미로

BFS를 해주면 된다. 시간에 따라 각 칸이 어디로 가는지, 그리고 각 위치에 있는 칸이 어딘지를 전처리해 줘야 한다. 구현이 더럽다.

G. Ant Colony

anteater가 파고 들어간 간선을 기준으로, 양쪽 서브트리에서 DFS를 한다. DFS를 하면서, 현재 간선에 어떤 범위의 개미들이 들어와야 anteater가 먹게 되는지를 세면 된다. 이 수가 $10^9$ 이상으로 커지게 되면 오버플로우를 방지하기 위해 중단해 줘야 한다. 리프 노드에 도달하면, 해당 범위 안에 있는 군집의 수를 세면 된다. 이것은 군집에 있는 개미들의 수를 사전에 정렬해 놓고, 이분 탐색으로 찾으면 된다.

시간 복잡도는 $O(N \log G)$이다.

H. Electricity

그래프가 주어졌을 때, 한 정점을 제거하고 나서 남는 최대 연결성분 수를 세는 문제이다. 그래프에 간선이 하나도 없다면 답은 $n-1$이다. 그렇지 않다면, 단절점을 구하는 DFS와 비슷한 걸 돌리면서, 각 정점별로 자신 아래의 연결성분 중 자신보다 낮은 깊이로 되돌아갈 수 없는 것의 개수를 세면 된다. 이렇게 하면 각 정점을 끊었을 때 몇 개의 컴포넌트가 추가로 생기는지 구할 수 있고, 문제를 해결할 수 있다.

시간 복잡도는 테스트 케이스당 $O(V+E)$이다.