m개의 원소를 조건에 맞게 n개의 원소에 배치하는 방법

C - Kaiten Sushi  C - Kaiten SushiAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp  i번째 사람의 미각 점수는 A[i]로 주어지고, j번째 초밥은 맛 점수가 B[j]로 주어진다. j = 1,2,..,m번 초밥이 1번부터 n번 사람에게 순서대로 주어지는데 A[i]  각각의 초밥이 어떤 사람에게 먹어지는지 결정한다. n,m  예를 들어 A = [3,8,2], B = [5,2,1]인데 B[0] = 5가 1번 사람에게 주어질때, A[0]  B[1] = 2가 1번 사람에게 주어지는데, A[0] > B[1]..

  • format_list_bulleted 애드 혹 알고리즘
  • · 2024. 12. 2.
  • textsms

재배열 부등식(rearrangement inequality)을 이용한 내적의 최대 최소

1. 재배열 부등식(rearrangement inequality) 실수 x11,2,..,n의임의의순열\sigma_{1}, \sigma_{2}, ... , \sigma_{n}으로부터x1yn+x2yn−1+...+xny12.증명S1 = x_{1}y_{1} + x_{2}y_{2} + .... + x_{a}y_{a} + .... + x_{b}y_{b} + ... + x_{n}y_{n}에서y_{a}  S2=x1y1+x2y2+...+xayb+...+xbya+...+xnyn 둘을 뺴면 $S1 - S2 = x_{a}(y_{a} - y_{b}) + x_{..

  • format_list_bulleted 그리디 알고리즘
  • · 2024. 11. 22.
  • textsms
그래프 전파 모형3 - 전파 최대화 문제(influence maximization)

그래프 전파 모형3 - 전파 최대화 문제(influence maximization)

1. viral marketing 소비자들로 하여금 상품에 대해 긍정적인 입소문을 내게하는 기법 효과적으로 상품 정보가 소비자들에게 알려질려면 소문의 시작점이 중요하다. 시작점에 따라 입소문이 전파되는 범위가 달라지기 때문이다.  2. importance of seed set SNS 인플루언서들이 높은 광고비를 받는 이유가 있다. 전파 모형에서 첫 시작점을 seed set이라고 부르는데 viral marketing에서는 이 시작점을 잘 선택해야 광고 효과를 극대화할 수 있다.   케이트 미들턴을 광고 모델로 선택했더니 판매량이 급증했다 선형 임계치 모형에서도 seed set의 중요성을 볼 수 있는데 처음에 u와 v를 선택했을 때 총 9명(7명 전파)이 A를 선택했다.    만약 위 모형에서 다음과 같이 ..

  • format_list_bulleted Graph
  • · 2024. 9. 2.
  • textsms

기간 제한이 있는 과제들에서 최대 가치를 얻는 그리디 알고리즘

13904번: 과제 (acmicpc.net) 과제의 기간 제한이 있고 해당 과제를 수행했을 때 얻는 가치가 서로 다르다 하루에 하나씩 과제만 처리할 수 있다. 주어진 과제들을 적절히 처리해서 최대 가치를 구한다면? --------------------------------------------------------------------------------------------------------------------------- 처음에는 과제 점수가 높은 순서대로 내림차순 정렬해서 현재 날짜랑 비교해서 처리할 수 있는 과제면 일단 가져가고 날짜랑 비교했을 때 처리할 수 없는 과제면.. 지금까지 가져간 과제들 비교해서... 실제 처리할 수 있는지 체크해보는것? 4 604 401 202 503 304 1..

  • format_list_bulleted 그리디 알고리즘
  • · 2024. 6. 4.
  • textsms

1부터 n까지 각각 1번씩 정확히 k개의 정수만 사용해서 합을 s로 만드는 그리디 알고리즘

19177번: Klothes (acmicpc.net) 1부터 n까지의 자연수 중에서 각각 1번씩만 사용하고, 정확히 k개의 정수만 사용해서 합을 s로 만드는 방법을 찾는 문제 n이 40000까지이고 테스트케이스가 8000개이다 보니 단순한 방법보다는 O(N)정도에 하나는 해결해야  만약 s가 가능한 범위를 벗어난다면 일단 만들수가 없다. s의 최솟값은 1부터 k까지 합 s의 최댓값은 n-k+1,n-k+2,...,n까지의 합 만약 s가 (1부터 k까지 합)   반대로 이 범위 안이라면 확실하게 만들 수 있다는 것이 보장된다. (1부터 k까지의 합) = a (n-k+1,...,n까지의 합) = b라고 할 때, a,a+1,a+2,..,b-1,b까지의 모든 정수는 반드시 만들 수 있다. 어떤 정수는 안되는게 있..

  • format_list_bulleted 그리디 알고리즘
  • · 2024. 5. 29.
  • textsms
ABC349 D번 복기 - log를 구하는 가장 정확한 방법 - math.log를 기피해야하는 이유

ABC349 D번 복기 - log를 구하는 가장 정확한 방법 - math.log를 기피해야하는 이유

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=2k(j),ri=2k(j+1)을 만족해야한다. 접근은 상당히 잘 했다 현재 시점 L을 기준으로 L=2kj를 만족하는 모든 k를 먼저 찾는다. 이거는 L이 2로 나누어 떨어지면,..

  • format_list_bulleted Python
  • · 2024. 4. 14.
  • textsms