import copy import bisect max_win=0 max_win_dice=None def cal2(k, num, a, dice, ret): if k==len(a): ret.append(num) return for i in range(6): cal2(k+1,num+dice[a[k]][i],a,dice,ret) def cal(a,b,dice): a_num_list=[] cal2(0,0,a,dice,a_num_list) b_num_list=[] cal2(0,0,b,dice,b_num_list) b_num_list.sort() cnt=0 for i in a_num_list: cnt+=bisect.bisect_left(b_num_list,i) return cnt def select(k, dice, ..
lower_bound lower_bound 함수는 오름차순으로 정렬된 원소들에 key를 삽입하고자 할 때 가능한 가장 왼쪽 인덱스를 구하는 함수이다. key=10 1 9 10 10 10 11 12 이는 조건이 x>=key인 결정 문제에서 결정 문제의 답이 참인 가장 작은 인덱스를 찾는 것과 같다. 이 결정 문제에 대해 각각의 원소의 답은 다음과 같다. F F T T T T T 1 9 10 10 10 11 12 upper_bound upper_bound 함수는 오름차순으로 정렬된 원소들에 key를 삽입하고자 할 때 가능한 가장 오른쪽 인덱스를 구하는 함수이다. key=10 1 9 10 10 10 11 12 이는 조건이 x>key인 결정 문제에서 결정 문제의 답이 참인 가장 작은 인덱스를 찾는 것과 같다. ..
왠지 treedp로 풀 수 있을 것 같은 강렬한 기운이 느껴졌다. 밑의 예제 그림을 보자. A에서 시작해서 정점 B에서 정점 D와 이어진 정점들을 쭉 방문한 후 정점 C를 방문하려고 한다.1번의 탐색으로 해결하려면 B에서 C를 방문할 때 D의 가중치합, E의 가중치합이 업데이트되어야 한다. 탑다운dp로 구할 수 있는 것은, E에서의 답, E에서의 답으로 구할 수 있는 D에서의 답, C에서의 답, E,D,C에서의 답으로 구할 수 있는 B에서의 답..이므로 탐색 1번으로는 해결할 수 없다. 다만 탐색 1번을 통해 구할 수 있는 것들 중 하나인, 각 정점을 루트로 하는 서브트리에서 해당 정점에서의 가중치합은 단 한 가지 경우 문제에서 요하는 진짜 해답과 일치한다. 바로 탐색를 시작한 정점 A에서이다. 또한 A..
이분탐색/투포인터 문제이다 이 문제에 나오는 정수들의 범위를 구하여 자료형을 정해 보자 우선 풀이는 다음과 같다 풀이 설명: 입력을 psum으로 저장한다음 psum으로부터 가능한 조합을 저장, 정렬, 둘이 더해서 값이 T인 경우의 수를 구함 시간복잡도는 이분탐색의 경우 O(n1^2*logn2), 투포인터의 경우 O(n1^2)이다. (n1=min(n,m), n2=max(n,m)) 이분탐색 풀이(lower bound, upper bound이용) #include using namespace std; #define fastio ios::sync_with_stdio(false),cin.tie(0) int32_t T, n,m,psum_a[1001],psum_b[1001]; vector a,b; map numOfX;..
문제 자체보다 trace를 출력하는 것이 관건인 문제이다 최댓값을 구하는 과정에서 trace또한 메모해놓으면 dfs 한번으로 답을 도출할 수 있지만 그렇게 한다면 메모리 초과를 받을 것이다 답을 구한 다음에 다시 탑다운으로 dp테이블을 봐가면서 적용되었던 값들을 추적하여 출력하면 된다. 다음은 전체 코드이다.#include using namespace std; #define MIN -10001 #define fastio ios::sync_with_stdio(false),cin.tie(0) vector adj_list[200001]; int n,score[200001], dp[200001][2]; int dfs(int v,bool flag){ if(dp[v][flag]!=MIN) return dp[v][f..
https://www.acmicpc.net/problem/1967 이문제를 풀어보라고 하면 구글검색을 한다음에 koosaga님의 dfs두번 돌리는 풀이를 보고 따라 해결한 다음 해결했습니다 하는 사람이 많아서 풀이를 적어보게 되었다 부모 노드에서의 답이 자식 노드에서의 답을 포함하므로 treedp로 풀어야겠다라고 생각할 수가 있다. 루트는 아무거나 루트로 해도 된다. dp[v]는 v를 루트로 하는 서브트리에서 v에서 리프노드까지의 경로들 중 최댓값이다. // U는 v의 자식 노드의 집합 OPT(V) = max(OPT(u)+cost(v,u)) u∈U int dfs(int v, int p){ int longest=0; for(auto [u,cost]: adj_list[v]){ if(u==p) continue..