[ AtCoder ] AtCoder Beginner Contest 334 Upsolving

A - Christmas Present

https://atcoder.jp/contests/abc334/tasks/abc334_a

A - Christmas Present

B가 크면 Bat, G가 크면 Glove 를 출력한다. ( B와 G는 같지 않다. )

b, g = map(int, input().rstrip().split())
print('Bat' if b > g else 'Glove')

예상 티어 : Bronze 5

 

B - Christmas Trees

https://atcoder.jp/contests/abc334/tasks/abc334_b

B - Christmas Trees

L <= A + kM <= R 을 충족하는 k의 개수를 세야 한다.

몫 나눗셈으로 편하게 구하기 위해, A와 R을 L만큼 밀어서 L을 사실상 0으로 만들었다.

A 음수 제한 등을 고려하여 식을 정리하면, ((R-L)-((A-L)%M))/M+1 이라는 식을 얻을 수 있다.

import sys
input = sys.stdin.readline

a, m, l, r = map(int, input().rstrip().split())
print(((r-l)-((a-l)%m))//m + 1)

 

예상 티어 : Bronze 2

 

C - Socks 2

https://atcoder.jp/contests/abc334/tasks/abc334_c

C - Socks 2

이미 두 짝 다 있는 양말들과 짝짓는 것도 좋지만, 잃어버린 양말들끼리 짝짓어도 상관없다. 예를 들면 (1, 8) (8, 10) 이든 (1, 10) 이든 9로 똑같기 때문이다.

잃어버린 양말들을 정렬했을 때, 무조건 인접한 양말끼리 짝지어야 한다. 만약 중간을 먼저 짝지어버리면 겹치는 부분이 생겨버리기 때문에 비효율적이다.

 

K가 짝수일 때는 인접한 양말끼리 짝지으면 답을 얻을 수 있지만, 홀수일 때는 짝을 짓지 못할 양말 1개를 정해야 한다.

 

짝을 짓지 못할 양말은 홀수번째 양말 ( 1, 9, 16 ) 이어야 한다. 짝수번째 양말을 제외해버린다면 ( 6, 10 ) 짝수번째 양말을 무조건 건너서 짝을 지어야 하므로 불필요한 부분이 생겨버리기 때문에, 무조건 인접한 양말끼리 짝짓는다.

제외 후보 양말들을 처음부터 하나씩 제외해보면서 최솟값을 구한다는 느낌으로, 슬라이딩 윈도우 기법과 비슷하게 빼고 더해보면서 최솟값을 구한다.

import sys
input = sys.stdin.readline

n, k = map(int, input().rstrip().split())
arr = list(map(int, input().rstrip().split()))
arr.sort()

if k % 2 == 1:
    res = 0
    for i in range(1, k-1, 2):
        res += arr[i+1] - arr[i]
    now = res
    for i in range(2, k, 2):
        now += arr[i-1] - arr[i-2]
        now -= arr[i] - arr[i-1]

        res = min(res, now)
    
    print(res)
else:
    res = 0
    for i in range(0, k-1, 2):
        res += arr[i+1] - arr[i]
    print(res)

예상 티어 : Silver 5

 

D - Reindeer and Sleigh

https://atcoder.jp/contests/abc334/tasks/abc334_d

D - Reindeer and Sleigh

주어진 순록 마리 수로 얻을 수 있는 최대한의 썰매 개수를 구해야 하므로, 썰매를 끌 수 있는 순록 마리 수 배열을 정렬해서 누적 합 배열로 만든 뒤, 이분 탐색으로 최대한의 썰매 개수를 구한다.

import sys
input = sys.stdin.readline

n, q = map(int, input().rstrip().split())
r = list(map(int, input().rstrip().split()))
r.sort()
arr = [r[0]]
for i in range(1, n):
    arr.append(arr[-1] + r[i])

def binarySearch(now, start, end):
    mid = (start + end) // 2
    if arr[mid] <= now < arr[mid+1]:
        return mid
    if end - start == 1 and arr[mid] > now:
        return start - 1
    if end - start == 1:
        return end
    if arr[mid] < now:
        return binarySearch(now, mid, end)
    if arr[mid] > now:
        return binarySearch(now, start, mid)

for i in range(q): 
    print(binarySearch(int(input().rstrip()), 0, len(arr) - 1) + 1)

이분 탐색 연습을 많이 해야할 것 같다..

예상 티어 : Silver 3

 

E - Christmas Color Grid 1

https://atcoder.jp/contests/abc334/tasks/abc334_e

E - Christmas Color Grid 1

BFS 로 Green 영역을 그룹화시키고, Red를 Green으로 칠했을 때 어느 Green 영역과 이어지는지를 그룹 번호로 파악하여 기댓값을 구했다. 출력을 위해 빠른 제곱과 페르마 소정리에 대한 개념이 필요하다. 

import sys
from collections import deque
input = sys.stdin.readline

h, w = map(int, input().rstrip().split())
maps = [list(input().rstrip()) for _ in range(h)]
greens = [[0 for _ in range(w)] for _ in range(h)]
row = [-1, 1, 0, 0]
col = [0, 0, -1, 1]

def bfs(start_y, start_x, now):
    queue = deque()
    queue.append([start_y, start_x])
    greens[start_y][start_x] = now

    while queue:
        now_y, now_x = queue.popleft()
        for d in range(4):
            ny = now_y + row[d]
            nx = now_x + col[d]

            if 0 <= ny < h and 0 <= nx < w and maps[ny][nx] == '#' and greens[ny][nx] == 0:
                greens[ny][nx] = now
                queue.append([ny, nx])

groups = 1
for i in range(h):
    for j in range(w):
        if maps[i][j] == '#' and greens[i][j] == 0:
            bfs(i, j, groups)
            groups += 1

sums = 0
cnt = 0
for i in range(h):
    for j in range(w):
        if maps[i][j] == '.':
            cnt += 1

            S = set()
            for d in range(4):
                ny = i + row[d]
                nx = j + col[d]

                if 0 <= ny < h and 0 <= nx < w and greens[ny][nx] != 0 and greens[ny][nx] not in S:
                    S.add(greens[ny][nx])
            
            sums += groups - len(S)

def power(a, b):
    if b == 0:
        return 1
    x = power(a, b//2)
    if b % 2 == 0:
        return x * x % 998244353
    else:
        return x * x * a % 998244353

def getInv(v):
    return power(v, 998244353 - 2)

def gcd(a, b):
    if b == 0: return a
    return gcd(b, a%b)

gcdres = gcd(sums, cnt)
sums //= gcdres
cnt //= gcdres
print(sums * getInv(cnt) % 998244353)

예상 티어 : Silver 1

 

F - Christmas Present 2

 

G - Christmas Color Grid 2