본문 바로가기

전체 글

 (147)
Good Bye 2022: 2023 is NEAR Dashboard - Good Bye 2022: 2023 is NEAR - Codeforces codeforces.com A - Koxia and Whiteboards 매번 정렬하면서 가장 작은 수를 대체하면 된다. 00:03 AC 정해에서는 마지막 수는 항상 남는다는 점을 이용한다. 따라서 마지막 수를 제외한 (N + M - 1)개의 수를 정렬한 후 상위 (N - 1)개의 수와 마지막 수를 선택하면 된다. B - Koxia and Permutation 1 N 2 (N - 1) 3 ... 00:07 AC C - Koxia and Number Theory 동일한 수가 존재한다면 x는 존재하지 않는다. 00:09 WA 추가적인 조건이 필요하다. 모든 a_i와 소수 p에 대하여 a_i % p의 빈도를 세자. ..
Codeforces Round #841 Dashboard - Codeforces Round #841 (Div. 2) and Divide by Zero 2022 - Codeforces codeforces.com 서론 난이도에 비하여 상당히 오래 걸렸다. A - Joey Takes Money 수 하나에 몰아주면 된다. 00:03 AC B - Kill Demodogs 수학 00:12 AC C - Even Subarrays 전체 경우에서 약수의 개수가 홀수인 경우를 빼는 것이 더 간편하다. 약수의 개수가 홀수인 수는 제곱수이다. 그리고 문제의 제한에 의하여 가능한 제곱수는 512개이다. 따라서 각 인덱스에 대하여 pxor을 구한 후 최대 512개의 원소만 순회하면 된다. 00:39 TLE map 대신 배열을 사용하도록 하였다. 00:43 RTE 인덱..
2022 제1회 미적확통컵 2022 제1회 미적확통컵 www.acmicpc.net A - 연속인가? ? 단순 수학 00:01 AC B - 수열의 극한값 정리하면 b와 c만으로 구성된 공식이 나온다. 00:09 AC G - 균등분포와 정규분포 0 또는 1에 가까운 값의 개수를 세면 된다. 00:18 AC H - 방향 정하기 한 점씩 결정해나간다고 생각하면 매우 단순한 공식이 나온다. 00:23 AC I - 빙고 기댓값의 선형성을 이용하여 잘 계산하면 된다. 00:51 AC C - 함수와 최소 스패닝 트리 모든 간선에 대하여 a는 동일하므로 간선의 가중치는 일차함수로 생각할 수 있다. 이때 두 일차함수의 교점에서 두 간선의 우열 관계가 뒤집히게 된다. 모든 교점에 대하여 적분값을 나누어서 계산해주면 된다. 분수 계산이 자주 등장하므로..
GBS Coding Contest 2022 Open GBS Coding Contest 2022 Open www.acmicpc.net A - 성장의 비약 선택권 case work 00:03 AC C1 - 물정수열 그리디하게 최대한 작은 값을 선택하면 된다. 현재 값을 x라고 하면 다음 값은 max(x + 1, minv)가 된다. 00:21 AC B1 - 알프스 케이블카 H의 제한이 작으므로 dp가 가능하다. 00:39 AC 정해는 그리디이다. 모든 a < b < c에 대하여 선분 (a, b), (b, c), (c, a)는 둔각삼각형을 이룬다. 따라서 모든 인접한 산에 대하여 와이어를 설치하는 것이 이득이다. D1 - 그램팬 조건을 만족하는 A와 Z의 개수를 잘 세주면 된다. 00:49 AC D2 - 팬램그 A와 Z의 개수가 모두 i개인 그램팬을 그리디하게 ..
Zero One Algorithm Contest 2022 Open Contest Zero One Algorithm Contest 2022 Open Contest www.acmicpc.net A - ZOAC 5 단순 구현 00:01 AC B - 전투의 신 수학 00:05 AC C - 황금 칵테일 map와 map 00:09 WA map 사용이 미숙하였다. 존재하지 않는 key에 [] 연산자를 사용하면 (key, default value) pair가 삽입되므로 주의해야 한다. 00:13 AC D - 이 사람 왜 이렇게 1122를 좋아함? 이분 탐색 00:18 WA 중간에 답이 정해지더라도 마지막까지 모순이 생기지 않는지 확인해야 한다. 00:29 AC E - 색종이와 공예 ㄱ자 모양이 등장하는지 확인하면 된다. 각 좌표당 4번씩만 검사하면 flood fill 없이 해결할 수 있다. 00:..
제1회 곰곰컵 제1회 곰곰컵 www.acmicpc.net 서론 그냥 어쩌다 보니 풀었다. A - 치킨댄스를 추는 곰곰이를 본 임스 단순 수학 B - 인사성 밝은 곰곰이 set C - 곰곰이의 식단 관리 수학 D - 결전의 금요일 dp E - Yes or yes dfs F - 숲속에서 새 구경하기 처음에는 Segment Tree로 풀었는데 더 쉬운 풀이가 존재한다. 답이 t라는 것은 새 3마리 중 적어도 1마리가 시점 t에 등장하였다는 것을 의미한다. 따라서 새 3마리에 대하여 lcm(Av, Bv, Cv) 미만의 시점 중 주기의 시작점만 고려하면 된다. bfs를 이용한 더 빠른 풀이가 존재하지만 설명은 생략한다. G - 합주단 곰곰 두 단원이 식사를 할 확률은 1 / K이다. 따라서 답은 N * (N - 1) / 2 /..
2022 서울사이버대학교 프로그래밍 경진대회 (SCUPC) 2022 서울사이버대학교 프로그래밍 경진대회 (SCUPC) www.acmicpc.net A - 빅데이터? 정보보호! N과 문자열의 길이만 보면 된다. 00:02 AC B - 멘토와 멘티 정렬 00:04 AC D - 은?행 털!자 1 map과 T - X 00:09 AC C - 비즈네르 암호 해독 구현 00:17 AC E - 은?행 털!자 2 D번과 유사하게 접근하면 된다. upper_bound로 T - X 이하인 원소를 찾아준다. 그리고 순회하면서 필요 없는 원소는 적절히 지워주면 된다. 00:27 AC G - 최빈값과 쿼리 전혀 다른 문제이지만 E번과 유사하게 접근하면 된다. 먼저 x가 K번 등장하는 연속된 부분 수열을 모두 찾자. 이때 수열은 x로 시작해서 x로 끝나야 한다. 전처리를 마친 후 offl..
Codeforces Round #838 Dashboard - Codeforces Round #838 (Div. 2) - Codeforces codeforces.com A - Divide and Conquer 합이 짝수라면 답은 0이 된다. 그렇지 않다면 각 인덱스마다 parity가 변하기 위한 최소 연산 횟수를 구하면 된다. 00:02 AC B - Make Array Good x 제한을 무시하고 풀었다. x 제한이 없다면 전부 maxv로 만들면 된다. 00:05 WA 모든 수를 가장 가까운 2의 제곱으로 만들면 된다. 00:12 AC C - Binary Strings are Fun 순차적으로 보면 된다. 이전 수와 현재 수가 동일하다면 경우의 수는 2배 증가한다. 그렇지 않다면 경우의 수는 1이 된다. 00:26 WA 모듈러 연산을 빼먹었다...

티스토리툴바