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

n번째로 작은 팰린드롬 수를 찾는 놀라운 방법

https://atcoder.jp/contests/abc363/tasks/abc363_d D - Palindromic NumberAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp  n이 최대 10^18까지라서 보통의 방법으로는 찾을 수 없다는 것이 느껴진다 그래서 일단 가능한 팰린드롬 수를 차례대로 나열해본다 0,1,2,3,4,5,6,7,8,9 >>> 10개 11,22,33,44,55,66,77,88,99 >>> 9개 101, 111, 121, 131, 141, ... ,191202,212,222,232,..., 292303..

• format_list_bulleted 알고리즘/애드 혹 알고리즘
• · 2024. 7. 23.
• textsms

배열에서 일부를 골라 공차가 매우 큰 등차수열이 되도록 만드는 방법의 수

E - Count Arithmetic Subsequences (atcoder.jp) E - Count Arithmetic SubsequencesAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp  배열 A에서 일부를 골라 길이가 i = 1,2,3,..,n인 등차수열을 만드는 방법의 수를 각각 구하는 문제 dp[i][j][d]을 길이가 j이고 공차가 d이며 등차수열의 끝 항이 A[i]인 등차수열을 만드는 방법의 수라고 해보자. 길이가 j-1이고 끝항이 A[k], k = 0,1,2,..,i-1인 모든 등차수열을 조사하여 A[i] ..

• format_list_bulleted 알고리즘/다이나믹 프로그래밍
• · 2024. 7. 15.
• textsms

트리에서 임의의 노드에서 모든 노드를 적어도 1번 이상 방문하는데 걸리는 최소 거리

E - Tree and Hamilton Path 2 (atcoder.jp) E - Tree and Hamilton Path 2AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp  트리의 어떤 정점 A에서 출발하여 모든 정점을 1번 이상 방문하고, 다시 정점 A로 돌아온다고 생각해보면, 만약 트리의 어떤 변을 제거하면 다음과 같이 2개의 연결성분이 생기고 출발점에서 다시 출발점으로 돌아올려면 두 연결성분을 서로 왔다갔다 해야하므로, 정확히 각 변을 2번 지나면 출발점에서 모든 노드를 1번 이상 방문하여 출발점으로 돌아올 수 있다..

• format_list_bulleted 알고리즘/DFS BFS 정복기
• · 2024. 7. 11.
• textsms

다이나믹 프로그래밍으로 구하는 복수순열2 - 주어진 개수의 알파벳들만으로 만들 수 있는 문자열의 개수

E - Alphabet Tiles (atcoder.jp) E - Alphabet TilesAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp  대문자 알파벳 A,B,C,..,Z의 개수가 주어질때, 이들로 만들 수 있는 길이 1부터 k까지 모든 문자열의 개수를 구하는 문제 길이가 s일때, 각각 A,B,C,...,Z 문자가 a1,a2,a3,...,a26개 있다고 한다면.. 이들을 일렬로 배열하는 복수순열의 개수와 같으므로,  $$\frac{(a1+a2+a3+...+a26)!}{a1!a2!...a26!} = \frac{s!}{a1!..

• format_list_bulleted 알고리즘/다이나믹 프로그래밍
• · 2024. 6. 20.
• textsms

다항식의 곱으로 구하는 복수순열1 - 주어진 개수의 알파벳들만으로 만들 수 있는 문자열의 개수

E - Alphabet Tiles (atcoder.jp) E - Alphabet TilesAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp  대문자 알파벳 A,B,C,..,Z의 개수가 주어질때, 이들로 만들 수 있는 길이 1부터 k까지 모든 문자열의 개수를 구하는 문제 길이가 s일때, 각각 A,B,C,...,Z 문자가 a1,a2,a3,...,a26개 있다고 한다면.. 이들을 일렬로 배열하는 복수순열의 개수와 같으므로,  $$\frac{(a1+a2+a3+...+a26)!}{a1!a2!...a26!} = \frac{s!}{a1!..

• format_list_bulleted 조합론
• · 2024. 6. 18.
• textsms