전체 글 (74) 썸네일형 리스트형 2023 ICPC Seoul 예선 후기 2023 ICPC 예선에 ktw020406, munhwas1140과 Mid Yummi팀으로 참가해 6솔 16등으로 마무리했고 저는 DGJ를 풀었습니다 16등이라고 보고 별 느낌이 없었는데 인접한 팀들을 보니 가슴이 웅장해지네요 + 예선을 잘치니까 욕심이 생겨서 본선 20등을 목표로 PS를 다시 열심히 하기로 했어요 스코어보드 작년 icpc 참가 경험이 있는 두 선배와 같이하게되었다 연습은 예선을 앞두고 딱 한번 했는데 뭔 인터렉티브 2개, 실수쓰는거 3개, 3차원 기하 1개 이런셋이 걸려서 처참한 결과를 확인하고 유의미한 전략 설정이나 피드백을 전혀 하지 못한채로 대회를 치게돼버렸다 예선에서 학교 컴퓨터에 C++ 세팅을 직접 해야됐는데 환경변수고 뭐고 아오 편한 세팅 맞춰둘 생각하니까 골통이 깨질것 같았.. 2023 UCPC 예선 후기 는 히다가 썼으니 링크만 달겠음... https://heejayaa.tistory.com/194 [BOJ 27014] Cube Stacking https://www.acmicpc.net/problem/27014 27014번: Cube Stacking Farmer John and Betsy are playing a game with N (1 ≤ N ≤ 30,000)identical cubes labeled 1 through N. They start with N stacks, each containing a single cube. Farmer John asks Betsy to perform P (1≤ P ≤ 100,000) operation. There are two types of ope www.acmicpc.net Tag : DSU 스몰투라지, 세그 등... 뇌절각은 잔뜩 보이는데 그냥 \(O(logN)\) 이하의 유니온 파인드로 생각을 했을 .. Path Comprssion DSU의 amortized O(logN) 증명 Weighted union rule, Path compression 중 하나만 사용하면 amotized \(O(logN)\), 둘 모두를 사용하면 amortized \(O(\alpha(N))\)임이 잘 알려져있습니다. Path compression만을 사용했을 때 시간복잡도의 증명은 한글 자료가 잘 없는 것 같아 작성합니다. Heavy Light Decomposition스러운 논리를 사용합니다. 정점 u가 v의 자식일 때 sz[v] \(\leq\) sz[u] / 2이면 u->v간선은 light edge, 나머지는 heavy edge라고 해봅시다. 당연하게도 heavy edge는 정점당 하나만 생깁니다 (sz[x] := x의 서브트리의 크기) 임의의 정점 (u, v)에 대해 u->v로 가는 경로는 최대 \.. [BOJ 11003] 최솟값 찾기 - 모노톤 큐 없이 O(n) https://www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 최솟값 찾기는 모노톤 큐를 사용해 푸는 풀이가 보편적인데 모노톤 큐를 사용하지 않는 \(O(n)\) 풀이를 소개하겠다. 1. 배열을 k개씩 묶음으로 쪼개 각각 묶음에서 prefix min, suffix min을 구한다. 2. min(prefix_min[i], suffix_min[i - k + 1])을 출력한다. i mod k = 0인 i는 i - k + 1 4500.. [BOJ 24978] Subset Equality https://www.acmicpc.net/problem/24978 24978번: Subset Equality The cows are trying out a new method of exchanging coded messages with each-other where they mix irrelevant letters in among relevant letters to make the messages hard to decode. The cows transmit two strings $s$ and $t$ each of length at most $10^5$ consi www.acmicpc.net Sol 1) 메모이제이션 잘한 완탐 문자 집합 A에 대해 정답이 Y라면 A의 부분집합 B는 모두 Y다. N이라면 .. [BOJ 3392] 화성 지도 https://www.acmicpc.net/problem/3392 3392번: 화성 지도 첫째 줄에 화성탐사선 성화가 보낸 지도의 수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 지도의 정보가 주어진다. 지도의 정보는 네 정수 x1, y1, x2, y2 (0 ≤ x1 < x2 ≤ 30,000, 0 ≤ y1 < y2 ≤ 30 www.acmicpc.net Tag : simd 스위핑하면서 (r-l)/16번 나이브하게 더해줬다. 시복은 \(O(30000^2 / 16) \) 코드 #pragma GCC optimize ("O3,unroll-loops") #pragma GCC target ("avx,avx2,fma") #include #include using namespace std; #de.. [BOJ 13551] 원과 쿼리 https://www.acmicpc.net/problem/13551 13551번: 원과 쿼리 2차원 좌표 평면 위에 점 N개가 있다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. x, y, r: 중심이 (x, y)이고, 반지름이 r인 원의 내부에 점이 몇 개 있는지 출력한다. 원의 둘레 위에 있는 www.acmicpc.net clang으로 냈더니 살짝 커팅한 나이브가 돌더라...ㅋㅋㅋ https://blog.naver.com/jinhan814/222680932977 [jinhan814님 풀이] 코드 #include "bits/stdc++.h" #define endl '\n' using namespace std; using ll = long long; const int di[4] = {0, -1, .. 이전 1 2 3 4 ··· 10 다음
