코딩생활

https://jungol.co.kr/problem/5686?cursor=MTMsMSw1아이디어0이상 2M미만의 수를 정점으로 하는 그래프를 생각해봅시다. 이때 i와 j를 잇는 간선이 있다는것은 i와 j사이의 해밍 거리가 1이라는것을 의미합니다. 그러면 등장하는 모든 x에 대하여 가장 멀리 떨어진 점을 찾아주면 됩니다. 이는 2M-1 xor x와 가장 가까운 거리에 있는 점을 의미하므로, 모든 x에 대하여 2M-1 xor x들을 잡고, 이것들을 기준으로 멀티소스 BFS를 사용해주면 각 점마다 가장 가까운 점까지의 거리를 구할 수 있습니다.소스코드#include #include #define ll long longusing namespace std;bool visit[1050101]={0};int dis[..

PS,CP 2026. 4. 24. 16:00

https://jungol.co.kr/problem/1246?cursor=MTMsNCwy아이디어준식이 P 이상일 수 있는지의 여부를 판단해봅시다. 그러기 위해서는 ai-P*bi의 값중 가장 큰 N-K개의 합이 0이상이여야합니다. 그러므로 0이상 1이하의 P에 대해서 매개변수탐색을 진행해주면 됩니다소스코드#include #include #include #define ll long longusing namespace std;bool Able(vector A,vector B,double P,ll K){ ll N=A.size(); vector v; for (ll i=0;i()); double sum=0; for (ll i=0;i=0;}int main(){ ios_base::..

PS,CP 2026. 4. 24. 09:00

https://jungol.co.kr/problem/2956?cursor=MTMsMiw0아이디어구간 [i+1,j]의 수들의 평균이 P 이상이라고 해봅시다. sum[i]를 A[1]+A[2]+...+A[i]라고 정의하면, (sum[j]-sum[i])/(j-i)>=p라고 정의할 수 있습니다. 이를 정리하면 sum[j]-pj>=sum[i]-pi이고, 이것은 인덱스에 의존하므로, 모든 인덱스 i에 대하여 sum[i]-pi를 저장한 후에, i소스코드#include #include #include #define ll long longusing namespace std;int tree[4040404]={0};ll Sum(ll s,ll e,ll node,ll l,ll r){ if (e v) //v에서 i v2; ..

PS,CP 2026. 4. 23. 16:00

https://jungol.co.kr/problem/3579?cursor=MTMsMSwy아이디어지금까지 들어간 수들을 정렬해봅시다. 그리고 새로운 수 x를 넣는다고 해봅시다. 그러면 x이상의 가장 작은 수와 x이하의 가장 큰 수가 있을것입니다. 그 두 수의 깊이의 최댓값 +1이 이 수 x의 깊이가 됩니다. 이를 std::set을 이용하여 구현해주면 됩니다.소스코드#include #include #include #define ll long longusing namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); ll N,i,x,sum=0; set > st; cin>>N; for (i=1;i>x; ..

PS,CP 2026. 4. 23. 09:00

https://jungol.co.kr/problem/5341?cursor=MTMsMSwx아이디어a에서 연산을 할 때에 곱셈을 한번 하고 그 다음에 나눗셈을 하는 경우는 없습니다.증명) 만약 그러한 경우가 존재한다고 해봅시다. 그리고 덧셈 연산을 빼고 곱셈과 나눗셈 연산만 남겨봅시다. 그러면 곱셈 바로 다음에 나눗셈이 등장하는 경우가 적어도 한 번 나타나게 됩니다. 이러한 경우 덧셈까지 고려하면 (곱셈) -> (덧셈) k번 -> (나눗셈)의 형태가 됩니다. 이떄 곱셈을 한 후에 수가 짝수이고 나눗셈을 하기 전에 수가 짝수이므로 k 또한 짝수가 됩니다. 그러면 위 k+2개의 연산을 사실 k/2개의 덧셈으로 표현할 수 있습니다. 그러므로 저러한 경우는 존재하지 않습니다. 그러면 항상 나눗셈이 몇번 등장하고 곱..

PS,CP 2026. 4. 22. 16:00

https://jungol.co.kr/problem/3998?cursor=MTMsMCw5아이디어i의 자식이면서 p값이 더 큰것의 개수를 세어주면 됩니다. 이때 p값의 범위가 너무 크므로 값 압축을 이용하여 1이상 100,000 이하의 수로 바꾸어줍시다. 그리고 DFS를 돌리면서 i번 노드에 들어갈 때까지 지나간 정점중 p값이 i의 p값보다 큰 정점의 개수를 저장해줍니다. 그리고 i번 노드의 DFS를 나올때까지 지나간 정점중 p값이 i의 p값보다 큰 정점의 개수를 저장해줍니다. 이 두 값의 차이가 i의 자식이면서 p값이 더 큰 정점의 개수입니다. 이와같은 쿼리는 세그먼트 트리를 이용해주면 해결해줄 수 있습니다.소스코드#include #include #include #define ll long longusi..

PS,CP 2026. 4. 22. 09:00

https://jungol.co.kr/problem/5602?cursor=MTMsMSww아이디어무조건 LLLLL...LLLRRRR..RRR의 꼴로만 남아있어야합니다. R 오른쪽에 L이 하나라도 있다면 둘중 하나는 다른 하나를 볼 수 있으므로 문제 조건이 성립하지 않게 됩니다. 그러므로 모든 인덱스 i에 대하여 [1,i]에서 L을 증가하는 순서대로 최대한 많이 뽑는 경우, [i+1,N]에서 R을 감소하는 순서대로 최대한 많이 뽑는 경우를 구해주면 됩니다. 이는 O(NlogN)에 각각의 개수를 모두 구해줄 수 있습니다. LIS를 이용해주면 됩니다.소스코드#include #include #include #include #define ll long longusing namespace std;ll LeftLIS[..

PS,CP 2026. 4. 21. 16:00

https://jungol.co.kr/problem/5092?cursor=MTMsMCw0아이디어만약 풀 문제를 정했다면, 어떤 순서대로 푸는것이 이득일까요? 이는 Exchange Argument로 최적화해줄 수 있습니다. i번째 문제를 풀기 시작한 시각을 t라하면, i번째 문제를 푼 시각과 i+1번째 문제를 풀기 시작한 시각은 t+Ri이라고할 수 있고, i+1번째 문제를 푼 시각은 t+Ri+Ri+1이라고 할 수 있습니다. 이때의 점수는 (Mi-(t+Ri)Pi)+(Mi+1-(t+Ri+Ri+1)Pi+1)이라고 할 수 있습니다. 이때 두 문제의 푸는 순서를 바꾸면 점수가 (Mi+1-(t+Ri+1)Pi+1)+(Mi-(t+Ri+Ri+1)Pi)가 되며, 앞에 식이 더 크거나 같아야하므로 정리하면 R/P가 증가하는 ..

PS,CP 2026. 4. 21. 09:00