전체 글 썸네일형 리스트형 2024 HCPC 출제 비하인드 대회 끝난 지 며칠은 지났는데 아직도 끝났다는 게 실감이 안 난다.체감상 11월 내내 대회 일만 한 것 같다. (기억왜곡일수도잇음) 올해 ALOHA는 봄/가을에 내부 대회를 한 번씩 열었었다. 쌓인 문제 목록 중에서 그래도 좋은 문제들을 HCPC에 내야 하니 선제는 여름방학 중에 단풍컵(가을 내부 대회) 선제하면서 같이 미리 끝내 두고, 11월부터 세팅을 시작했다. 지금 돌이켜보면 출제 일정이 좀 빠듯했는데, 인공지능 중간고사가 11월 4일이었어서 어쩔 수 없었다.. 각자 문제 세팅은 11/13일 정도까지 끝냈고, 이때부터 검수를 시작했다. 11월 1일에 BOJ 홍보 게시판 / solved.ac 디스코드에 검수자 모집 글을 올렸었는데, 생각보다 신청해주시는 분이 적어서 작년 검수진께도 DM 싹 보내고 현.. 더보기 백준 16287 Parcel https://www.acmicpc.net/problem/16287 MITM? .. 모르겠다분할 정복으로 풀었다 4개를 고르는 경우를 모두 살펴야 하는데 $O(N^2)$까지 되는 제한이다.BOJ 9007 같은 느낌으로 일단 2개를 고르는 경우를 모두 구한 뒤 이를 잘 활용해 답을 구하고 싶어진다. $w$ 범위가 너무 크지 않으니 2개를 고르는 모든 경우에 대해 고른 두 수의 합을 인덱스로 사용하는 체크 배열을 만들면 합치는 과정은 $O(N^2)$ 정도에 할 수 있다. 2개를 고른 두 경우를 합칠 때 선택한 원소가 같으면 안 되니 배열을 반으로 나누어 한 쪽에서 2개, 다른 쪽에서 2개를 선택한다는 생각을 해볼 수 있다. 반으로 나누면 한 쪽에서 4개 모두 고르는 경우는 분할 정복처럼 처리할 수 있으니 .. 더보기 백준 10070 벽 https://www.acmicpc.net/problem/10070 구간에 min, max를 적용하는 쿼리를 처리하면 된다.구간 쿼리니까 세그 박고 싶은데 먼가 잘 안 되고..무지성으로 쓰자니 쿼리 순서에 따라 답이 달라지고..세그비츠가 비슷한 연산을 지원했던 것 같기도 하고..?뇌절하지 말자 lazy propagation을 설계할 때는 한 정점에 여러 쿼리가 쌓이는 상황을 잘 생각해야 한다.같은 구간에 적용된 쿼리 중 min 쿼리는 $h$가 최대인 것만, max 쿼리는 $h$가 최소인 것만 고려하면 된다는 점은 자명하다. 고려할 min 쿼리의 $h$를 $min_h$, max 쿼리의 $h$를 $max_h$로 두자.구간에 적용된 $min_h$ $\le$ $max_h$인 경우는 문제가 되지 않고, 크기가 뒤.. 더보기 백준 2673번 교차하지 않는 원의 현들의 최대집합 http://icpc.me/2673 2673번: 교차하지 않는 원의 현들의 최대집합 평면상에 있는 원의 둘레에 100개의 점이 일정한 간격으로 시계방향으로 번호가 1, 2, ... 100으로 붙여져 있다. 이 점들을 끝점으로 갖는 N개의 선분(원의 현)이 입력으로 주어질 때, 이들중에서 서 www.acmicpc.net 풀이 원의 현이라고 하면 되게 복잡해지고 풀기 싫어집니다. 하지만 두 현의 교차 여부만 중요하다는 점을 잘 생각해 보면 현을 수평선상의 구간으로 생각해도 문제가 없다는 것을 알 수 있습니다. 두 현의 교차하려면 각 현을 나타낸 두 구간이 겹치면서 한 구간이 다른 구간에 포함되지 않아야 합니다. 아래 그림은 예제를 구간으로 나타낸 모습입니다. 여기까지 왔으면 DP로 문제를 풀 수 있습니다. .. 더보기 ABC 228 E Integer Sequence Fair 풀이 오늘 대회 중에 아쉽게 못 풀었던 문제입니다. 페르마의 소정리를 안다면 어렵지 않게 풀 수 있고, 좋은 문제인지는 잘 모르겠지만 개인적으로 이 문제를 풀며 몇 가지를 배우게 되어 정리할 겸 풀이를 작성하려 합니다. 문제 https://atcoder.jp/contests/abc228/tasks/abc228_e E - Integer Sequence Fair AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 1 이상 K 이하의 자연수가 N개 있는 모든 배열에 1 이상 M 이하의 가치를 매기는 경우의 수를 $Q = 99824435.. 더보기 백준 17106번 빙고 http://icpc.me/17106 17106번: 빙고 한 줄에 5개의 글자, 총 5줄을 출력한다. 각 줄은 순서대로 빙고판의 각 행을 나타낸다. 색칠된 칸은 "#", 색칠되지 않은 칸은 "."로 따옴표 없이 나타낸다. 예를 들어 A1, C3, C4만 색칠하려면 다음과 www.acmicpc.net 풀이 25개의 빙고 칸 각각을 색칠하거나 색칠하지 않을 수 있으므로 빙고 칸을 채우는 경우의 수는 $2^{25}$가지입니다. 모든 경우를 살펴보며 각 경우의 수마다 모든 칸이 올바르게 색칠되었는지를 체크하는 코드를 작성하면 정답을 찾을 수 있습니다. 다소 문제가 되는 칸은 B5입니다. 다른 칸들은 모두 빙고판의 상태를 통해 올바르게 색칠되었는지 알 수 있지만 이 칸은 그렇지 않습니다. B5가 참이라고 가정하고.. 더보기 백준 4828번 XML http://icpc.me/4828 4828번: XML 인터넷프로그래밍 교수 이다솜은 XML이야말로 세상을 바꿀 혁신적인 언어라고 믿으며, 항상 학생들에게 XML의 장점을 어필한다. 그러나 잘못 사용되었다가는 지구를 파괴할 수도 있는 무시무시 www.acmicpc.net 풀이 코드를 한 글자씩 읽으며 현재 상태를 저장하는 열거형 변수 now의 값과 현재 글자에 따라 적절히 처리해주었습니다. 상태가 TAG이면 태그를, AMPERSAND이면 & 다음을 읽고 있다는 의미이며 둘 다 해당되지 않는 상태는 NORMAL으로 나타냅니다. 문제가 있는 코드를 만나면 상태를 ERROR로 지정하고 읽기를 중단합니다. 코드를 모두 읽은 후 context 스택이 비었는지, 아직 태그나 & 뒤를 읽고 있는지 여부를 추가적으로 .. 더보기 신기한 정렬 알고리즘 생활코딩에서 신기한 정렬 알고리즘을 접했습니다. 이게 왜 되지? 싶지만 놀랍게도 오름차순으로 잘 정렬됩니다!! 논문 링크도 있길래 읽어 보았습니다. 아래는 위 논문을 참고한 알고리즘 정당성 증명입니다. 초기 배열에 같은 수가 없다고 가정하고 작성했지만, 있어도 큰 차이는 없습니다. 정당성 증명 위 알고리즘을 그대로 구현하고, 과정을 확인하기 위해 swap 직후마다 배열 전체를 출력하는 코드를 추가했습니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include using namespace std; int arr[1000]; void print(int* a, int n) { for (int i = 1; i 더보기 이전 1 2 3 4 다음
