코딩생활

https://jungol.co.kr/problem/8671아이디어경로는 정해져있습니다. 같은 간선을 왔다갔다 하는것은 A+B>=0이므로 이득일 수 없습니다. 그러므로 경로는 정해집니다. 또한 a에서 b로 가는 경로는 LCA를 통해 a->lca와 b->lca의 합성으로 구할 수 있습니다. 이제 우리가 구해야하는것은 a->lca에서의 결과적인 높이차, 그 과정에서의 가장 높이 올라가는 값, lca->b에서의 결과적인 높이차, 그 과정에서의 가장 높이 올라가는 값입니다. 사실 높이가 아니라 체력이긴 한데 그냥 높이로 부릅시다. 이는 LCA에서의 희소배열을 이용해주면 됩니다. UpHeight[i][a]는 노드 i에서 2a만큼 올라간 조상까지 올라갈 때 높이차입니다. 반대로 DownHeight[i][a]는 노드..

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

https://jungol.co.kr/problem/5338아이디어dp[i][j][k]를 1번째 소부터 i번째 소까지만 고려하고 i번째 소의 h값 hi가 j이며 모든 소들의 배고픈 정도를 k로 맞추는 경우의 수라고 정의합시다. 다만 이러면 공간복잡도가 1억이 되므로 dp[j][k]만을 저장하고 배열을 돌아가면서 사용합시다. 이 dp테이블을 채우는것 자체는 쉽습니다. dp[i][j][k]=dp[i-1][k][k]+dp[i-1][k+1][k]+...+dp[i-1][Hi-1+(j-k)][k]가 됩니다. 다만 중요한것은 이 dp테이블을 바탕으로 정답값을 어떻게 도출할지입니다. 만약 N이 홀수라면, 모든 소들에 대해서 h값을 똑같이 맞추는 값은 h배열에 따라 하나로 정해져있습니다. 다시 말하면, dp[N][*][..

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

https://codeforces.com/contest/2228/problem/B아이디어도망치는 입장에서는 최대한 기다린 다음에 한칸 떨어졌을 때부터 도망가는것이 무조건 이득입니다. 그러므로 (떨어진 거리)+k가 정답이 됩니다. 하지만 n이 3이하라면 그냥 한번의 턴에 잡히게 됩니다. 이를 고려해주면 됩니다.소스코드#include #include #define ll long longusing namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); ll T; cin>>T; while (T--) { ll N,x1,x2,k; cin>>N>>x1>>x2>>k; if (N

PS,CP 2026. 5. 20. 16:00

https://jungol.co.kr/problem/5721아이디어어떤 구간 [x+1,y]가 가능하기 위해서는 다음중 하나를 만족해야합니다. 이때 I[i]를 1부터 i까지 'I'의 개수, C[i]를 1부터 i까지의 'C'의 개수, P[i]를 1부터 i까지의 'P'의 개수라고 합시다.1. I[y]-I[x]==C[y]-C[x]2. P[y]-P[x]==C[y]-C[x]3. I[y]-I[x]==P[y]-P[x] 1번 식을 정리하면 I[y]-C[y] 와 I[x]-C[x]가 같은 x값을 찾음과 동시에 P[y]-I[y]보다 P[x]-I[x]가 더 작아야합니다. 이러한 모든 x에 대하여 그 위치 x에서의 dp값을 더해주면 됩니다. 이는 세그먼트 트리로 해결해줄 수 있습니다.I[y]-C[y], P[y]-I[y]와 같은 ..

PS,CP 2026. 5. 20. 09:00

https://jungol.co.kr/problem/10802?cursor=NTkwLDcsNQ==아이디어정답직선중에서 석유의 양 끝 점 중 두개 이상을 지나는 직선이 존재함을 보일 수 있습니다. 다시 말하면, 하나의 점을 고정시키고 그 점을 지나는 직선들에 대해서 최댓값을 구하기 위해서는 그 점과 다른 모든 점들을 잇는 직선에서 가장 많은 석유와 만나는 직선을 찾아주면 됩니다. 한 점을 고정시켜주고 나머지 점들에 대해서 반시계방향으로 살펴보면서 석유에 들어가는 지점은 +(석유의 길이), 나가는 지점은 -(석유의 길이)를 해주면 됩니다. 이때 한 방향에 +와 -가 겹쳐있는 경우도 있는데, 이러한 경우에는 +를 먼저 해줌으로써 가능한 모든 경우를 체크해줄 수 있습니다.소스코드#include #include ..

PS,CP 2026. 5. 19. 16:00

https://jungol.co.kr/problem/3671아이디어CHT를 이용해주면 됩니다. 기울기가 작은 것부터 차례대로 넣으면서 볼록 껍질을 만들어줍시다. 그리고 x가 주어지는 쿼리들은 다 모아놓은 다음에 정렬해서 한번에 처리해줍니다.소스코드#include #include #include #define ll long longusing namespace std;void minimize(vector > &v){ sort (v.begin(),v.end()); vector > res; for (ll i=0;i A,pair B){ return (double)(A.second-B.second)/(double)(B.first-A.first);}vector > CHT(vector >..

PS,CP 2026. 5. 19. 09:00

https://jungol.co.kr/problem/2303?cursor=NTkwLDQsNw==아이디어일단 용액을 정렬해줍시다.그리고 앞에서부터 첫번째 용액을 골라줍시다. 첫번째 용액의 인덱스 i를 골랐으면 두 포인터를 이용하여 i초과의 범위에서 두번째와 세번째 용액으로 적절한것을 골라주면 됩니다. 그러면 O(N2)에 최적해를 구할 수 있습니다.소스코드#include #include #define ll long longusing namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); ll N,i,arr[5050]={0},a=2e9,b=2e9,c=2e9; cin>>N; for (i=0;i>arr[i]; ..

PS,CP 2026. 5. 18. 16:00

https://jungol.co.kr/problem/1769?cursor=NTkwLDYsMQ==아이디어현들의 집합을 잡았다고 해봅시다. 여기서 임의의 원소 [l1,r1], [l2,r2]에 대해서 l1 dp[i][j]를 구간 [i,j] 안에 포함되는 현들의 집합에서의 정답값이라고 해봅시다. 만약 [i,j]의 현이 존재한다면, dp[i][j]는 dp[i+1][j-1]+1이 가능합니다. 그렇지 않다면 i이상 j미만의 모든 k에 대하여 dp[i][j]는 dp[i][k]+dp[k+1][j]도 가능하게 됩니다. 이러면 O(N3) DP로 문제를 해결해줄 수 있습니다.소스코드#include #include #define ll long longusing namespace std;ll dp[111][111]={0};boo..

PS,CP 2026. 5. 18. 09:00