PS
-
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. 이를 재귀적으로 생각한다. 그러나 위 접근법을 이용한 풀이를 내려면 수열의 임의의 구간에서 유일한 원소가 존재하는지 판별해야 하는데, 이를 빠르게 할 수..
-
KMP 알고리즘자료 2024. 7. 15. 12:17
Q) 길이가 $N$ 이하인 두 문자열 $A$와 $B$가 있다. 이때 $A$가 $B$를 substring으로 가지는지 판별하여라.나이브를 생각해보자. $A$와 $B$의 길이를 각각 $a$, $b$라고 할 때 $A$의 모든 점에서 시작해 길이가 $b$인 substring을 뽑고, 그것이 $B$와 같은지 확인하면 되므로 나이브의 시간복잡도는 $O(N^{2})$이 된다. KMP 알고리즘은 이 문제를 선형에 푸는 데 사용된다. 직관적인 최적화를 생각해보자. 눈으로 두 문자열을 비교한다고 생각할 때, 우리는 위의 나이브 알고리즘처럼 하나하나 비교하지 않는다. 대충 표현하자면 좀 많이 겹치는 것 같은 부분을 집중해서 비교한다고도 할 수 있다. 이를 알고리즘적으로 서술하는 것이 가능할까?KMP 알고리즘의 작동 방식을 ..
-
UCPC 2024 예선 후기대회 2024. 7. 15. 04:44
ICPC 팀원 두 명이 모두 방학에 바쁘다고 탈주를 해버렸다. 그래서 고등학교 친구들(crescmoon, menzrach02)과 함께 즐겜팟을 꾸려 올해 UCPC에 참가하게 되었다. 즐겜팟이지만 나름 SNU X KAIST X MIT라는 멋있는 간판까지 달고 있는 팀으로, 본선 진출을 목표로 참가했다. crescmoon은 PS를 잘 안 해서 그렇지 최근 코포 두 라운드의 퍼포먼스가 각각 퍼플과 오렌지인 재능충이고, menzrach02는 나한테 PS를 배우던 두세 달 이외에는 PS를 한 적이 없고 자기는 PS가 싫다고 주장하지만 나한테 배울 당시 BFS도 모르던 수준에서 시작해 몇 달 만에 CHT나 HLD 등 RUN 중급반 스터디 내용을 흡수하던, 마찬가지로 재능충이다. 그렇기에 가장 어려운 점인 "고등학교..
-
2024 현대모비스 알고리즘 경진대회 후기대회 2024. 7. 15. 03:31
작년 여름에 SCPC, UCPC는 본선까지 갔으나 현대모비스만 예선에서 탈락했던 기억이 있다. 결론부터 말하자면 올해는 본선 진출에 성공했다! 오늘은 현대모비스 후기를 풀어보도록 하겠다.[예선]작년 예선 광탈의 경험으로 깨달은 점은 "여유를 부리면 안 된다"였다. 대충 이 정도면 이 문제 구현이 끝나고 다음 문제로 넘어가겠지 싶은 시점에 의문의 맞왜틀이 시작되면 멘탈이 흔들리면서 아예 망할 수 있기 때문이었다. 그래서 이번에는 풀이가 생각나면 이걸 짤 수 있을까 고민하기도 전에 구현에 들어갔다.1번)유향그래프가 주어질 때, 몇 개의 정점에 말을 놓는다. 말은 매시간 간선을 따라 최대 한 칸 움직인다. 단 첫 번째 시간에는 무조건 한 칸 움직인다. 이때 어떻게 해도 충분한 시간 후에 한 정점에 두 개 이상..
-
백준 13182 제비문제 2023. 7. 13. 17:12
https://www.acmicpc.net/problem/13182 13182번: 제비각 테스트 케이스마다 한 줄에 그가 잠을 자러 갈 때까지 뽑게 되는 제비 개수의 기댓값을 출력한다. 정확한 판별을 위해, 답을 기약분수로 나타내었을 때 a/b가 된다면, (a × b-1) mod 1,000,000,007을www.acmicpc.net열심히 식을 정리하면 되는 문제이다. Trivial 하게 $D_{r, g, b, k}$를 정의하자. 이때 다음 식을 세울 수 있다.$$D_{r, g, b, k}={r \over r+g+b}D_{r-1, g, b, k}+{g \over r+g+b}D_{r, g, b, k}+{b \over r+g+b}D_{r, g, b, k-1}+1$$위 점화식을 조금 정리하면 아래와 같다.$$D..