jay153의 PS 일지

https://www.acmicpc.net/problem/1349 코드http://boj.kr/01722eeb80874eb5a548de9a33448799 난이도 : P2 Elapse Time : 50min 문제를 보고 든 생각은 2개였다. 최종적으로 모든 도시 쌍이 연결되어 있어야 하고 그 비용을 최소화하는 문제이기 때문에 최소 스패닝 트리와 연관이 있을 것 같다는 것과 $N$이 많이 작아 모든 도시 쌍을 다 살펴보는 것이 가능하다는 것이었다. 이 문제에서는 도로의 추가가 없더라도 들어갈 수밖에 없는 고정 비용이 존재한다. 각 도시별로 추가적인 집을 짓는 데 $ \frac{(A_i-B_i)(A_i+B_i-1)C_i}{2}$의 비용이 들고, 연결된 $(i,j)$의 쌍에 대해 $(A_i-B_i)(A_j-B_..

https://www.acmicpc.net/problem/31879  코드http://boj.kr/c33077594ab64b29afb982119b7f59c9 2024 한양대학교 ERICA 프로그래밍 경시대회 HEPC Open Contest N 난이도 : P1 Elapse Time : 80min 문제를 처음 봤을 때 쿼리의 형태부터 살폈다. 문제에서 요구하는 쿼리의 종류는 3개이다. 2번 쿼리는 일반 세그먼트 트리의 update 쿼리와 같고, 3번 쿼리는 금광세그를 조금 변형해주기만 하면 된다. 이 문제가 다른 문제와 가지는 차별점은 1번 쿼리인데, 수열의 값을 바꿔주는 과정에 최대 $N$번 발생할 수 있다. 이 문제를 나이브하게 접근하면 0이 아닌 연속 구간 합을 구하기 위한 1번 세그먼트 트리, 1번 ..

https://codeforces.com/contest/1998 Performance Rating : 2900 A$(x_c, y_c)$를 중심으로 점대칭 시키는 것이 더 강한 조건이기 때문에 이를 만족시키도록 짰다. B주어진 $q_i=p_i(\mathrm{mod}\;n)+1$으로 잡으면 $i=1$, $j=n$일 때를 제외하고 $p_i+ \;\cdots\; +p_j=q_i+.\;\cdots\; q_j$가 성립하는 $i$, $j$가 존재하지 않기 때문에 답이 된다. C$a_i+median(c_i)$에서 $b_i=1$이라면 $k$번의 실행을 모두 $a_i$에 하는 것이 이득이고 $b_i$가 0인 $i$ 중 $a_i$가 최대인 것과 $b_i$가 1인 $i$ 중 $a_i$가 최대인 것 두 개만 보면 된다는 생각을..

https://www.acmicpc.net/problem/24233 코드http://boj.kr/ec86dd18783840d69865df8ff58bea42 shake! 2021 F 난이도 : P2 Elapse time : 80min 처음 이 문제를 봤을 때 든 생각은 2가지였다. 스위핑을 쓰고 싶다는 생각과 #1665와 상황이 비슷 점이 있다는 것이었다. 하지만 물고기가 각자 속도를 가지고 있다는 점과 길이가 제각각이라는 점이 풀이를 떠올리기 힘들게 만들었다. 풀이를 생각하던 중 물고기의 위치와 시간 사이의 그래프를 그려보았는데 그 그래프에서 특정 영역의 중첩 횟수 최댓값을 구하면 된다는 것을 알게 되었다. 그래서 시간에 따른 물고기의 시작점과 끝점의 위치 식을 모두 저장해 놓고 교점을 가지고 스위핑을 ..

https://www.acmicpc.net/problem/23736 코드http://boj.kr/247a5b6a0d2141aeafb65039b92cac04 3rd UNIST Algorithm Programming Contest Uni-CODE 2021 G 난이도 : P2 Elapse time : 10min 우선 문제 상황이 꽤 복잡해 보였다. 문제를 간단화하기 위해 게임을 하면서 선택한 간선들을 초기 그래프에 표시했을 때 어떤 모양이 될지 생각해 보았다. 당연하게도 그래프의 스패닝 트리가 되는 것을 확인했고 Yunee가 어떻게 빨간색과 파란색을 나누든 최대 스패닝 트리를 고를 수 있다. 그렇다면 Woongbae의 입장에서는 최대 스패닝 트리를 만드는 것이 이득이고 반대로 어떻게 빨간색과 파란색을 나누든 ..

https://www.acmicpc.net/problem/18303 코드http://boj.kr/fe36e3b0eef6488098fb5a81110b80f3 Southwestern European Regional Contest SWERC 2019 K 난이도 : P2 Elapse time : 50min 문제 지문이 복잡하여 이해하는데 시간이 꽤 걸렸다. 문제 이해를 하고 나니 문제의 요구사항은 꽤 간단했다. 유향그래프 $P$에서 한 정점 $T$가 주어졌을 때 $P$에 있는 정점 중 $T$로 향하는 간선이 있는 정점들을 생각하자. 그 정점들 중 $T$와 직접 연결된 간선을 거치지 않으면 $T$로 도달할 수 없는 정점들을 모두 구하는 문제였다. 우선 $T$로 향하는 간선이 존재하는 모든 정점들에 대해 그래프 탐..

https://www.acmicpc.net/problem/10760 코드http://boj.kr/2d99b1fb4d394b3a810946241c8a2e1e업솔빙http://boj.kr/34a429ec34da451bba1b598137e5fca8 USACO Open Contest 2015 Gold 3 난이도 : P1 Elapse time : 100min 처음에 이 문제를 봤을 때는 시뮬레이션을 하지 않고 어떻게 풀 수 있을까? 였다. 이때 든 생각이 $i$번째 건초더미와 $j$번째 건초더미 사이에 있을 때 각각의 크기가 $p_j-p_i$이상이면 두 건초더미 사이를 절대 나갈 수 없다는 것이었다. 그렇다면 이 조건을 만족하는 모든  구간 길이의 합을 구하면 된다. 이 아이디어를 떠올리기까지 30분이 걸렸는데,..

https://codeforces.com/contest/2069Performance Rating : 2700 A 처음에 조금 당황했는데 잠깐 생각해 보니 B에 1 0 1이 있는지 판단하는 문제였다. B 체스판칠을 하면 하나의 색깔을 무조건 2번에는 원하는 색으로 바꿀 수 있다. 그래서 인접한 같은 색이 있으면 2, 없으면 1이 된다. 이를 구현해 맞았다. C 문제를 보고 DP가 아닐 수 없다고 생각했다. 길이가 3 이상인데 2인 것도 포함하는 것을 짰다가 길이 3 이상이라는 것을 알고 수정했다. D 우선 양 끝에서 $s[i]=s[n-i-1]$이면 볼 필요가 없다는 것을 생각했다. 이후 바꾸지 않을 substring을 고를 때 그 substring에서 남은 string의 알파벳의 개수 중 반을 넘게 가져가..