F - Double Sum (atcoder.jp) F - Double SumAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 문제는 매우 간단하다 A1,A2,A3,...,AN이 주어지면, $$\sum_{i = 1}^{n} \sum_{j = i+1}^{n} max(A_{j} - A_{i},0)$$을 구하는 문제 n제한이 40만이라 단순하게 풀면 당연히 시간초과... 1. max(a,b) = (|a-b| + a+b)/2 방법은 많이 있던데 아주 간단하고 경이로운 솔루션이 있어서 복기해본다 배열 A에 대한 함수 f를 다음과 같이..
D - New Friends (atcoder.jp) D - New Friends AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 문제를 요약하자면... 어떤 노드 X에서 직접적으로 연결되어 있지는 않지만, 다른 노드들을 거쳐서 도달할 수 있는 노드 Z가 존재한다면 그러한 경로의 개수를 구하는 문제 예를 들어 위 그래프에서 1번 노드에서 2,4번은 직접 연결되어 있고, 3번 노드는 직접 연결되어 있지 않은데, 1 > 2 > 3으로 갈 수 있으므로 1개 2번 노드에서 1,3번은 직접 연결되어 있는데 4번은 직접 연결되어 있지..
https://atcoder.jp/contests/abc349/tasks/abc349_d D - Divide IntervalAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp L부터 R-1까지 연속된 정수 수열이 주어질때, 이 수열을 최소 개수의 구간으로 나눌려고 한다 L $li = 2^{k}(j), ri = 2^{k}(j+1)$을 만족해야한다. 접근은 상당히 잘 했다 현재 시점 L을 기준으로 $L = 2^{k}j$를 만족하는 모든 k를 먼저 찾는다. 이거는 L이 2로 나누어 떨어지면,..
https://atcoder.jp/contests/abc348/tasks/abc348_d D - Medicines on Grid AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 문제 자체는 어디서나 많이 보던 기본적인 BFS/DFS 셋팅이다 2차원 맵에 특정 위치에 약이 있는데, 이 약을 먹으면 에너지가 E로 된다. 이동할때마다 에너지가 1씩 감소한다 약은 먹어도 되고 먹지 않아도 되는데, 단 1번만 먹을 수 있고 먹으면 사라진다 에너지 0부터 시작한다고 할때, 목표로 하는 지점에 도착할 수 있는가? 그냥 기본적인 BFS..
E - Insert or Erase (atcoder.jp) E - Insert or Erase AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 수열 A의 원소들이 모두 서로 다른 원소이며, 삽입하는 연산과 삭제하는 연산을 수행한다. 연산을 수행할 때마다 A의 원소들은 모두 서로 다르다는 것이 보장된다. 연산은 2가지이다. x 원소 바로 뒤에 y를 삽입하는 연산 x를 삭제하는 연산 연결리스트로 접근해야지 생각하긴 했는데... x를 어떻게 바로 찾아야 하나 고민하다가 실패했다.. 연결리스트는 접근하는데 O(N)이라서.. 분명..
1. 문제1 https://atcoder.jp/contests/abc341/tasks/abc341_d D - Only one of two AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이 n,m,k가 주어지는데 n이나 m중 어느 하나만으로 나누어 떨어지는 정수들을 오름차순 정렬할때, k번째로 작은 양의 정수를 찾는 문제 예를 들어 n = 2, m = 3, k = 5이면 2,3,4,8,9,10,...은 각각 2나 3중 어느 하나만으로 나누어 떨어지는 정수들이다. 4는 2로 나누어 떨어지지만 3으로 나누어 떨어지지 ..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
