전체 글 (35) 썸네일형 리스트형 BAPC 2017 어젯밤에 비요뜨랑 같이 BAPC 2017 셋을 돌았다. 그냥 적-절해보여서 들고 왔는데 풀 때는 힘들었다. 그리고 셋 만들 때 순서를 잘못 만들어서 M번 Manhatten Mornings가 H번으로 가버렸으니 양해부탁드립니다. https://gunwookim.tistory.com/10 결과. F. Falling Apart (gunwookim,3분) 비요뜨가 슥삭해서 나는 풀이는 모른다. B. Amsterdam Distance (urd05,20분) 식을 세워보면 (r*(y좌표 차이)/n+min(r*PI*(y좌표중 작은 것)/n*(x좌표 차이)/m,2*r*(y좌표 중 작은 것)/n)이다. 예제도 안 돌려보고 직선으로 가는 게 더 빠른 케이스를 고려하지 않아서 1틀했다. D. Detour (urd05,103분.. 수열과 쿼리 25 풀이+시간복잡도 증명 수열과 쿼리 25. 크기 n의 배열이 존재하고, 쿼리는 3개가 존재한다. 1. l r x가 주어지면 구간 (l,r)에 x를 and 연산한다. 2. l r x가 주어지면 구간 (l,r)에 x를 or 연산한다. 3. l r x가 주어지면 구간 (l,r)에 있는 원소들의 최댓값을 출력한다. 1 2020 3/17 problem solving 오늘도 간략하게. Ice Skates 홀의 결혼정리가 동원된다. 홀의 결혼정리를 간략하게 설명하자면, 이분그래프가 존재할 때 그 이분그래프에서 최대매칭이 존재하는 것의 필요충분조건은 이분그래프 한쪽의 모든 부분집합에 대해서 그 크기가 그들과 접한 다른 쪽 부분집합의 크기보다 작거나 같다는 것이다. 그러면 모든 1 3/16 problem solving 가끔씩 푼 문제를 간략하게 정리해보는 것도 괜찮을 거 같다. 아주 간략히. 반 나누기 있는 간선을 다 없애고, 없는 간선을 다 만들어보자. 그리고 문제를 다시 해석하면, '다른 반 학생들 사이에는 간선이 없어야 된다.'라고 할 수 있다. 그러면 답은 이 그래프에서의 컴포넌트 개수와 컴포넌트 크기들임을 알 수 있다. 하지만 간선이 O(N^2)개라 탐색을 하기 힘든데, 제외되는 간선을 넣어놓고 적절히 set과 upper_bound로 BFS 돌아주자. 시간복잡도는 O(ElogV). Ridges and Valleys 먼저 컴포넌트 단위가 아닌 한 정점마다 생각해주자. 각 정점마다 그 정점보다 높은 정점과 접하지 않으면 ridge, 그 정점보다 낮은 정점과 접하지 않으면 valley 형태라 해주자. 같은 높이의 .. Baby-step Giant-step 알고리즘 https://platter.tistory.com/7 백준 7936번 N의 존재 풀이 http://boj.kr/7936 7936번: N의 존재 문제 양의 정수 m과 소수 p, 그리고 p로 나누었을 때의 나머지 a가 주어진다. 이때, nn + nm을 p로 나눈 나머지가 a가 되는 양의 정수 n이 존재하는지를 구하고, 존재하면 n.. platter.tistory.com 어제 이 문제에 대한 풀이를 썼었다. 그러면서 이산 로그를 구하는 부분은 Baby-step Giant-step 알고리즘으로 쉽게 구할 수 있다 했는데, 이번에는 이에 대해서 써보려고 한다. http://boj.kr/4357 4357번: 이산 로그 문제 소수 P(2 ≤ P < 231), 정수 B(2 ≤ B < P), 정수 N(2 ≤ N < P).. 백준 7936번 N의 존재 풀이 http://boj.kr/7936 7936번: N의 존재 문제 양의 정수 m과 소수 p, 그리고 p로 나누었을 때의 나머지 a가 주어진다. 이때, nn + nm을 p로 나눈 나머지가 a가 되는 양의 정수 n이 존재하는지를 구하고, 존재하면 n을 구하는 프로그램을 작성하시오. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 첫째 줄에는 테스트 케이스의 개수 d (1 ≤ d ≤ 300)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 세 정수 p, a, m이 주어진다. (2 ≤ p ≤ 109, 0 www.acmicpc.net n^n+n^m=a(modp)인 n이 존재하는지 찾고 존재한다면 그 숫자를 출력해야 한다. x=n%p,y=n%(p-1)이라 하자. n^n=x^n,n^m=x^m으로 나타낼.. BOJ 굿바이 2019 특별상을 받았다. 플4짜리 D를 50분에 뚫고 플3짜리 E를 2시간동안 못 푼 굿바이 BOJ 2019 대회. 제 실력조차도 발휘하지 못한 대회였다. 하지만 그 대회에서 나는 특이한 특별상을 받을 수 있었다. 그 이유는... 90분에 17등이라서라고 한다. jhnah917님의 '9'0분에 '17'등인 듯하다. jhnah917님 사랑합니다!!! 특별상은 베스킨라빈스 기프티콘이다. 한겨울이지만 달고 맛있을 것 같다. 대회 개최해주신 모든 분들께 감사합니다. 나에 대하여 이름 : 조영욱 -백준 : urd05 -코드포스 : platter (최고 레이팅 : Grandmaster,2575) -대구과학고등학교 졸업(33기), 서울대학교 컴퓨터공학부 재학(23학번) 경력 2020 2020 국제정보올림피아드 여름학교 처음반 수료 2020 한국정보올림피아드 1차대회 전체응시자부문 금상 NYPC 2020 동상 2020 한국정보올림피아드 2차대회 은상 2021 2021 국제정보올림피아드 겨울학교 처음반 수료 2021 국제정보올림피아드 국가대표 후보 2021 한국정보올림피아드 1차대회 전체응시자부문 금상 2021 한국정보올림피아드 2차대회 동상 2021 국제정보올림피아드 여름학교 계속반 수료 2022 2022 국제정보올림피아드 겨울학교 계속반 수료 2022 아시아태평양정보올림피아드 은메달.. 이전 1 2 3 4 5 다음
