전체 글
-
중급반 8주차 풀이 - 세그먼트 트리ALOHA - 2022/ALOHA - 중급반 (2022 1학기) 2022. 5. 31. 13:05
1. [2042] 구간 합 구하기 (Gold I) 더보기 Segment Tree (Point Update & Range Sum Query) 연습 문제입니다. const int N = 1048576; ll seg[2097160]; void upd(int pos, ll val){ pos += N-1; seg[pos] = val; pos >>= 1; while (pos){ seg[pos] = seg[pos= 1; ed >>= 1; } return res; } void Main(){ int n, m, k; cin >> n >> m >> k; int q = m+k; for (int i = 1; i > seg[i+N-1]; } for (int i = N-1; i >= 1; i--){ seg[i] = seg[i po..
-
초급반 8주차 풀이 - 이진 탐색, 파라메트릭 서치, LIS in O(N log N)ALOHA - 2022/ALOHA - 초급반 (2022 1학기) 2022. 5. 31. 07:46
중급반 3주차 풀이 - 이진 탐색, 파라메트릭 서치, 두 포인터 A. [11053] 가장 긴 증가하는 부분 수열 (Silver II) 더보기 \( DP_{i} := \) \( i \)번째 원소로 끝나는 LIS 로 정의하면, \( DP_{i} = \max_{A_{j} \lt A_{i}} DP_{j} + 1 \)로 점화식을 세울 수 있습니다. 초기.. hibye1217-aloha.tistory.com 중급반 3주차의 1~13번 문제입니다. (...)
-
고급반 7주차 풀이 - 으랏차차 (5 / 14)ALOHA - 2022/ALOHA - 고급반 (2022 1학기) 2022. 5. 25. 16:48
1. [19321] Longest Increasing Subsequence (Gold IV) 더보기 예제가 너무 친절합니다. \( f_{i} \)가 큰 값부터, 같다면 앞의 칸부터 시작해서 \( N \)부터 1까지 채워주면 됩니다. 이러면 동일한 레벨 or 낮은 레벨에서의 값은 무시하면서 진행되니 잘 되는 걸 볼 수 있습니다. int arr[100020]; int ans[100020]; void Main(){ int n; cin >> n; priority_queue pq; for (int i = 1; i > arr[i]; pq.push({ arr[i], -i }); } for (int i = n; i >= 1; i--){ int val = pq.top().fr, idx = -pq.top().sc; pq...
-
중급반 7주차 풀이 - DSU, MSTALOHA - 2022/ALOHA - 중급반 (2022 1학기) 2022. 5. 25. 15:34
1. [1717] 집합의 표현 (Gold IV) 더보기 Union-Find 구현 문제입니다. 특별한 것도 없습니다. int par[1000020]; int fnd(int a){ if (par[a] == a){ return a; } return par[a] = fnd(par[a]); } void uni(int a, int b){ par[fnd(a)] = fnd(b); } void Main(){ int n, q; cin >> n >> q; for (int i = 0; i > typ; if (typ == 0){ int a, b; cin >> a >> b; uni(a, b); } if (typ == 1){ int a, b; cin >> a >> b; cout n >> m; for (int i = 1; i arr..
-
초급반 7주차 풀이 - STL, GreedyALOHA - 2022/ALOHA - 초급반 (2022 1학기) 2022. 5. 25. 10:33
1. [8958] OX퀴즈 (Bronze II) 더보기 문자열을 한 글자씩 읽으면서 O가 나올 때마다 점수에 1씩 더하고, X가 나올 때마다 점수를 0으로 초기화시켜주면 됩니다. 최종 점수는 각 글자에서 얻는 점수의 합이 됩니다. void Main(){ int t; cin >> t; while (t--){ string s; cin >> s; int ans = 0, com = 0; for (char ch : s){ if (ch == 'O'){ com += 1; } else{ com = 0; } ans += com; } cout q; while (q--){ string x, s; cin >> x >> s; if (s == "enter"){ st.insert(x); } else{ st.erase(x); } }..
-
[2022.05.18.] n^m의 약수의 합ALOHA - 2022/ALOHA - 오늘의 문제 (2022 1학기) 2022. 5. 22. 00:00
문제 정보 링크: https://www.acmicpc.net/problem/11693 난이도: Gold II 분류: [수학 → 정수론] [분할 정복 → 분할 정복을 이용한 거듭제곱] 문제 요약 \( N^M \)의 약수의 합을 구하면 됩니다. 정말 정직하죠? 풀이 \( N \)을 소인수분해한 결과가 아래와 같다고 합시다. \( N = p_{1}^{e_{1}} \times p_{2}^{e_{2}} \times \ldots p_{k}^{e_{k}} \) 그럼 \( N^M \)을 소인수분해한 결과는 자명히 아래와 같게 됩니다. \( N^M = p_{1}^{Me_{1}} \times p_{2}^{Me_{2}} \times \ldots p_{k}^{Me_{k}} \) 지금부터는 이 \( Me_{i} \)를 편의상 ..
-
[2022.04.14.] N과 M (6)ALOHA - 2022/ALOHA - 오늘의 문제 (2022 1학기) 2022. 5. 21. 23:41
문제 정보 링크: https://www.acmicpc.net/problem/15655 난이도: Silver III 분류: [재귀 → 백트래킹] 문제 요약 \( N \)개의 수가 주어질 때, \( M \)개를 중복없이 선택해서 만들 수 있는 모든 조합을 찾으면 됩니다. 풀이 오름차순으로 정렬된 수열을 출력해야 하니, 들어온 수들을 오름차순 정렬해봅시다. 이제 남은 건 백트래킹으로, \( M \)개를 "중복 없이" 고르는 걸 시뮬레이션해주면 됩니다. 이는 "마지막으로 선택한 원소의 위치"를 저장한 뒤, 이보다 더 오른쪽에 있는 원소만을 골라주면 됩니다. int n, m; int arr[10]; int res[10]; void btk(int cnt, int idx){ if (cnt == m){ for (int..
-
고급반 6주차 풀이 - 으쌰으쌰 (10 / 13)ALOHA - 2022/ALOHA - 고급반 (2022 1학기) 2022. 5. 19. 14:39
1. [14370] 전화번호 수수께끼 (Large) (Gold III) 더보기 숫자를 나타내는 영어단어들을 보면, 자주 나오지 않는 글자들이 있는 걸 볼 수 있습니다. 이를 사용해서 특정 숫자의 개수를 빠르게 판별할 수 있지 않을까요? 네, 됩니다. 심지어, 이 방식으로 10개의 숫자를 모두 정할 수 있습니다. 아래는 각 숫자의 개수를 찾기 위해 사용한 표이며, 이 순서대로 볼드체 처리한 글자를 사용해서 개수를 세주면 됩니다. 0 E O R Z 2 O T W 4 F O R U 6 I S X 8 E G H I T 3 EE H R T 5 E F I V 7 EE N S V 1 E N O 9 E I NN 답이 없는 경우는 문제에서 제외해줬으니 위 방식대로 개수를 신나게 구해주면 됩니다. int cnt[130],..