본문 바로가기

알고리즘48

SCPC 2023 1차 예선 예선에서 3문제 이상 푼건 처음이라 나름 기쁘다. ㅎㅎ 문제 1: O(N) 완전탐색 #include #define all(v) (v).begin(), (v).end() using namespace std; using ti2 = pair; using ll = long long; using tl2 = pair; void solve() { int N, A, B; cin >> N >> A >> B; // A > B if (A 1; if (l 1; if (v[mid] rmost_berry) r.. 2023. 7. 29.
라빈-카프와 부분문자열 쿼리 문자열 s의 해시값은 위 해시 함수로 $O(|s|)$에 구할 수 있다. using ll = long long; using pll = pair; const ll X = 131, md1 = 1e9+7, md2 = 1e9+9; pll hs(string &s) { pll H = { 0, 0 }; for (int i = 0; i < s.size(); ++i) { auto &[a, b] = H; a = (a * X + s[i]) % md1; b = (b * X + s[i]) % md2; } return H; } 길이가 $L (L \le |s|)$인 모든 부분문자열들의 해시값 역시 라빈-카프 알고리즘으로 $O(|s|)$에 구할 수 있다. #include #define all(v) (v).begin(), (v).end.. 2022. 7. 22.
shake! 2021 참여 및 PS를 마치며... 지난 대회보다 4등 올랐다. ^^ C번 까지는 쉬웠는데 감이 떨어져서 여러 번 틀려버렸다. (아쉽다는 뜻) 이번 대회를 마지막으로 PS는 그만두기로 했다. 긴 실력 정체와 더 이상 대회에서 유의미한 결과를 내지 못함을 인정한다는 뜻이다. 그래도 공부를 열심히 해본 경험이 생겼고, 좋은 친구들도 만들어 지난 2년에 후회는 없다. 졸업까지 남은 3년동안은 개발 공부에 더 열을 올리고 재미있는 웹 장난감도 많이 만들어보려 한다. 내 인생 화이팅!! ㅎㅎ 2022. 1. 15.
2021 인하대학교 프로그래밍 경진대회(IUPC) 참여 팀 수퍼겁쟁이들의 쉼터 (39dll, yuja, 나)로 참여하여 총 일곱 문제를 풀었다. 감이 많이 떨어져 걱정이 많았는데, 운 좋게 최고의 팀원들을 만나 1등 상을 수상했다. ㅎㅎ 나는 A, B, K번을 풀었는데 모두 쉬운 문제라 풀이는 따로 작성하지 않는다. 공식 풀이 대신 이번 대회가 팀 대회라는 부분에서 잘했던 점과 아쉬웠던 점을 되짚어보면.. 우선 yuja님이 대부분의 구현을 맡아주셨다. (감사합니다) 나는 대략적인 풀이를 전달한 뒤 입력파일 생성기 작성과 반례 찾기에 집중했고, 오류 수정에 도움이 될 수 있었다. 다른 문제에 도전하는 것도 좋았겠지만 WA에도 사기를 잃지 않을 수 있었던 점에서 만족스러웠다. 한두 문제 정도 더 풀 수 있었지만, 아쉽게도 그러지 못했던 이유는 1. 최근에 코드포.. 2021. 10. 4.
Segment tree struct Segt { using T = int; static constexpr T def = 1= 1; ) { seg[i] = segfun(seg[i 2021. 8. 12.
UCPC 2021 예선 참여 후기 openingsound, 39dll님과 함께 팀 Wrong answer on으로 참여하였다. 나는 B, H 두 문제를 풀었고, 총 다섯 문제를 풀어 64등으로 마감하였다. 비대면으로 별다른 준비 없이 시작했지만, 대회 과정이 즐거웠고 나쁘지 않은 결과로 마무리하게 되어 만족스럽다. 아래는 내가 작성한 풀이와 구현이다. B번 항체 인식 22352번: 항체 인식 첫 번째 줄에는 SP 촬영 결과의 크기를 의미하는 두 정수 $N$과 $M$이 주어진다. ($1 \le N, M \le 30$) 이는 촬영 결과가 세로로 $N$칸, 가로로 $M$칸 크기의 격자라는 것을 의미한다. 다음 $N$개의 줄에는 www.acmicpc.net 처음 상태에서 DSU로 같은 집합끼리 묶는다. 다음 상태에서 바뀐 cell이 속한 집합에.. 2021. 8. 1.