jay153의 PS 일지

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의 알파벳의 개수 중 반을 넘게 가져가..