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

문자열 수를 10진법으로 바꾸는 테크닉2 - n을 n번 이어붙인 정수

D - 88888888 (atcoder.jp) D - 88888888AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp  n을 n번 이어붙였을때, 그것을 998244353으로 나눈 나머지를 구하는 문제 숫자를 이어붙인 문제는... 한번 10진법으로 바꿔보면 해결법이 보이는 경우가 있다 https://deepdata.tistory.com/1235 문자열 수를 10진법으로 바꾸는 테크닉 - 배열에서 모든 가능한 순서쌍의 두 수를 이어붙여 만든D - Another Sigma Problem (atcoder.jp) D - Another..

• format_list_bulleted 애드 혹 알고리즘
• · 2024. 9. 8.
• textsms

특정한 정점들을 반드시 포함하는 최소 정점 트리 만들기 - list말고 반드시 set을 사용해야하는 경우

https://atcoder.jp/contests/abc368/tasks/abc368_d D - Minimum Steiner TreeAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp  1부터 n까지 번호를 가진 정점을 가진 트리에서 어떤 정점들을 제거할때, 특정한 정점 v1,v2,...,vk를 반드시 포함하게 하는 트리를 만들고 싶다면, 그러한 트리의 최소 정점 수는? 예를 들어 왼쪽 트리에서 1,3,5를 반드시 포함하는 트리를 만들고 싶을때, 4번, 6번, 7번을 제거하면 된다     사실 테크닉에 감탄해서 복기하는거긴 한..

• format_list_bulleted 애드 혹 알고리즘
• · 2024. 8. 31.
• textsms

n개의 구간 각각에서 어떤 정수들을 골라 합해 0을 만들 수 있는가?

https://atcoder.jp/contests/abc362/tasks/abc362_c C - Sum = 0AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp  n개의 구간 (Li,Ri)가 주어질때, 이 구간들 각각에서 정수 Xi를 하나 골라 n개 합쳐서 0을 만들 수 있는지? 그렇다면 그러한 정수 배열을 하나 찾는 문제 먼저 그러한 정수 배열이 존재하는지 알 수 있을까? 이것부터 어렵더라고 근데 생각보다 간단했다  $$L_{1}$$ L_{2}  ...  $$L_{n}  이들을 합해도 부등식이 유지되므로,$$ \sum_{i =..

• format_list_bulleted 애드 혹 알고리즘
• · 2024. 8. 24.
• textsms

겹치는 직선 구간쌍의 개수 빠르게 세기

D - Intersecting Intervals (atcoder.jp) D - Intersecting IntervalsAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp  50만개의 구간 [l,r]이 주어질때, 이들 중 서로 겹치는 구간 쌍의 개수가 몇개인지 구하는 문제 모든 구간 쌍에 대해 서로 겹치는지 조사할려면 $O(N^{2})$인데, 당연히 N이 최대 50만이므로 시간제한에 맞지 않는다 전체 구간 쌍의 개수는 n개중 2개를 선택하는 경우의 수이므로, nC2 = n(n-1)/2 만약 서로 겹치치 않는 구간 쌍의 개수를 구..

• format_list_bulleted 투 포인터 알고리즘
• · 2024. 8. 2.
• textsms

index와 value를 바꾸는 다이나믹 프로그래밍 트릭

E - Maximum Glutton (atcoder.jp) E - Maximum GluttonAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 단맛이 a 짠맛이 b로 주어지는 n개의 음식을 먹는데  단맛이 x를 초과하거나 짠맛이 y를 초과하는 순간 음식을 그만 먹는다면 음식을 최대한 많이 먹고자할때, 최대로 먹을 수 있는 음식의 수는? 전형적인 배낭 문제라서 dp[i][j][k] = i번째 음식까지 먹었을때 단맛의 합이 j, 짠맛의 합이 k인 경우 먹은 최대 음식의 수로  하면 될것 같다고 생각을 했는데 n이 80이고 a가 ..

• format_list_bulleted 다이나믹 프로그래밍
• · 2024. 7. 29.
• textsms