Codeforces Round #546 (Div. 2) A ~ C

codeforces.com/contest/1136

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

풀은 문제:A, B, C

못 풀은 문제: D, E

풀이만 보고 풀은 문제:

코드와 풀이를 보고 풀은 문제:

난이도

A - 800

B - 1000

C - 1500

D - 1800

E - 2200

 

 

C번 아이디어를 뒤늦게 생각해내서 아쉽

 

 

 

 

A. Nastya Is Reading a Book

 

챕터가 몇장부터 몇장까지 있는지 입력값에서 보여주고, 읽어야할 남은 챕터가 몇인지 구해야한다.

주의할 점은 입력값이 k이면 k-1쪽까지 읽었다는 것이다.

 

def main():
    n = int(input())
    D = [[*map(int,input().split())] for _ in range(n)]
    k = int(input())
    for i in range(n):
        if D[i][0] <= k <= D[i][1]:
            z = i
    print(n-z)

 

 

B. Nastya Is Playing Computer Games

 

두번째 예제에서 Nastya가 처음 위치에서 이동할 수 있는 방향은 왼쪽, 오른쪽으로 나뉠 수 있다.

 

먼저 왼쪽으로 쭉 이동하면서 동전을 주운다음 오른쪽으로 쭉 이동하면서 동전을 주우면 답이 나오고, 오른쪽으로 쭉 이동하면서 동전을 주운다음 오른쪽으로 쭉 이동하면서 동전을 주우면 값이 답보다 큰 것을 알 수 있다.

그러므로 k/2의 몫이 오른쪽 끝이랑 가까우면 오른쪽으로 갔다가 왼쪽으로 가고, k/2의 몫이 왼쪽 끝이랑 가까우면 왼쪽으로 갔다가 오른쪽으로 가면 된다.

이걸 시뮬레이션으로 구현하면 된다.

 

두가지 경우를 나누어서 풀어주면 된다.

에디토리얼에서는 이것을 공식으로 푸는데 답이 (2*n + 1) + (n - 1) + min(k - 1, n - k) 라고 한다.

2*n + 1은 모든 돌을 옆으로 치워야하므로 n, 딱 한번은 돌을 두 개를 치워야하므로 1을 추가, 맨홀에서 동전을 가져가야하므로 n으로 2*n + 1이 나온다.

n - 1은 왼쪽 끝에서 오른쪽 끝, 혹은 오른쪽 끝에서 왼쪽 끝으로 가는데 걸리는 시간 n - 1이다.

min(k - 1, n - k)는 위에 시뮬레이션 풀이에 나와있듯이 가까운 곳으로 이동하는데 걸리는 시간이다.

 

def main():
    n, k = map(int,input().split())
    stone = [1]*n
    ans = 0
    if k > n//2:
        k-=1
        stone[k] = 0
        stone[k-1] += 1
        ans = 2
        for i in range(k+1,n):
            ans += 1
            ans += stone[i]
            stone[i-1] += stone[i]
            stone[i] = 0
            ans += 1
        ans += n-k
        for i in range(k-1,-1,-1):
            ans+=1
            ans += stone[i]
            stone[i+1] += stone[i]
            stone[i] = 0
            ans += 1
        print(ans-1)
    else:
        k-=1
        stone[k] = 0
        stone[k+1] += 1
        ans = 2
        for i in range(k-1,-1,-1):
            ans+=1
            ans += stone[i]
            stone[i+1] += stone[i]
            stone[i] = 0
            ans += 1
        ans += k
        for i in range(k+1,n):
            ans += 1
            ans += stone[i]
            stone[i - 1] += stone[i]
            stone[i] = 0
            ans += 1
        print(ans)

 

 

C. Nastya Is Transposing Matrices

 

이 문제의 핵심 아이디어는 전치행렬을 이용하여 행렬의 값들을 바꿀 수 있는 곳을 살펴보면 /모양처럼 대각선에 있는 숫자들 끼리만 서로 바꿀 수 있다는 점이다.

 

그래서 이렇게 배열 A에 빨간선에 해당하는 숫자들끼리 배열을 만들고, 똑같이 배열 B에 해당하는 부분도 만들어서 서로 각각의 빨간선 위치에 들어있는 숫자들이 똑같은지 확인해주면 된다.

빨간선은 n+m-1개가 나온다.

 

코드는 위에서 설명한 것처럼 n+m-1개의 배열 2개를 만들어서 서로 비교하거나

파이썬은 defaultdict를 이용하여 배열A의 빨간선에 있는 숫자가 보일때마다 +1씩 해주고, 그다음 for문을 이용하여 B행렬의 빨간선 안에 있는 값이 A행렬의 빨간선 안에 있는 값과 똑같을때마다 해당값을 -1씩 빼준다. 그다음 defaultdict의 값이 전부 0인지만 확인해주면 된다.

 

def main():
    n,m = map(int,input().split())
    A = [[*map(int,input().split())] for _ in range(n)]
    B = [[*map(int,input().split())] for _ in range(n)]
    visit = [defaultdict(lambda:0) for _ in range(n+m-1)]
    for i in range(m):
        x,y = 0,i
        while 1:
            if 0<=x<n and 0<=y<m:
                visit[i][A[x][y]]+=1
                x+=1;y-=1
            else:break
    for i in range(1,n):
        x,y = i,m-1
        while 1:
            if 0<=x<n and 0<=y<m:
                visit[i+m-1][A[x][y]]+=1
                x+=1;y-=1
            else:break
    for i in range(m):
        x,y = 0,i
        while 1:
            if 0<=x<n and 0<=y<m:
                visit[i][B[x][y]]-=1
                x+=1;y-=1
            else:break
    for i in range(1,n):
        x,y = i,m-1
        while 1:
            if 0<=x<n and 0<=y<m:
                visit[i+m-1][B[x][y]]-=1
                x+=1;y-=1
            else:break
    flag = True
    for i in range(n+m-1):
        for x in visit[i].keys():
            if visit[i][x] != 0: flag = False
    if flag:print('YES')
    else:print('NO')

 

 

D. Nastya Is Buying Lunch

 

내일 일어나서 풀을 예정