코딩생활

https://jungol.co.kr/problem/1994?cursor=NTA4LDAsOA==아이디어멀티소스 다익스트라를 이용해서 모든 노드에 대해 동아리로부터 떨어진 거리를 구해줍니다. 만약 하나의 시작점-도착점 쿼리가 있다면, 동아리로부터의 거리가 먼 노드부터 하나씩 추가하면서 시작점과 도착점이 연결되는 순간을 유니온 파인드를 이용해 구해주면 됩니다. 하지만 이러한 쿼리가 여러개가 있다면, PBS를 사용해야합니다. PBS는 병렬 이분 탐색으로, 어떤 쿼리에 대해서 동아리로부터의 거리가 가장 먼 K개의 노드만을 가지고 이동할 수 있는가? 라는 질문으로 매개변수탐색을 해주면 됩니다. 그러면 O(M log N)에 문제를 해결해줄 수 있습니다.소스코드#include #include #include #inc..

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

https://jungol.co.kr/problem/3900?cursor=NTA4LDAsNw==아이디어세그먼트 트리를 만들어서 특정 구간 내의 모든 고깔을 방문했을 때의 이동거리와 한개를 제외하고 방문했을 때의 최소 이동거리를 저장합시다. 이때 인접한 두 구간을 합칠 때 모든 고깔을 방문하는 경우는 그냥 (왼쪽 구간의 모든 고깔 방문)+(두 구간 사이 점의 거리)+(오른쪽 구간의 모든 고깔 방문)을 해주면 되며, 하나를 제외하고 방문하는 경우는 추가로 왼쪽 구간의 맨 오른쪽 고깔을 지나지 않는 경우와 오른쪽 구간의 맨 왼쪽 고깔을 지나지 않는 경우를 고려해주면 됩니다.소스코드#include #include #include #define ll long longusing namespace std;struc..

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

https://codeforces.com/contest/2222/problem/B아이디어홀짝성이 같은 인덱스끼리는 뒤집기를 통해 마음대로 swap을 할 수 있습니다. 그러므로 마킹을 할 때에 최대한 큰것들을 마킹하기 위해서 마킹할 인덱스의 홀짝성을 바탕으로 홀수의 개수와 짝수의 개수를 세어주면 됩니다. 홀수 인덱스의 마킹 개수를 Odd라고 합시다. 그리고 홀수 인덱스의 수들을 OddNum이라고 합시다. 그러면 OddNum에서 가장 큰 Odd개를 마킹해주면 됩니다. 이때 이중에 음수가 끼어있으면 그 음수는 마킹하지 않습니다. 만약 모든 수가 음수라면 가장 큰 (절댓값이 가장 작은) 음수만을 마킹해주면 됩니다. 짝수도 마찬가지입니다.소스코드#include #include #include #define ll ..

카테고리 없음 2026. 5. 5. 16:00

https://codeforces.com/contest/2222/problem/A아이디어1을 만들 수 있기 위해서는 ai중에서 100인것이 존재해야합니다. 그리고 ai중에서 100인것이 존재한다면, 모든 수를 만들 수 있습니다. 그러므로 입력받은 수 중에서 100인것이 있는지 확인해주면 됩니다.소스코드#include #include #define ll long longusing namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); ll T,N,i,x; cin>>T; while (T--) { cin>>N; bool exist=false; for (i=1;i>x; ..

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

https://codeforces.com/contest/2226/problem/B아이디어순열의 조건을 무시해봅시다.어떠한 부분수열이 좋은 부분수열일 조건은 무엇일까요? 바로 그 부분수열에 서로다른 수의 개수가 두개이며, 그 두 수의 차이와 최대공약수가 같은 경우입니다. 그런데 주어진 수열은 순열이므로 부분수열 안의 서로다른 수의 개수가 2일 조건은 부분수열의 길이가 2인 경우입니다. 그러므로 연속한 두 수를 보고 그 수의 차이와 최대공약수가 같은 경우의 개수를 세어주면 됩니다.소스코드#include #include #define ll long longusing namespace std;ll gcd(ll a,ll b){return ((b)?gcd(b,a%b):a);}int main(){ ios_bas..

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

https://codeforces.com/contest/2226/problem/A아이디어최대한 모두 따로따로 고려해줍시다. 다만 1은 최대한 다른 수들과 붙여줍니다. 그러므로 1이 아닌 수가 들어오면 그냥 결괏값에 더해주고, 1이 들어오면 그 1이 마지막 인덱스의 1인 경우에 결괏값에 1을 더해주면 됩니다.소스코드#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,i,x,sum=0; cin>>N; for (i=1;i>x; ..

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

https://koistudy.net/prob_page?NO=4319아이디어NearDotRange를 3000으로 바꾸었다. 사실 이것은 가장 가까운 점을 고르는것과 관계없이 그냥 모든것을 탐색한다고 봐도 된다. 그런데 이렇게하면 오히려 점수가 안나온다. 차라리 순서대로 보는게 나은듯 하다.그래서 NearDotRange를 20과 3000으로 하였고 그때의 가능한 후보들을 증가하는 순서대로 보았다. 그래도 크게 달라진 점은 없는 것 같다.소스코드#include #include #include #include #include #include #include #define ll long longusing namespace std;using namespace chrono;const ll NearDotRange=2..

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

https://koistudy.net/prob_page?NO=4319아이디어2-opt를 할 때에 가장 가까운 몇개만 후보로 넣고 돌리는 코드를 구현해보았다. 일단 NearDotRange=20이다.생각보다 결과가 좋지 않았다 (1069점)소스코드#include #include #include #include #include #include #include #define ll long longusing namespace std;using namespace chrono;const ll NearDotRange=20;vector > Dots;ll Dis2(array A,array B){ ll dx=A[0]-B[0],dy=A[1]-B[1],dz=A[2]-B[2]; return dx*dx+dy*dy+..

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