2022 경인지역 6개 대학 연합 프로그래밍 경시대회 shake!

작년에 이어 올해도 출전할 수 있었다.

출제진이나 스태프가 되지 않는 이상 아마 매년 출전하지 않을까 싶다.

 

작년에 비해 실력의 최댓값은 크게 늘지 않았지만 평균값은 크게 늘었다고 자부했다.

코딩 테스트 합격을 위해서는 플래티넘 문제를 풀 필요가 없다. 시간제한 안에 골드3 수준의 문제만 무조건 맞출 수 있다면 대부분 합격 하고도 남을 것이다. 그래서 그 부분을 중점적으로 공부했던 것 같다.

 

수상을 위해서는 2022년 1학기라도 다녔어야 하지만 군대이슈로 인해 22년에는 학교를 다니지 않았어서 어차피 수상권에 들어도 수상을 못하기 때문에 굉장히 가벼운 마음으로 임했다.

 

역시 A번 부터 그리 간단한 문제는 아니였던 것 같다. 10분 가까이 잡아먹고 2번 정도 틀렸던 것 같다.

사실 맨 처음 생각한대로 그냥 log를 이용해서 풀어주면 되는 문제였지만 뇌절로 인한 이슈가 생각보다 컸다.

 

https://www.acmicpc.net/problem/27724

from sys import stdin
from math import log2
input=stdin.readline

n,m,k=map(int,input().split())
arr=[i+1 for i in range(n)]
wcnt=0
mx=-1
while n:
    mx+=1
    n//=2
print(min(int(log2(k))+m,mx))

 

B번은 보자마자 읽기가 굉장히 싫었지만 그렇게 어려운 문제는 아니였다.

늘 그렇듯 소수의 개수는 그리 많지가 않고, 제곱의 힘은 굉장히 강력하다.

 

https://www.acmicpc.net/problem/27725

from sys import stdin
from copy import deepcopy
input=stdin.readline

n=int(input())
p=sorted(map(int,input().split()))
k=int(input())
cnt=0
np=deepcopy(p)
dep=0
while True:
    nnp=[]
    dep+=1
    for i in range(len(np)):
        cnt+=k//np[i]
        if np[i]*p[i]<k:
            nnp.append(np[i]*p[i])
    np=deepcopy(nnp)
    if not nnp:
        break
print(cnt)

 

C번 문제는 풀고나서 보면 굉장히 쉬운 문제지만 대회 당시에는 왜 이렇게 어려웠었는지 모르겠다.

m1,m2,m3 순으로 튜플을 만들어서 딕셔너리의 키값으로 이용해주면 된다.

증명은 못했지만 생각보다 경우의 수가 굉장히 적었다.

 

https://www.acmicpc.net/problem/27726

from sys import stdin
from collections import defaultdict as dd
input=stdin.readline

def find(x,no):
    if x==par[no][x]:
        return x
    else:
        par[no][x]=find(par[no][x],no)
        return par[no][x]

def union(a,b,no):
    a=find(a,no)
    b=find(b,no)
    if a<b:
        par[no][b]=a
    else:
        par[no][a]=b

n=int(input())
m1,m2,m3=map(int,input().split())
par=[[i for i in range(n+1)] for i in range(3)]

for i in range(m1):
    a,b=map(int,input().split())
    union(a,b,0)

for i in range(m2):
    a,b=map(int,input().split())
    union(a,b,1)

for i in range(m3):
    a,b=map(int,input().split())
    union(a,b,2)


for i in range(1,n+1):
    for j in range(3):
        find(i,j)
case=dd(list)
for i in range(1,n+1):
    key=(par[0][i],par[1][i],par[2][i])
    case[key].append(i)

ans=[]
for i in case:
    if len(case[i])>1:
        ans.append(case[i])

print(len(ans))
for i in sorted(ans):
    print(*i)

 

D번은 아직도 잘 모르겠다. 잘못된 접근을 어찌어찌 이어가면서 여러가지 예외처리를 해주면서 어거지로 맞췄다.

아이디어는 "정렬이 된 이후로 남은 k는 k//n번 만큼 더 정렬시킬 수 있다"에 집중을 해주었고, 그렇다면 맨 처음 정렬만 어찌어찌 구해주면 답을 구할 수 있을 것이라 생각했다. 그 방법으로는 이제 높이가 같은 것들끼리 합쳐주면서 천천히 올려준다는 느낌으로 구현할 수 있을 것이라 생각했는데 결국 되기는 했지만 정말 더러운 코드가 나왔다.

 

https://www.acmicpc.net/problem/27727

from sys import stdin
from collections import deque
from heapq import heappop,heappush
input=stdin.readline

# 초기 상태, k가 충분히 커서 모든 수가 같아진 상태

# 일단 무조건 다 채워서 비내림차순을 무조건 만들어주기는 해야함.

n=int(input())
arr=list(map(int,input().split()))
k=int(input())
hq=[]
ch=False
cnt=0

uns=set()
mx=-1
tos=[0]*n
for i in range(n):
    if arr[i]>=mx:
        mx=arr[i]
    else:
        tos[i]=mx
        uns.add(i)
if uns:
    fu=True
else:
    fu=False
q=deque(sorted([(arr[i],1,i) for i in range(n)]))
while k and len(q)>1:
    now,nowlen,nowidx=q.popleft()
    dif=q[0][0]-now
    if nowidx in uns:
        heappush(hq,(tos[nowidx],nowidx))
    if nowlen*(dif)<=k:
        k-=nowlen*dif
    else:
        k=0
        break
    if not uns:
        cnt+=dif
    nxt=q.popleft()
    if hq and nxt[0]>=hq[0][0]:
        _,torem=heappop(hq)
        uns.remove(torem)
        if not uns:
            cnt+=1
    q.appendleft((nxt[0],nowlen+1,nxt[2]))
if fu and len(q)==1 and cnt==0:
    uns=set()
    cnt+=1
if not uns:
    cnt+=k//n
print(cnt)

 

G번은 대회 당일에 아이디어까지는 떠올렸지만 코드까지 짜지는 못했다. 그리고 이 문제는 훈련 나가서까지 내 머릿속을 맴돌며 나를 괴롭혔다.

 

dist[now]+=dist[bef]-dist[now]-tree[bef][now]*use[now]+tree[bef][now]*(use[bef]-use[now])

 

이 점화식만 세웠는데 이 점화식을 바탕으로 dfs 1번과 O(N)번의 연산을 통해 최소가 되는 위치를 찾아줄 수 있었다.

여기까진 어찌어찌 구현했지만 정작 이어진 뒤 거리의 합을 구해지 못해서 실전에서는 못풀었던 문제이다.

 

https://www.acmicpc.net/problem/27730

from sys import stdin,setrecursionlimit
setrecursionlimit(120000)
from collections import defaultdict as dd
from collections import deque
input=stdin.readline

def solve(n):
    def getdist(now):
        use[now]=1
        for i in tree[now]:
            if vi[i]==0:
                vi[i]=1
                getdist(i)
                par[i]=now
                use[now]+=use[i]

    def getminloc():
        vi=[0]*(n+1)
        vi[1]=1
        queue=deque([])
        for i in tree[1]:
            queue.append((i,1))
        while queue:
            now,bef=queue.popleft()
            vi[now]=1
            dist[now]+=dist[bef]-dist[now]-tree[bef][now]*use[now]+tree[bef][now]*(use[bef]-use[now])
            use[now]=n
            for i in tree[now]:
                if vi[i]==0:
                    queue.append((i,now))

    tree=[dd(int) for i in range(n+1)]
    dist=[0]*(n+1)
    vi=[0]*(n+1)
    vi[1]=1
    use=[0]*(n+1)
    par=[i for i in range(n+1)]
    for i in range(n-1):
        a,b,c=map(int,input().split())
        tree[a][b]=tree[b][a]=c

    a=getdist(1)
    order=[]
    for i in range(1,n):
        order.append((use[i+1],i+1))
    order.sort()

    for usetime,now in order:
        dist[par[now]]+=tree[par[now]][now]*usetime
        dist[par[now]]+=dist[now]
        
    getminloc()
    mn=float('inf')
    mnidx=''
    for i in range(n):
        if dist[i+1]<mn:
            mn=dist[i+1]
            mnidx=i+1
    return mn,mnidx

n=int(input())
mn1,mnidx1=solve(n)
m=int(input())
mn2,mnidx2=solve(m)
print(mnidx1,mnidx2)
print(mn1*m+mn2*n+m*n)

아마 이 문제는 아는사람은 아는 웰논 문제였을 것 같다.

 

늘 그렇듯 무지성 제출 후 수정으로 인한 패널티를 굉장히 많이 받았다. 

결과는 16등으로 마무리 했지만 오랜만에 대회에 대한 욕심이 조금 생겼던 것 같다.

군인이기 때문에 캠을 켜는 코딩테스트의 경우 응시조차 불가능해서 최근에 많이 죽은 감을 되찾을 수 있던 것 같다.