Codeforces Round #533 (Div. 2) A ~ D

codeforces.com/contest/1105

Dashboard - Codeforces Round #533 (Div. 2) - Codeforces

 

풀은 문제: A, B, C

못 풀은 문제: D, E

문제 풀이만 보고 풀은 문제:

문제 풀이와 코드 둘 다 본 문제:  D

 

난이도

A - 1100

B - 1100

C - 1500

D - 1900

E - 2200

 

 

 

D번은 백준에서 BFS 문제를 많이 풀어봐서 충분히 풀 수 있던 문제였는데, 해석을 제대로 못해서 모르는 문제가 되버린게 아쉬웠다.

 

 

 

 

 

A. Salem and Sticks

 

n = 1000, a = 100이 최대이므로 바로 브루트포스를 생각해볼 수 있다.

그래서 t의 값을 for문으로 돌려서 막대기의 길이가 t보다 크면 t+1로 바꾸고, 막대기의 길이가 t보다 작으면 t-1로 바꿔줄 수 있도록 한다.

그다음 최소값을 찾아내면 된다.

 

def main():
    n = int(input())
    a = [*map(int,input().split())]
    ans = [-1,float('inf')]
    for i in range(1,101):
        z = 0
        for x in a:
            if abs(x-i) > 1:
                if x > i : z += abs(x - (i+1))
                else: z += abs(x - (i-1))
        if ans[1] > z:
            ans = [i, z]
    print(*ans)

 

 

B. Zuhair and Strings

 

이거는 알파벳 개수를 세는 배열 letters를 하나 만들고, for문을 돌려서 알파벳 번호에 해당하는 letters 배열의 위치에 값을 1씩 더해준다. 그런데 우리는 연속된 문자를 구하는 것이므로 현재 위치에 해당하는 배열을 제외한 나머지 배열의 값은 0으로 만들어주면 된다.

 

그래서 배열 letters의 알파벳 값이 k가 되면 그 배열의 값을 0으로 초기화시켜주고, ans 배열에 해당하는 알파벳 번호에 값을 1 더해주면 된다.

 

def main():
    n,k=map(int,input().split())
    s = input()
    ans = [0]*26
    letters = defaultdict(lambda: 0)
    for i in range(n):
        letters[s[i]] += 1
        for x in letters.keys():
            if letters[x] == k:
                ans[ord(x)-97] += 1
                letters[x] = 0
            if x != s[i]: letters[x] = 0
    print(max(ans))

 

 

 

 

 

C. Ayoub and Lost Array

 

경우의 수를 구하는 문제인데 백준에서 dp로 많이 본 문제 같았다.

 

일단 문제에서 더해서 3으로 나누어 떨어지는 개수를 구하는 것이니까 숫자들을 3으로 나눈 나머지의 값인 0, 1, 2으로 배열을 3개로 나누어서 개수를 셀 수 있다.

그런데 l, r의 값이 10억이기 떄문에 그냥 for문으로 돌리면 시간 초과가 나올 것이다.

그래서 적절히 잔머리를 써야하는데, 만약 l, r = 3, 6이면 나머지가 0인 값이 2, 나머지가 1인 값이 1, 나머지가 2인 값이 1이 나오고, l, r = 9, 15이면 각각 3, 2, 2개가 나올 것이다.

이것을 일반화해보자 l, r = 3*k, 3*(k+i)가 있으면 각각 i+1, i, i개가 나올 것이다.

그래서 l의 값에 -0, -1, -2를 하여 3의 배수로 만들어주고, r값에 +0, +1, +2를 하여 3의 배수로 만들어준다.

이때 -1, -2, +1, +2를 해서 3의 배수를 만든다면 해당 나머지에 해당하는 배열 값에 -1, -1, -1, -1를 해주면 된다.

 

이렇게 해서 숫자를 다 구했으면 for문으로 한 칸씩 이동하면서 값을 곱하면 된다.

만약 나머지의 값이 0, 1, 2인 숫자의 수가 각각 5개, 7개, 9개(num = [5, 7, 9])라고 가정하면

첫번째 값은 ans[0][0] = 5, ans[0][1] = 7, ans[0][2] = 9가 될 것이고

그리고 두번째 값은 첫번째 값을 보면서 적절한 값을 더해주는 방법을 사용해야한다. 그니까 두번째 값의 나머지가 0이 되려면 (첫번째 값에서 나머지가 0인 값) * (나머지가 0인 숫자의 개수) + (첫번째 값에서 나머지가 1인 값) * (나머지가 2인 숫자의 개수) + (첫번째 값에서 나머지가 2인 값) * (나머지가 1인 숫자의 개수)를 계산하면 답이 된다.

그래서 이걸 i번째로 일반화시키면

ans[i][0]은 ans[i-1][0] * num[0] + ans[i-1][1] * num[2] + ans[i-1][2] * num[1]

ans[i][1]은 ans[i-1][0] * num[1] + num[i-1][1] * num[0] + ans[i-1][2] * num[2]

ans[i][2]는 ans[i-1][0] * num[2] + num[i-1][1] * num[1] + ans[i-1][2] * num[0]

이 될 것이다.

 

모듈러 연산을 하라고 되어있으므로 여기에 모듈러 연산을 추가하면 된다.

 

def main():
    n,l,r=map(int,input().split())
    num = [0,0,0]
    x, y = 0,0
    ans = [[1]*26 for _ in range(n)]
    for i in range(3):
        x = l-i
        if i:num[x%3] -= 1
        if x%3 == 0:break
    for i in range(3):
        y = r+i
        if i:num[y%3] -= 1
        if y%3 == 0:break
    z = y//3 - x//3
    num[0] += z + 1
    num[1] += z
    num[2] += z
    ans[0] = num
    for i in range(1,n):
        ans[i][0] = ((ans[i-1][0]*num[0]) + (ans[i-1][1]*num[2]) + (ans[i-1][2]*num[1]))%MOD
        ans[i][1] = ((ans[i-1][0]*num[1]) + (ans[i-1][1]*num[0]) + (ans[i-1][2]*num[2]))%MOD
        ans[i][2] = ((ans[i-1][0]*num[2]) + (ans[i-1][1]*num[1]) + (ans[i-1][2]*num[0]))%MOD
    print(ans[n-1][0])

 

 

 

 

D. Kilani and the Game

 

땅따먹기 게임이랑 비슷한데, 살짝 다른점은 s배열에 나온 숫자만큼 모든 방향으로 움직여서 구역을 차지하면 되는 문제이다.

 

일단 한 번에 여러칸을 움직일 수 있으니 q와 new_q로 나누어서 deque 또는 queue를 이용하여 BFS를 진행하면 된다.

new_q의 역할은 한계만큼 이동하였을 때의 좌표들을 new_q에 넣고, q가 전부 비워지면 q = new_q, new_q = deque()로 업데이트하여 다음턴이 돌아올 때 이동할 수 있도록 한다.

 

큐에 들어가는 인자는 x, y, num, move인데 x,y는 좌표위치이고, num은 팀 번호, move는 지금까지 이동한 횟수이다.

아래 코드에서는 무한루프를 돌게 만들었으므로 flag라는 bool변수를 만들어서 모든 q에 원소가 들어가있지 않는다면 탈출하도록 만들어주었다.

 

코드는 48690018를 보았다.

def main():
    n, m, p = map(int,input().split())
    s = [*map(int,input().split())]
    D = [[*input()] for _ in range(n)]
    S = [[-1]*m for _ in range(n)]
    ans = [0]*p
    q=[deque() for _ in range(p)]
    new_q = [deque() for _ in range(p)]
    for i in range(n):
        for j in range(m):
            if 49<=ord(D[i][j])<=57:
                x = int(D[i][j])
                S[i][j] = x
                q[x-1].append([i,j,x,0])
                ans[x-1] += 1
    while 1:
        flag = False
        for i in range(p):
            if len(q[i]): flag = True
        if not flag: break

        for i in range(p):
            while q[i]:
                x,y,num,move = q[i].popleft()
                for j in range(4):
                    nx,ny = x+dx[j],y+dy[j]
                    if 0<=nx<n and 0<=ny<m and D[nx][ny] == '.' and S[nx][ny] ==-1 and move < s[num-1]:
                        S[nx][ny] = num
                        ans[num-1] += 1
                        if move + 1 == s[num-1]: new_q[i].append([nx,ny,num,0])
                        else:q[i].append([nx,ny,num,move+1])
            if len(new_q[i]):
                q[i] = new_q[i]
                new_q[i] = deque()
    print(*ans)