뉴비의 PS 낙서장

Codeforces Round #640 (Div. 4) 처음으로 Div. 4를 쳐봤다. 풀이를 간략하게 적어보겠다! A - Sum of Round Numbers 그냥 분리하면 된다. 너무 쉬우니 코드는 올리지 않겠다. B - Same Parity Summands 적당히 케이스 분류를 하면 된다. i) 모두 1을 채워 넣고 나머지 한개에 몰아 넣기 ii) 모두 2를 채워 넣고 나머지 두개에 몰아넣기 #include #pragma gcc optimize("O3") #pragma gcc optimize("Ofast") #define x first #define y second using namespace std; typedef long long ll; typedef unsigned long long ull; ..

플랫이랑 코포가 언레되는걸 보고 1시간 반짜리 플레 3문제를 돌기로 했다. A - 티켓 (?, ?분) 너무 어려워서 못풀었다. B - 천상용섬 (gunwookim, 17분) dp점화식을 세웠다. dp[i][j] : i번째 물체를 높이 j로 잘랐을때 나올 수 있는 경우의 수 이제 최적화(?)를 진행해보자 최적화1 - O(NH^2) 모든 방법을 하나하나 해본다. 최적화2 - O(280NH) 1부터 100만까지의 수중에 약수의 최대 갯수는 280개 이므로, O(NH)번 만큼 돌면서 그 전의 높이의 약수만 보면 된다. 약수를 빠르게 구하는 방법은 sqrt(N)방법으로, 미리 전처리를 해둔다. 최적화3 - O(280^2N) 이번엔 O(NH)번 만큼 도는게 아니라 i번째 물체의 높이도 약수만 보면 된다는 것을 알 ..

이번엔 엡실론, 플랫과 셋이서 BAPC 2016 을 쳤다. [플랫 블로그] L - Sticky Situation (gunwookim, 3분) 두번 뇌절을 했다. (흙흙) 정렬 후 인접한 3개에 대해 삼각형이 만들어지는지 판별한다. #include #pragma gcc optimize("O3") #pragma gcc optimize("Ofast") #define x first #define y second using namespace std; typedef long long ll; typedef pair pi; int n; ll a[20005]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n; for(int i = 1;i > a[i..

놀고만 있던 저에게 urd05가 셋을 돌자고 제안을 했다. 그 셋은 바로 BAPC 2017 같이 푸는거라 그나마 재미가 더 있었다! 5시간동안 했는데, 너무 힘들었다. (오랜만에 몇시간 연속으로 코딩..) 간략하게 내가 아는 풀이를 적어보겠다! B - Amsterdam Distance 15003번: Amsterdam Distance Your friend from Manhattan is visiting you in Amsterdam. Because she can only stay for a short while, she wants to see as many tourist attractions in Amsterdam in as little time as possible. To do that, she need..

오랜만에 앳코더를 봤다. 그럭저럭 본것 같다. (안친 사이에 실력이 꽤 늘었다) 간략하게 풀이 설명을 한다! A 번 문제 A~B 사이에 K의 배수가 있는지 없는지 판별하는 문제다. B/K - (A-1)/K 가 0인지 아닌지 판별하면 된다. #include using namespace std; int n; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n; int a,b; cin >> a >> b; cout > x; while(g m >> Q; for(int i = 1;i > q[i].a >> q[i].b >> q[i].c >> q[i].d; } a[0] = 1; dfs(1..

세 용액은 여러가지 풀이가 있습니다 1. 트리를 이용한 풀이 2. 이분탐색을 이용한 풀이 3. 양방향 탐색을 이용한 풀이 이 블로그에서는 양방향 탐색을 이용한 풀이 입니다. \(N\) 번을 돌면서 하나를 고정시키고 나머지 두개를 양방향 탐색으로 찾는 풀이입니다. 시간복잡도는 \(O(n^{2})\) 입니다. #include using namespace std; /// 풀이 : 하나를 고정시키고 나머지 두개를 양방향 탐색으로 찾을거에요! int n; long long a[5005]; int main() { cin >> n; for(int i = 1;i > a[i]; } sort(a+1,a+n+1); /// 정렬을 해야 가능해요! int idx1 = n-2,idx2 = n-1,idx3 = n; /// 여기에 ..

Mo's algorithm 을 사용하는 문제다. 와아아아아아아앙 짝짝짝짝 각 숫자마다 list로 관리하면서 (dq[i].front-dq[i].back) 의 값이 숫자 i 의 최대 길이이다. 이제 이 숫자 i의 최대길이를 O(k) 가 아닌 O(sqrt(K)) 에 구해아 한다. 이 방법은 최대길이를 관리하는 버킷을 만들어서 sqrt(K) 개로 쪼갠다음 각 구간을 관리한다. 이러면 제일긴 길이 를 찾는방법을 O(sqrt(K)) 만에 구할 수 있다. 자세한건 코드를 보자. #include using namespace std; list dq[300005]; int n,k,Q,val,sz; int ans[300005],a[300005]; int b[300005],cnt[5000005]; struct Query { ..

\(DP[N] : N\)번째 징검다리를 건널때 나올 수 있는 경우의 수 라고 잡아보면 \(DP[N] = DP[N-1]+DP[N-2]+...+DP[1]\) 이라는 식이 나오는데 \(DP[N-1] = DP[N-2]+DP[N-3]+...+DP[1]\) \(DP[N-2] = DP[N-3]+DP[N-4]+...+DP[1]\) . . . \(DP[1] = 1\) 이제 \(DP[1]\) 부터 \(DP[n-1]\)을 \(DP[n]\) 의 식에 대입해 보면 \(DP[N] = 2^{1}(DP[N-2]+DP[N-3]+...+DP[1])=\) \(2^{2}(DP[N-3]+DP[N-4]+...+DP[1])\) \(= 2^{3}(DP[N-4]+DP[N-5]+...+DP[1])... =2^{N-2}DP[1]\) 가 나옵니다. DP..

알고리즘은 그리디 입니다. 일단 제일 가격이 낮은 숫자들로 최대한 채웁니다. 이때, 0 이 제일 싼 가격이면 그 다음으로 싼 가격의 숫자를 맨 앞에 놓고 그 뒤에 0을 쭉 붙입니다. 그러면 쓰고 남는 돈이 있는데 이 돈으로 최대한 큰 수로 바꿉니다. 각 숫자에 대해 몇개씩 살 수 있는지 나오는데 이 숫자들을 내림차순으로 나열하면 제일 큰 숫자를 만들 수 있습니다. 제가 쫌 코드를 드럽게 짜기 때문에 풀이 이해용으로만 보시기 바랍니다. #include using namespace std; typedef long long ll; int n,pl,End; ll k,x,co[15],ch[15],tmp[15]; struct Money { ll cost; int num; }a[15]; bool cmp(Money p..

오프라인 다이나믹 커넥티비티 알고리즘을 알아보자. Offline Dynamic Connectivity 는 간선 추가, 삭제를 오프라인으로 처리하는 문제에 쓰인다. 대표적으로 BOJ의 16911 = 16912 = 15316 r) return; if(rl 1; add(node*2,l,mid,rl,rr,x), add(node*2+1,mid+1,r,rl,rr,x); } void Rollback(int cntt) { for(int i = 1;i > n >> Q; for(int i = 1;i op >> x >> y; if(x > y) swap(x,y); if(op == 1) vis[i] = 1,LifeTime[{x,y}] = i,QueryIn[i] = {x,y}; else if(op == 2) vis[LifeTim..