Codeforces Round 931 (Div. 2)

A. Too Min Too Max(링크)

접근 방법

수식적으로 증명하는 방법이 있으나, A인 만큼 빠르게 직관으로 접근해보았다.

4개의 숫자, a, b, c, d가 있다고 하자.

이 때, 차례로 이웃한 숫자와의 차이가 가장 크게 만들면 된다.

그렇다면 a, b, c, d를 가장 큰 수, 가장 작은 수를 반복해서 넣으면 된다는 생각으로 이어진다.

Solution

수열을 정렬한 후 a, b, c, d를 차례로 (가장 큰 수) (가장 작은 수) (두번째로 큰 수) (두번째로 작은 수)로 하여 문제에서 말하는 수식을 풀면 된다.

 

import sys

input = sys.stdin.readline
sys.setrecursionlimit(int(1e9))

T = int(input())

while T:
    T -= 1

    _ = input()
    arr = sorted(list(map(int, input().split())))

    print(
        abs(arr[0] - arr[-1])
        + abs(arr[-1] - arr[1])
        + abs(arr[1] - arr[-2])
        + abs(arr[-2] - arr[0])
    )

---

B. Yet Another Coin Proble(링크)

접근 방법

이 문제는 꽤나 고생했던 문제이다.

우선, 만약 모든 동전들이 1, 10, 100, 1000, 10000 등과 같이 금액 동전으로 항상 큰 금액 동전을 만들 수 있는 경우라면 greedy하게 큰 동전부터 최대로 사용하는 방식을 택하면 된다.

하지만, 이번 문제의 경우 동전의 금액이 1, 3, 6, 10, 15으로, 앞선 문제와는 다른 관계이다.

Solution 1. 내가 푼 방법(DP)

우선 내가 푼 방식은 어찌 됐던, 모든 동전의 최소 공배수는 30원이기 때문에, 30원은 15원이 가장 빠르게 만든다.

문제는 30으로 나눴을 때의 나머지 금액인데, 이 때는 DP를 이용하여 계산했다.

어차피 for 문 30번만 돌면 DP 값을 다 구할 수 있으므로, O(t)에 문제를 해결할 수 있다.

 

import sys

input = sys.stdin.readline
sys.setrecursionlimit(int(1e9))

T = int(input())

dp = [0] + [-1] * int(29)
for i in range(0, 30):
    if i + 1 < 30:
        if dp[i+1] == -1:
            dp[i+1] = dp[i] + 1
        else:
            dp[i+1] = min(dp[i+1], dp[i] + 1)
    if i + 3 < 30:
        if dp[i+3] == -1:
            dp[i+3] = dp[i] + 1
        else:
            dp[i+3] = min(dp[i+3], dp[i] + 1)
    if i + 6 < 30:
        if dp[i+6] == -1:
            dp[i+6] = dp[i] + 1
        else:
            dp[i+6] = min(dp[i+6], dp[i] + 1)
    if i + 10 < 30:
        if dp[i+10] == -1:
            dp[i+10] = dp[i] + 1
        else:
            dp[i+10] = min(dp[i+10], dp[i] + 1)
    if i + 15 < 30:
        if dp[i+15] == -1:
            dp[i+15] = dp[i] + 1
        else:
            dp[i+15] = min(dp[i+15], dp[i] + 1)

while T:
    T -= 1
    n = int(input())
    ans = n
    if n < 30:
        print(dp[n])
    else:
        ans = min(n // 15 + dp[n % 15], n // 15 - 1 + dp[n%15 + 15])
        print(ans)

2. Editorial 방법(Bruteforce)

Editorial에서는 좀 더 Naive한 방법을 소개하는데, 이 방식에서는 각 동전이 최대로 사용될 수 있는 개수를 한정하는 방식이다.

즉, a 동전이 b 동전이 만들 지 못하는 최대 개수까지 사용되는 것이다.

이 방식을 택하면 각 동전은 최대 다음 개수만 사용해도 된다는 것을 알 수 있다.

• 1원: 2개
• 3원: 1개
• 6원: 4개
• 10원: 2개

따라서, 총 for문 3 * 2 * 5 * 3 번 돌면서 정답을 구하면 된다.

C. Find a Mine

접근 방식

처음 풀어보는 Interactive 문제이다.

그래서인지, 매우 고생했고, 시간 안에 해결하지 못했다.

문제를 읽고 가장 먼저 발견한 직관은, 어떤 점을 기준으로 query 했을 때, 출력하는 거리는 query 한 점을 기준으로 45도 회전한 정사각형 내에 정답이 있다는 것이다.

따라서, 만약 꼭지점 중 한 곳에서 query를 한다면, 맨허튼 거리 d인 대각선 내에 정답이 존재한다는 것이다.

Solution

꼭지점 중 한 곳에서 쿼리를 먼저 한다.

이후에, 해당 대각선의 양 끝에서 쿼리를 날린 후 각 꼭지점에서 말하는 거리만큼 떨어진 대각선 위의 점을 쿼리하면 총 4번만에 찾을 수 있다.

이 때, 양 끝 점에서 쿼리를 하는 이유는 한 쪽 대각선 끝을 기준으로 대각선 위의 지뢰보다 더 가까운 지뢰가 존재할 수 있기 때문이다.

 

import sys

input = sys.stdin.readline
sys.setrecursionlimit(int(1e9))

T = int(input())

def check(x, y):
    print(f"? {x} {y}")
    sys.stdout.flush()
    dist = int(input())
    if dist == 0:
        print(f"! {x} {y}")
        sys.stdout.flush()
        return True, dist
    return False, dist


while T:
    T -= 1
    m, n = map(int, input().split())

    is_match, dist = check(1, 1)
    
    if is_match:
        continue

    dx = min(m - 1, dist)
    dy = min(n - 1, dist)

    is_match, dist1 = check(1 + dx, 1 + dist - dx)

    if is_match:
        continue

    is_match, dist2 = check(1 + dist - dy, 1 + dy)

    if is_match:
        continue

    is_match, _ = check(1 + dx - dist1//2, 1 + dist - dx + dist1//2)

    if is_match:
        continue

    print(f"! {1 + dist - dy + dist2//2} {1 + dy - dist2//2}")
    sys.stdout.flush()