Codeforces Round 886 (Div. 4) (버츄얼) 후기

 

https://codeforces.com/contest/1850

 

 

친구들이랑 학기 중에 매주 1회씩 버추얼 돌리기로 계획,

첫 주인데 응시 도중 두명이 도망갔지만 일단 끝까지 풀었다.

 

 

div 4긴 하지만 처음으로 다 풀었다! 2년전에 div4에서도 올솔을 한적은 있지만 그때는 해시 저격으로 결국 한 문제를 틀렸었는데 이번에는 그런거 없이 다 풀었다. 

 

https://codeforces.com/contest/1850/problem/A

 

A번은 숫자 3개가 주어졌을 때 두 수의 합이 10을 넘길 수 있는지 없는지 판별하는 문제였다.

 

from sys import stdin,setrecursionlimit
input=stdin.readline
setrecursionlimit(3000)
from collections import deque,defaultdict
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right
from math import *

for _ in range(int(input())):
    a,b,c=map(int,input().split())
    if sum(sorted([a,b,c])[1:])>=10:
        print("YES")
    else:
        print("NO")

 

https://codeforces.com/contest/1850/problem/B

 

B번은 살짝 처음에는 이해하기 어려웠는데 (필요 없는 값이랑 지문이 상당히 까다로웠던) 결국 10 미만의 숫자들 중 가치가 최대가 되는 값을 찾으면 된다.

비용 / 가치 이렇게 n개가 주어지고 비용이 10 미만으로 가치가 최대가 되도록 찾아주면 되는 문제였다.

 

from sys import stdin,setrecursionlimit
input=stdin.readline
setrecursionlimit(3000)
from collections import deque,defaultdict
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right
from math import *

for _ in range(int(input())):
    n=int(input())
    ans=0
    mx=0
    for i in range(n):
        a,b=map(int,input().split())
        if a<=10:
            if mx<b:
                mx=b
                ans=i+1
    print(ans)

 

https://codeforces.com/contest/1850/problem/C

 

C는 종이에 적힌 글자 찾는 문제다! .과 글자가 주어지는다
..K....
..O....
..A....
..L....

..A....
이런 식으로 입력이 들어오면 적힌 글자를 찾는 문제다.
.은 빈칸이고 빈칸이 아닌 곳에 적혀있는 글자를 찾는 건데 방향이 고정이고 문자열이 하나밖에 없으니까 .을 모두 빼주거나 .은 스킵하고 문자열만 받아주면 된다.

 

from sys import stdin,setrecursionlimit
input=stdin.readline
setrecursionlimit(3000)
from collections import deque,defaultdict
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right
from math import *

for _ in range(int(input())):
    arr=[list(input().rstrip()) for i in range(8)]
    w=''
    for i in range(8):
        for j in range(8):
            if arr[i][j]!='.':
                w+=arr[i][j]
    print(w)

 

https://codeforces.com/contest/1850/problem/D

 

n개의 숫자들을 차이가 k 이하가 되도록 적절히 지우는 문제, 지우는 횟수의 제한은 없고 수를 지운 뒤에 원하는 순서대로 정렬할 수 있다.

 

지우는 횟수를 최소화 해야 하므로 차이가 k개인 숫자들의 그룹 중 가장 큰 그룹만 남기고 전부 지워주면 된다. 만약 가장 큰 그룹의 크기가 a고 다른 그룹의 크기가 b라면 그룹을 남기기 위해 지워야 하는 수의 개수 n-a는 항상 n-b보다 작기 때문에 가장 큰 그룹을 제외한 다른 그룹을 지우는 것은 손해이다. 따라서 가장 큰 그룹의 개수를 구하고 n에서 빼주면 된다.

 

from sys import stdin,setrecursionlimit
input=stdin.readline
setrecursionlimit(3000)
from collections import deque,defaultdict
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right
from math import *

for _ in range(int(input())):
    n,k=map(int,input().split())
    arr=sorted(map(int,input().split()))
    st=[arr[0]]
    group=[]
    for i in range(1,n):
        dif=abs(st[-1]-arr[i])
        if dif>k:
            group.append(len(st))
            st=[arr[i]]
        else:
            st.append(arr[i])
    if st:
        group.append(len(st))
    print(n-max(group))

 

https://codeforces.com/contest/1850/problem/E

 

이처럼 생긴 액자가 주어지는데 사진의 크기 + 틀의 크기가 액자의 크기이다. 사진의 크기와 액자의 크기의 총합이 주어졌을 때 틀의 크기를 구하는 문제인데, 숫자 제한을 살펴보면 틀의 크기를 1부터 늘려가면서 하기에는 무리가 있으므로 매개변수탐색을 활용하여 구해줄 수 있다.

 

low를 0 high를 10억으로 잡고 탐색해주면 넉넉하게 해결할 수 있다.

 

from sys import stdin,setrecursionlimit
input=stdin.readline
setrecursionlimit(3000)
from collections import deque,defaultdict
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right
from math import *

for _ in range(int(input())):
    n,c=map(int,input().split())
    arr=list(map(int,input().split()))
    low=0
    high=10**9
    while low<high:
        mid=(low+high)//2
        s=0
        for i in arr:
            s+=(i+2*mid)**2
        if s<c:
            low=mid+1
        elif s==c:
            break
        else:
            high=mid
    print(mid)

 

https://codeforces.com/contest/1850/problem/F

 

숫자 n개가 주어지고 숫자 1~n까지 숫자 중에 주어진 숫자들의 배수 중 가장 많이 중복되는 수를 찾는 문제다(?)

예를 들어 n이 7이고 1 2 2 3 3 4 9 라면 정답은 1~7 사이의 숫자가 될 수 있고, 6이 2,2,3,3의 배수이므로 정답은 6이다.

 

에라토스테네스의 채를 활용하여 이 문제를 해결 할 수 있는데, 일반적으로 돌아가는 에라토스테네스의 채는 소수를 true로 잡았다면 소수 i에 대해 i+i부터 n까지 i만큼 증가시켜서 케이스를 지워나가는데 여기서는 입력받은 수를 i로 해서 시작한다고 생각하면 된다. 말이 조금 어려운데 코드로 보면 조금은 쉽다.

from sys import stdin,setrecursionlimit
input=stdin.readline
setrecursionlimit(3000)
from collections import deque,defaultdict
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right
from math import *


for _ in range(int(input())):
    n=int(input())
    arr=list(map(int,input().split()))
    real=[0]*(n+1)
    for i in arr:
        if i<=n:
            real[i]+=1
    ans=[0]*(n+1)
    for i in range(1,n+1):
        if real[i]:
            for j in range(i,n+1,i):
                ans[j]+=real[i]

    print(max(ans))

 

https://codeforces.com/contest/1850/problem/G

 

기하학 문제였는데

위 사진처럼 8방향에 관계에 놓인 그룹들을 구하는 문제이다.

n이 커서 nlogn 이내로 구해야 하는데 N,S 방향의 경우 X가 같은 경우로 쉽게 묶을 수 있고, W,E도 Y가 같은 경우로 쉽게 묶을 수 있다. NE와 SW, NW와 SE는 내가 수학을 못해서 한참 고민했지만 X-Y가 같거나 X+Y가 같은 경우로 묶어주면 된다.

각각을 전부 구해준 뒤 그룹끼리 묶어주면 해결 할 수 있다.

맨 처음 딕셔너리를 사용했다가 역시나 터져버렸다. 그냥 정렬 후 묶어주는 방식으로 바꿔주었다.

from sys import stdin
input=stdin.readline

def getcnt(arr):
    cnt=0
    bef='s'
    c=0
    for i in arr:
        if bef!=i:
            cnt+=c*(c-1)
            bef=i
            c=1
        else:
            c+=1
    if c>1:
        cnt+=c*(c-1)
    return cnt


for _ in range(int(input())):
    n=int(input())
    ddx=[]
    ddy=[]
    ddd=[]
    ddr=[]
    ans=0

    for i in range(n):
        a,b=map(int,input().split())
        ddx.append(a)
        ddy.append(b)
        ddd.append(a-b)
        ddr.append(a+b)

    ddx.sort();ddr.sort();ddd.sort();ddy.sort()
    ans+=getcnt(ddx)
    ans+=getcnt(ddy)
    ans+=getcnt(ddd)
    ans+=getcnt(ddr)

    print(ans)

 

https://codeforces.com/contest/1850/problem/H

 

지점간 연결 관계가 주어지는데 특이하게 X축 하나에서의 관계이다.

예를 들어
1 2 3
2 3 -1
이라는 관계가 주어진다면

x축 <--...--1-32--...-->

이렇게 되는 건데 +3은 오른쪽 3칸 옆에 있다, -1은 왼쪽 한칸 옆에 있다. 이렇게 주어지는 것이다.

이렇게 관계가 주어질 때 해당 관계를 만족하도록 배치할 수 있는지 판별하는 문제이다.

 

만약 2 3 1, 3 2 -2 이런 관계가 존재한다면 불가능한 관계인 것이다. 3은 2의한칸 오른쪽인 동시에 2칸 왼쪽일 수 없다. 

 

dfs를 이용하여 해당 문제를 해결 할 수 있다.

일단 입력으로 들어온 수를 뒤집어서 관계가 있는 것들을 하나의 그룹으로 묶을 수 있다. 위의 예시를 보면

1 2 3 은 2 1 -3과 같은 뜻이고, 2 3 -1은 3 2 1과 같은 뜻이다.

이렇게 뒤집은 경로도 모두 추가해주면 같은 그룹에 속해있다면 어떤 지점을 선택하더라도 같은 그룹에 속해있는 관계가 성립 되는지 직접 배치해보면서 파악할 수 있다.

DFS를 처음 시작하는 위치를 0으로 잡고, 탐색을 진행하면서 vi를 실제 위치로 초기화 해준다.

1에서 시작했다면 vi[1]=0이고, 1 2 3과 같은 관계가 존재한다면 vi[2]=3이다. 이런 식으로 탐색을 진행하다가 vi[x]가 이미 구한 값인데 위치 정보가 다르다면 불가능한 경우이다. 2 3 1, 3 2 -2 이 관계에서 처음에 vi[2]=0 vi[3]=1 이 되고, 다음 탐색에서 vi[3]에서 -2를 한 위치가 vi[2]여야 하는데 다르므로 불가능함을 구할 수 있다.

 

살짝 억울한건 또 파이썬이라 재귀로 짜면 터진다.

파이썬 지옥의 이지선다 (python으로 제출하고 시간초과 vs pypy로 제출하고 메모리 초과) 는 아니고 파이썬으로 제출해도 메모리로 터졌다.

 

종료 2분전에 후다닥 비재귀로 짜서 겨우 통과했다.

from sys import stdin, setrecursionlimit
setrecursionlimit(200000)
input = stdin.readline

def dfs(start):
    stack = [(start, 0)]
    
    while stack:
        now, current_loc = stack.pop()
        
        if vi[now] == inf:
            vi[now] = current_loc
        
        for nxt, dist in graph[now]:
            nxt_loc = current_loc + dist
            if vi[nxt] == inf:
                stack.append((nxt, nxt_loc))
            elif vi[nxt] != nxt_loc:
                return False
                
    return True

for _ in range(int(input())):
    n, m = map(int, input().split())
    inf = float('inf')
    vi = [inf] * (n + 1)
    graph = [[] for _ in range(n + 1)]
    
    for _ in range(m):
        a, b, c = map(int, input().split())
        graph[a].append((b, c))
        graph[b].append((a, -c))
    
    flag = True
    
    for i in range(1, n + 1):
        if vi[i] == inf:
            if not dfs(i):
                flag = False
                break
    
    if flag:
        print("YES")
    else:
        print("NO")

 

버추얼이긴 하지만 파이썬 억까(?)가 아니었다면 첫 퍼플퍼포가 나오지 않았을까 싶다.