전체 글
-
2024 ICPC Asia Seoul Regional 후기대회 2024. 12. 14. 08:03
팀원 : abra_stone, gs20036 별로 후기글을 쓸 만큼 좋은 성적을 거두지 못한 대회라 짧게 쓰고자 한다. 예선) A, E, F, H를 풀었다. 나는 빠르게 E와 F를 풀고, 남는 시간에 G 풀이를 냈다. gs20036이 A를 퍼솔하고 abra_stone이 H를 맞왜틀 끝에 풀었는데, 남은 시간에 gs20036의 D와 내 G를 둘 다 짜려다가 둘 다 맞왜틀을 당하고 4솔로 마무리했다. 내가 푼 문제들의 풀이는 다음과 같다. E : 각 열에 대해 전처리를 하면 된다. 매우 쉬운 문제이다.F: 각 선분에 대해 주어진 두 점이 같은 편에 있는지 반대편에 있는지 판별하면 된다. 이는 CCW를 이용해 쉽게 할 수 있다.G: 같은 가중치를 가진 간선들을 그룹화하고 가중치가 작은 순으로 정렬한다. 이후 ..
-
2024 SCPC 2차 예선 후기 및 풀이대회 2024. 7. 27. 22:05
기분 좋게 12시쯤 일어나서 디스코드를 보니 9시에 SCPC가 시작해 있었다.1. 연속 10과 1로 이루어진 문자열이 주어진다. $S$의 비용을 지불하고 0을 1로, $E$의 비용을 지불하고 1을 0으로 바꿀 수 있을 때, 연속된 1이 한 묶음 이내가 되게 하는 최소 비용을 구하는 문제이다. 각 인덱스에 대해, 이 인덱스 이전을 00...0011...11로 만들 수 있는 최소 비용과, 이 인덱스 뒤를 11...1100...11로 만들 수 있는 최소 비용을 DP로 구한 다음, 더해서 최솟값을 찾는다. 이후 전부를 0으로 만드는 비용과 비교하여 출력하면 된다. 더보기#include#includeusing namespace std;typedef long long ll;int t, n, s, e;int arr[..
-
백준 3408 - Non-boring sequences문제 2024. 7. 21. 03:25
https://www.acmicpc.net/problem/3408길이 $N(\leq 200000)$의 수열이 주어졌을 때, $N$의 모든 substring이 유일한 원소를 가지면 non-boring, 아니면 boring을 출력하는 문제다. 처음에 시도한 접근법은 아래와 같다.1. 수열 전체에 유일한 원소가 없다면 그 수열은 boring이다.2. 그렇지 않다면, 해당 원소를 포함한 모든 구간은 유일한 원소를 가진다.3. 따라서 해당 원소를 기준으로 수열이 두 부분으로 나뉘어지게 되고, 각각이 non-boring이면 전체 수열도 non-boring이다.4. 이를 재귀적으로 생각한다. 그러나 위 접근법을 이용한 풀이를 내려면 수열의 임의의 구간에서 유일한 원소가 존재하는지 판별해야 하는데, 이를 빠르게 할 수..