뭔가 계속 귀찮고, 시간이 안맞아서 이대로면 언제 다시 칠지 몰라서 조금 피곤하지만 몬스터 한캔 빨고 시작했다.
연휴를 마무리하는 기념으로 div3 응시 시작
https://codeforces.com/contest/2014
A번 문제
알고리즘 : 구현
A번 문제는 간단한 문제였다. 사람들이 가지고 있는 금화의 개수가 배열로 주어진다. 금화를 k개 이상 가지고 있는 사람에게서 금화를 모두 가져올 수 있고, 금화가 0개인 사람을 만나면 내가 금화를 가지고 있다면 금화를 준다.
이렇게 금화를 준 횟수를 구하는 문제이다.
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 *
from itertools import combinations,permutations
for _ in range(int(input())):
n,k=map(int,input().split())
have=0
arr=list(map(int,input().split()))
ans=0
for i in range(n):
if arr[i]>=k:
have+=arr[i]
elif arr[i]==0:
if have:
have-=1
ans+=1
print(ans)B번 문제
알고리즘 : 수학, 조건
n과 k가 주어진다. n-k+1 ~ n까지의 수의 총합이 짝수인지 홀수인지 판별하는 문제다.
문제에서는 제곱의 합을 구하라고 하지만 홀수의 제곱은 홀수고, 짝수의 제곱은 짝수이니 총합과 차이가 없다.
어째선지 머리가 안돌아가서 한참 해맸다.. 결국 4단위로 (홀짝홀짝) (짝홀짝홀) 패턴이 반복됨을 이용해서 풀어주었다.
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 *
from itertools import combinations,permutations
for _ in range(int(input())):
n,k=map(int,input().split())
if n%2:
if k%4==3 or k%4==0:
print("YES")
else:
print("NO")
else:
if k%4==1 or k%4==0:
print("YES")
else:
print("NO")C번 문제
알고리즘 : 매개변수탐색, 이분탐색
n명의 사람이 있고 각자 처음 돈이 ai만큼 있다. "가장 많은 돈을 가진 사람"이 x만큼의 돈을 더 얻었을 때, 전체 돈의 "평균"의 "절반" 이하가 되는 사람들의 수가 "절반"을 "넘게"되는 가장 작은 x를 찾는 문제다.
x의 범위가 매우 커서 x를 찾기 위해 매개변수탐색을 사용해줬다. 그럼 이제 매개변수탐색을 하기 위해 필요한 조건을 찾아야 한다.
x만큼의 돈을 추가했을 때, 몇명의 사람이 평균의 절반 이하만큼 돈을 가지게 되는지 찾는 함수를 만들어주면 된다. 일단 매번 총합을 구하지 않도록 초기의 돈의 합이 s라고 하면, (s+x)/(n*2)보다 돈을 적게 가지고 있는 사람의 수를 세주면 된다.
이것을 빠르게 구하기 위해 초기 돈을 정렬시킨 뒤 이분 탐색으로 O(logN)으로 해결할 수 있다.
이분탐색 + 매개변수 탐색을 활용해서 O((logN)^2)으로 해결할 수 있다.
주의사항은 매개변수탐색에 활용할 최댓값의 범위가 상당히 크다. 10^9*10^6보다는 크게 잡아야 하는데 맨 처음에 10^10으로 했다 WA를 받았다. 10^22로 고쳤더니 맞았다. 해설을 쓰면서 보니까 이분탐색까지는 안써도 충분히 돌아갈 것 같다.
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 *
from itertools import combinations,permutations
def checkcase(add):
val=(s+add)/(2*n)
idx=bisect_left(arr,val)
return idx
for _ in range(int(input())):
n=int(input())
arr=sorted(map(int,input().split()))
mn=0
mx=10**22
s=sum(arr)
rich=max(arr)
while mn<=mx:
mid=(mn+mx)//2
arr[-1]+=mid
loc=checkcase(mid)
arr[-1]-=mid
if loc>n//2:
mx=mid-1
else:
mn=mid+1
print(mn if mn != 10**22+1 else -1)D번 문제
문제가 상당히 재밌는데, 선분의 시작점과 끝점, 그리고 구간의 길이 d가 주어졌을 때 그 구간 안에 가장 적은/많은 종류의 선분을 갖는 위치를 찾는 문제이다.
어제 리뷰하면서 그림판으로 쓱쓱 그린 그림이 있는데
검은색 부분이 범위이고, 색깔 가로선이 선분이다. d만큼 구간을 정해서 구간 내의 가장 많은/적은 종류의 선분을 갖는 위치를 찾는건데,
대충 이런 느낌이라면 i~i+d 구간에는 3종류 (빨강,초록,하늘) 선분이 존재한다.
같은 값이라면 가장 왼쪽의 i를 찾는 문제인데 맨 처음에 누적합(+1,-1) 을 생각했는데 코드까지 다 짜고보니 "종류"의 개수라서 적합하지 않아 보였다. 따라서 다른 풀이를 생각해야 했는데
떠올린 풀이는 슬라이딩 윈도우이다. 선분의 시작점에 +1, 선분의 끝점에 -1을 배치하는 식으로 해결하는데 슬라이딩 윈도우 알고리즘을 사용하면서 새로운 위치를 포함시킬 때 그 위치가 선분의 시작점이면 +1을 해주고, 가장 오래된 위치를 제거할 때 그 위치가 선분의 끝점이면 -1을 해줘서 해결할 수 있었다.
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 *
from itertools import combinations,permutations
for _ in range(int(input())):
n, d, k = map(int, input().split())
arr = [list(map(int, input().split())) for i in range(k)]
presum=[0]*(n+2)
start=[0]*(n+2)
end=[0]*(n+2)
for i in arr:
s,e=i
presum[s]+=1
presum[e+1]-=1
start[s]+=1
end[e]+=1
for i in range(1,n+1):
presum[i]+=presum[i-1]
s=0
for i in range(d):
if start[1+i]==1:
s+=1
ansb=1
ansm=1
mn=s
mx=s
for i in range(1,n-d+1):
if start[i+d]:
s+=start[i+d]
if end[i]:
s-=end[i]
if s<mn:
ansm=i+1
mn=s
if mx<s:
ansb=i+1
mx=s
print(ansb,ansm)E번 문제
올해 항공대 프로그래밍 대회 마지막 문제랑 비슷한 문제, 이게 조금 더 쉽지 않나 싶다.
가중치가 있는 양방향 그래프에서 시작한다. 1번노드에서 시작하는 A와 N번 노드에서 시작하는 B가 만날 수 있는 최소 시간을 구하는 것인데, 못만날 수도 있다. (못만나면 -1 출력)
근데 중간에 말을 탈 수 있는 위치가 있다. 말을 탈 수 있는 위치에 도착하면 말을 탈 수 있고, 이후 이동에 걸리는 시간이 절반이 된다. 만나는 지점에서 말의 탑승 여부는 중요하지 않다.
일반 다익스트라와 동일하게 진행하는데 방문 배열을 vi[player][ride][loc] (player : A인지 B인지, ride : 말을 탔는지 아닌지, loc : 위치) 이렇게 사용해서 풀었다. 저렇게 하면 배열 크기가 2*2*200000이라 조금 무겁지 않나 싶었는데 문제 시간 제한이 5초여서 돌아갔다. vi를 따로 관리해준 경우도 제출해봤는데 시간차이가 크지는 않았다.
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 *
from itertools import combinations,permutations
inf=float('inf')
for _ in range(int(input())):
n,m,h=map(int,input().split())
horse=set(map(int,input().split()))
graph=[[] for i in range(n+1)]
for i in range(m):
a,b,c=map(int,input().split())
graph[a].append((b,c))
graph[b].append((a,c))
hq=[(0,0,1,0),(0,0,n,1)] # ride,cost, loc, type
vi=[[[inf]*(n+1) for i in range(2)] for i in range(2)]
vi[0][0][1]=vi[0][1][n]=0
ans=inf
while hq:
ride,cost,now,typ=heappop(hq)
if now in horse:
ride=1
if vi[ride][typ][now]<cost:
continue
for nxt,nxtc in graph[now]:
nxtcost=cost+(nxtc//2 if ride else nxtc)
if vi[ride][typ][nxt]>nxtcost:
vi[ride][typ][nxt]=nxtcost
heappush(hq,(ride,nxtcost,nxt,typ))
for i in range(1,n+1):
for j in range(2):
for k in range(2):
ans=min(ans,max(vi[j][0][i],vi[k][1][i]))
print(ans if ans!=inf else -1)F번문제
F번은 트리DP, 그리디 둘 중 하나라 생각했는데 그리디로 안되는걸 눈치챘고, 트리DP는 못풀 것 같았는데 진짜 못풀었다.
최근 div4를 계속 올솔해서 자신감이 붙은 상태였는데 피곤해서 영독이 전혀 안되었다. 그래도 F는 못풀었을 것 같아서 점수는 비슷하게 나왔을 듯 ㅋㅋ..
'후기 > 대회' 카테고리의 다른 글
| Codeforces Round 898 (Div. 4) (버추얼) (1) | 2024.09.08 |
|---|---|
| Codeforces Round 886 (Div. 4) (버츄얼) 후기 (0) | 2024.08.31 |
| [2024 KAUPC] 대회 문제 풀이(코드) (1) | 2024.08.05 |
| 7월달 여러 대회들 후기 (2) | 2024.07.31 |
| Codeforces Round 944 (Div. 4) 그래프 탐색에 미친 남자 (1) | 2024.05.11 |
