2022 KOI 고등부 본선 후기

총

24 / 100 / 100 / 0

으로 224점, 가채점 결과로 34등 상위 18% 동상이 나왔다.

 

시험 양상

시작하자마자 문제들을 모두 읽었다.

1번은 트리여서 우선 넘겨놨고, 4번은 손도 못댈거같아서 치워놨다.

2번과 3번 둘다 무언가 기시감이 드는 문제였지만, 구현이 3번 먼저 생각나서 3번 먼저 코드를 짜기 시작했다.

3번은 무난하게 예외처리하고 디버깅하니 100점을 받을 수 있었다.

3번을 푼 이후 1번으로 넘어왔는데, dfs에서 벗어나지 못한 나머지 시간을 많이 날렸다.

진전이 없어 보여서 2번을 봤다.

내가 생각한 2번 해답 구현이 생각보다 어려운 문제여서 시간을 꽤 쓰고 100점을 받았다.

1번으로 돌아왔는데 dfs에서 벗어나지 못하고 어떻게든 최적화하려다가 실패하고 24점을 받게 되었다.

 

1번 - 트리 / 유니온파인드

그래프를 별로 안좋아해서 나중에 풀려고 넘겼다.

다시 돌아와서 dfs로 삽질하다가 24점밖에 못건졌다.

정해는 트리를 height 기준으로 정렬한 후, 선택된 노드 윗쪽으로 현재 값들을 더해주면 각 그룹의 크기를 구할 수 있고,

그 이후부터는 조합론을 사용하면 된다.

풀었어야하는데 못풀었다.

백준 난이도로 골드 상위- 플래 하위 나올거같다.

 

2번 - 그리디

100점 받은 코드:

import sys
import heapq
def findhalf():
    if lehea[0][0]*-1 > (a-len(ans))//2:
        return True
    else:
        return False
a = int(input())
b = list(map(int,input().split()))
things = [[] for i in range(a)]
visited = [False for i in range(a)]
ans = []
lens = {}
hea = []
lehea = []
possible = True
for i in range(a):
    heapq.heappush(things[b[i]-1],i)
for p in range(a):
    if things[p]:
        heapq.heappush(hea,[things[p][0],p])
for p in range(a):
    if (len(things[p]) > a//2 and (a-len(ans))%2 == 0) or (len(things[p]) > a//2+1 and (a-len(ans))%2 == 1):
        possible = False
        break
    if len(things[p]) > a//2:
        ans.append(heapq.heappop(things[p]))
 
    heapq.heappush(lehea,[-len(things[p]),p])
if not possible:   
    print(-1)
    sys.exit()
forbid = -1
if ans:
    forbid = b[ans[-1]]-1
while hea:
    now = heapq.heappop(hea)
    if not things[now[1]]:
        continue
    elif now[0] != things[now[1]][0]:
        if things[now[1]]:
            heapq.heappush(hea,[things[now[1]][0],now[1]])
        continue
    if ans and now[1] == b[ans[-1]]-1:
        temp = now
        flag = True
        while temp[1] == b[ans[-1]]-1 and hea:
            now = heapq.heappop(hea)
            ans.append(heapq.heappop(things[now[1]]))
            if things[now[1]]:
                heapq.heappush(hea,[things[now[1]][0],now[1]])
            visited[ans[-1]] = True
            forbid = b[ans[-1]]-1
            while True:
                if lehea[0][1] == now[1]:
                    thing = heapq.heappop(lehea)
                    heapq.heappush(lehea,[thing[0]+1,thing[1]])
                while lehea[0][0]*-1 != len(things[lehea[0][1]]):
                    thing = heapq.heappop(lehea)
                    heapq.heappush(lehea,[-len(things[thing[1]]),thing[1]])
                if not findhalf():
                    break
                else:
                    thing = heapq.heappop(lehea)
                    ans.append(heapq.heappop(things[thing[1]]))
                    heapq.heappush(lehea,[thing[0]+1,thing[1]]) 
        now = temp
    if not things[now[1]]:
        continue
    elif now[0] != things[now[1]][0]:
        heapq.heappush(hea,[things[now[1]][0],now[1]])
        continue
    ans.append(heapq.heappop(things[now[1]]))
    if things[now[1]]:
        heapq.heappush(hea,[things[now[1]][0],now[1]])
    visited[ans[-1]] = True
    forbid = b[ans[-1]]-1
    while True:
        if lehea[0][1] == now[1]:
            thing = heapq.heappop(lehea)
            heapq.heappush(lehea,[thing[0]+1,thing[1]])
        while lehea[0][0]*-1 != len(things[lehea[0][1]]):
            thing = heapq.heappop(lehea)
            heapq.heappush(lehea,[-len(things[thing[1]]),thing[1]])
        if not findhalf():
            break
        else:
            thing = heapq.heappop(lehea)
            ans.append(heapq.heappop(things[thing[1]]))
            forbid = b[ans[-1]]-1
            heapq.heappush(lehea,[thing[0]+1,thing[1]]) 
for i in range(len(ans)):
    ans[i]+=1
print(*ans)

난잡하게 pq 30만개 만들어서 풀었다.

각 숫자별로 pq를 만들고 사전순으로 먼저오는 숫자들, 무조건 지금 사용해야하는 숫자들을 pq로 따로따로 만들어서 서로서로 업데이트하고 초기화해가며 풀었다.

더 깔끔한풀이가 있을거같은데 100점 받았으면 된 것 같다.

백준 난이도는 플래 상위 - 다이아 하위까지 나올거같다.

 

3번 - 그리디

100점받은 코드

import copy,math
import sys
input = sys.stdin.readline
n = int(input())
data = sorted(list(map(int,input().split())))
curdata = copy.copy(data)
m,k = map(int,input().split())
lastpos = 0
cursum = data[0]
add = m*k  
for i in range(1,len(data)):
    while lastpos < i:
        if data[i] > curdata[lastpos] and curdata[lastpos]-data[lastpos] < m:
            value = min([m-(curdata[lastpos]-data[lastpos]),data[i]-curdata[lastpos],add,math.floor((add+cursum)/(i-lastpos))-curdata[lastpos]])
            cursum+=value
            curdata[lastpos]+=value
            add-=value
        if curdata[lastpos]-data[lastpos] == m or math.floor((add+cursum)/(i-lastpos))-curdata[lastpos] == 0:
            cursum-=curdata[lastpos]
            lastpos+=1
            continue
        break
    if i != len(data)-1:
        cursum+=curdata[i]
tlastpos = lastpos
i = len(data)-1
while lastpos < i:
    if data[i] > curdata[lastpos] and curdata[lastpos]-data[lastpos] < m:
        value = min([m-(curdata[lastpos]-data[lastpos]),data[i]-curdata[lastpos],add,math.floor((add+cursum)/(i-lastpos))-curdata[lastpos]])
        cursum+=value
        curdata[lastpos]+=value
        add-=value
    cursum-=curdata[lastpos]
    lastpos+=1 
while add:
    if curdata[tlastpos]-data[tlastpos] < m:
        value = min([m-(curdata[tlastpos]-data[tlastpos]),math.floor(add/(len(data)-tlastpos))])
        curdata[tlastpos]+=value
        add-=value
    tlastpos+=1
print(*sorted(curdata))

투 포인터를 사용하여 가장 최적의 레벨 업과 현재 사용한 레벨 업을 모두 계산하면서 풀었다.

가장 중요한 관측은 각 객체들이 레벨업 할 수 있는 최대 횟수는 항상 정해져 있다는 것인데, 평균보다 작을 떄까지 최대 횟수와 가깝게 올리면 O(NlogN)(소팅을 먼저 해야 하기 때문에) 에 풀 수 있다.

개인적으로 비슷한 유형에 문제에 익숙하였기때문에 쉽게 풀 수 있었다.

백준 난이도는 플래 상위- 다이아 하위 나올거같다.

 

4번 - 그래프? 트리 ? 

문제 보고 이건 아니다 싶어서 튀었다.

들리는 말로 난이도가 백준 기준 다이아 상위정도라는 말에 안보길 잘했다고 생각한다.