1주 내내 아무것도 하기 싫어서 아무것도 안하고 있다가 할건 해야지 하고 시작.
결과
A번 풀이
문제
https://codeforces.com/contest/1971/problem/A
알고리즘 분류
구현, 정렬
풀이
a, b 가 주어지면 정렬된 순서로 출력
값이 2개밖에 없으니까 min max이용해서 해결해줫다.
from sys import stdin,setrecursionlimit
from collections import deque,defaultdict
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right
from math import *
setrecursionlimit(200000)
input=stdin.readline
for _ in range(int(input())):
a,b=map(int,input().split())
print(min(a,b),max(a,b))B번 풀이
문제
https://codeforces.com/contest/1971/problem/B
알고리즘 분류
구현 문자열
풀이
순서를 바꿔서 기존 문자열과 다른 문자열을 만들수 있으면 YES 출력 후 예시 출력, 아닌 경우 NO 출력인데
모두 같은 문자로 이루어진 문자열이 아니면 YES이고 다른 문자열 하나 출력은 맨 앞꺼 때서 맨뒤에 붙여줬다. 혹시 이렇게 해서 같은 값이 나올수 있지 않을까 하고 다를때 까지 비교해서 출력하게 짜긴 했는데 제출하고 생각하니 무조건 맨 앞에거 때서 맨뒤 붙이면 달라지게 된다.
for _ in range(int(input())):
s=input().rstrip()
if len(set(s))!=1:
print("YES")
print(s[1:]+s[0])
else:
print("NO")C번 풀이
문제
https://codeforces.com/contest/1971/problem/C
알고리즘 분류
구현
풀이,
선분 교차 판별인데 교차하거나 교차하지 않음을 보이면 된다. 교차하는 경우는 a<c<b, not a<d<c인 경우 그리고 그 반대의 경우가 있는데 교차하지 않는 경우는 a<c<b, a<d<c 이거나 not 앞 상황 인 경우이다.
for _ in range(int(input())):
a,b,c,d=map(int,input().split())
if min(a,b)<c<max(a,b) and min(a,b)<d<max(a,b):
print("NO")
elif not (min(a,b)<c<max(a,b)) and not (min(a,b)<d<max(a,b)):
print("NO")
else:
print("YES")D번 풀이
문제
https://codeforces.com/contest/1971/problem/D
알고리즘 분류
그리디, 문자열, 정렬
풀이
아이디어는 이어지는 순서가 1->0이나 0->1일때 분리해주면 되는데 단 한번 0->1인 경우 이어붙일 수 있다.
01001001011인 경우 0->1인 경우 묶은 한개의 블럭과 1로만 이루어진 블럭 0으로만 이루어진 블럭으로 나누면 0으로만 이루어진, 0->1 전환되는 블럭, 1으로만 이루어진 블럭 이렇게 붙이면 된다.
스택을 활용해서 이걸 구현했다.
for _ in range(int(input())):
case=list(input().rstrip())
zeroone=False
now=0
st=[]
ans=0
while now<len(case):
if case[now]=='1':
if not st or st[-1]=='1':
st.append('1')
else:
if not zeroone:
zeroone=True
st.append('1')
else:
ans+=1
st=['1']
if case[now]=='0':
if not st or st[-1]=='0':
st.append('0')
else:
st=['0']
ans+=1
now+=1
print(ans+bool(st))E번 풀이
문제
https://codeforces.com/contest/1971/problem/E
알고리즘 분류
구현, 이분탐색, 정렬, 수학
풀이
구간의 거리를 알고, 구간 사이의 지점을 알려주고 지점별 도착 시간을 알려준다. 지점 사이 거리와 도착 시간을 이용하여 지점 사이에 이동속도를 구할 수 있다.
쿼리로 주어지는 위치를 알고있는 지점들에 대해 이분탐색해서 위치를 구해준 뒤 가장 가까운 거리에서 얼마나 떨어져 있는지 구할 수 있고, 지점 사이의 이동속도를 알고 있으므로 시간을 구할 수 있다.
문제에서 소수점을 버리라고 하는데 소수 처리가 이문제 신경썼어야 할 부분이다.
시간을 구하는게 거리/걸린 시간인데 이걸 float형태로 저장했다 나중에 연산에 사용하면 WA 받는다. (알고 싶지는 않았지만 ㅠㅠ) 소수점을 버릴 수 있으므로 나중에 쿼리에서 주어지는 위치와 가장 가까운 지점 사이의 거리를 속도로 나눠주어야 하는데 이걸 지점 사이의 속도가 d/t 쿼리에서 주어진 위치에서 가장 가까운 지점 사이의 거리가 D라고 했을 때 D를 이동하는데 걸리는 시간을 구하는 방법은 D/(d/t)이므로 (D/1)/(d/t)꼴로 생각해서 (D*t)/d로 해주면 되는데 소수점은 버려야 하므로 이렇게 연산시 소수가 등장할 일이 없다. 지점 사이의 속도를 d/t가 아닌 d,t를 따로 저장해주어서 해결했다.
풀이랑 별개로 E번까지 풀면서 setrecursionlimit을 20만 땡겨놓고 있었다. 생각해보니까 pypy 사용시 저렇게 하면 메모리 엄청 잡아먹어서 메모리 초과 당하는데 까먹고 있었다. 그래서 메모리로 1WA, 소수 신경 안쓰다가 2WA.. 해서 3WA 받고 통과했다.
from sys import stdin,setrecursionlimit
from collections import deque,defaultdict
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right
from math import *
input=stdin.readline
for _ in range(int(input())):
n,k,q=map(int,input().split())
a=[0]+list(map(int,input().split()))
b=[0]+list(map(int,input().split()))
spd=[]
for i in range(k):
spd.append((a[i+1]-a[i],b[i+1]-b[i]))
ans=[]
for i in range(q):
loc=int(input())
if loc==0:
ans.append(0)
continue
idx=bisect_left(a,loc)-1
ans.append(b[idx]+(spd[idx][1]*(loc-a[idx]))//spd[idx][0])
print(*ans)
F번 풀이
문제
https://codeforces.com/contest/1971/problem/F
알고리즘 분류
이분탐색, 그래프 탐색
풀이
사실 맨 처음 떠오른 풀이는 DP, 어떤 규칙이 존재하지 않을까 했는데 규칙을 못찾았고, 심지어 브루트포스로 n<3000까지 구해봤는데 크기가 단조 증가가 아니라 감소도 하는거 보고 이 문제 DP 아닐 가능성이 있다는 생각이 들었다.
그래서 처음 생각이 난게 https://www.acmicpc.net/problem/1300이 문제인데, 매개변수나 이분탐색으로 어떻게 수학적으로 잘 접근하면 풀리지 않을까, 고민하고 있다가 갑자기 어떤 생각이 들었다.
생각보다 증가폭이 굉장히 작다. 최대값이 1만인데 예시 케이스에서 2천의 출력값이 12000밖에 되지 않았고, 3000까지 브루트포스로 구한 값들을 봐도 1만가지 가도 40만 안쪽으로 풀 수 있을 것 같았다. 그래서 한번 다 구해보자 라는 생각이 들었다.
몇가지 아이디어를 적용해볼 수 있다. 굳이 모든 분면의 점들을 모두 구할 필요 없다. 한개의 분면을 정해서 그쪽만 구한 뒤 *4를 해주면 된다. 그럼 이제 그 값들을 어떻게 구할 것이냐 생각을 해보면 대충 이 점들의 분포는 원형이다. 그리고 시작점으로 선택할 점이 있다. 바로 n,0과 0,n이다. 이 값들은 항상 고정이다 거리가 n+1이면 n+1,0 0,n+1 이럴 것이고, 이 점에서 bfs를 돌렸다. 나는 0,n에서 출발해서 오른쪽, 아래, 오른쪽아래 이렇게 3방향으로 이동을 진행해서 n**2<=x**2+y**2<(n+1)**2인 값들을 모두 구해주었다.
이문제도 recursionlimit 200000때문에 메모리 한번 터졌다 ㅠㅠㅠㅠㅠ.. F->E 순서로 풀어서 눈치채는게 늦었다. 그냥 큐땜에 터졌나 하고 어찌 최적화 하니 다음엔 맞아서,,
from sys import stdin,setrecursionlimit
from collections import deque,defaultdict
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right
from math import *
setrecursionlimit(200000)
input=stdin.readline
dx=[0,-1,-1]
dy=[1,0,1]
def bfs(x,y):
vi=defaultdict(int)
queue=deque([(x,y)])
n=x
vi[(x,y)]=1
while queue:
x,y=queue.popleft()
for i in range(3):
nx=x+dx[i]
ny=y+dy[i]
if nx>0 and ny>-1:
if (nx,ny) not in vi and n**2<=nx**2+ny**2<(n+1)**2:
vi[(nx,ny)]=1
queue.append((nx,ny))
return len(vi)
for i in range(int(input())):
n=int(input())
print(bfs(n,0)*4)G번 풀이
문제
https://codeforces.com/contest/1971/problem/G
알고리즘 분류
정렬, 분리집합
풀이
HACK 당했다 ㅠ.. xor 연산의 특징을 알고 있으면 조금 편한데
x y가 있을 때 x^y한 결과가 4 이하인 경우 1,2,3인 경우 스왑 가능한데 x^n=y인 경우 x^y=n이다. 그니까 n이 1,2,3일 때 x^n이 같은 배열에 존재하면 그 값들 끼리는 스왑이 가능하다. 이 값들끼리 잘 묶고 정렬해서 작은값부터 차례대로 넣어주면 되는데 여기서 분리집합을 썼어야 했다. 나는 BFS로 했는데 TLE 2번 받고 어찌어찌 최적화 하긴 했는데 불안한 상태로 제출해서 결국 TLE로 HACK당했다. 구현에서 좀더 빡세게 커팅했으면 통과 했을 것 같기도 했다.
def bfs(x):
queue=deque([x])
vii=defaultdict(int)
vi=set()
for i in idx[x]:
vi.add(i)
vii[x]=1
while queue:
now=queue.popleft()
for i in range(1,4):
nxt=now^i
if nxt not in vii and nxt in idx:
for j in idx[nxt]:
vi.add(j)
vii[nxt]=1
queue.append(nxt)
od=[]
for i in sorted(vii):
od+=[i]*len(idx[i])
return sorted(vi),od
for _ in range(int(input())):
n=int(input())
arr=list(map(int,input().split()))
idx=defaultdict(list)
for i,v in enumerate(arr):
idx[v].append(i)
ans=[-1]*n
for i in range(n):
if ans[i]==-1:
loc,v=bfs(arr[i])
for j in range(len(loc)):
ans[loc[j]]=v[j]
print(*ans)후기
모든 문제를 BFS나 DFS같은 기본적인 테크닉으로 접근하는 병이 생겼나보다 ㅋㅋㅋㅋ
이번에는 지문이 술술 읽혀서 나름 만족스러웠고 ( 영어가 안되니 문제 이해하는데 생각보다 시간이 많이 걸린다 )
F번 코드를 어떤 외국인 친구가 봤는지
이런 메세지를 보냈다. 대충 해석하면 "와 님 코드 신기하네 발상 어떻게 함?" 이런 느낌인데 부끄러운 실력이지만 기분 좋았다 ㅋㅋㅋ 답변은 뭐 위에 적은것처럼 "무식하게 구해봤는데 경우의 수 얼마 안되서 걍 다 구해봄" 이렇게 보내줬다.
G번 핵당한거 맘아프긴 해도 간만에 푸는 맛 제대로 느꼈던 것 같다.
'후기 > 대회' 카테고리의 다른 글
| [2024 KAUPC] 대회 문제 풀이(코드) (1) | 2024.08.05 |
|---|---|
| 7월달 여러 대회들 후기 (2) | 2024.07.31 |
| Codeforces Round 943 (Div. 3) (2) | 2024.05.03 |
| Codeforces Round 937 (Div. 4) (3) | 2024.04.01 |
| KAUPC 2023 대회 후기 (1) | 2023.07.30 |
