코딩생활

https://jungol.co.kr/problem/1672아이디어그래프로 생각해봅시다. S에서 시작하는 DFS를 돌려봅시다. 만약 어떤 점이 단절점이되는데, 이 점으로 인해 S와 E가 떨어지게 된다면, 그 점은 반드시 지나는 점입니다. 이를 구현해주면 됩니다.소스코드#include #include #include #define ll long longusing namespace std;vector Graph[252525];ll visit[252525]={0},now=0;bool Include[252525]={0},danjeol[252525]={0};ll DFS(ll node,ll before){ visit[node]=++now; ll mn=now; for (ll next:Graph[no..

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

https://jungol.co.kr/problem/6131아이디어만약 트리가 고정되어있다고 생각해봅시다. 그리고 루트노드는 리프노드가 아니라고 해봅시다. 일단 리프노드가 홀수개이면 절대 불가능합니다. 만약 짝수개라면 각각의 간선마다 몇번 지나는지 셀 수 있습니다. 그 간선이 node-par[node]를 잇는다면, node를 루트로 하는 서브트리에서 리프노드의 개수를 cnt[node]라 할때, cnt[node]가 홀수라면 그 간선은 한번, 짝수라면 두번 지나게 됩니다. 즉, 루트가 아닌 모든 노드에 대해서 cnt[node]가 홀수면 1, 짝수면 2를 전체 값에 더해주면 됩니다. 그러면 이를 어떻게 빠르게 갱신할 수 있을까요? ETT와 HLD와 느리게 갱신되는 세그먼트 트리를 이용해주면 됩니다. 어떤 점에..

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

https://jungol.co.kr/problem/5256?cursor=MTQsMSwx아이디어문제를 조금 바꾸면 다음과 같은 쿼리를 2M개 수행하는것이 됩니다.- 구간 [S,E]에서 K이하의 수의 개수구간 [S,E]에서 [L,R]의 범위에 포함되는 수의 개수는 (구간 [S,E]에서 R이하의 수의 개수)-(구간 [S,E]에서 L-1이하의 수의 개수)가 되기 때문입니다. 그러면 저 쿼리는 어떻게 수행할까요?N개의 수와 2M개의 쿼리에 대해서 각각이 의미하는 수를 증가하는 순서대로 정렬해봅시다. 그리고 앞에서부터 보면서 N개의 수에 포함이 되면 그 수의 위치에 표시를 합니다. 만약 2M개의 쿼리에 포함이 된다면 주어진 [S,E]의 구간에서 표시된 점의 개수를 세어줍니다. 그러면 모든 쿼리에 대해 정답을 O(..

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

https://jungol.co.kr/problem/5754아이디어쪽방이 있는 개미굴은 무조건 쪽방을 쓰는것이 이득입니다.증명) 쪽방이 있는 i번째 방에 대해서 그 개미굴의 쪽방을 쓰지 않는 최적해가 존재한다고 가정해봅시다. 이 경우에 i번째 방을 쓰는지와 관계 없이 i번째 방을 사용하지 않고 그 쪽방을 사용하면 전체 사용하는 방의 개수가 감소하지 않게 됩니다. 그러므로 항상 쪽방을 사용하는것이 이득입니다. 그러면 쪽방이 있는 방은 사용할 수 없게 됩니다. 그러면 배열 상에서 쪽방이 없는 연속한 방의 개수가 k개이면 (k+1)/2의 버림값이 사용할 수 있는 방의 개수가 됩니다. 이를 계산해주면 됩니다.소스코드#include #include #define ll long longusing namespace ..

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

https://jungol.co.kr/problem/8605?cursor=MjcsMSw0아이디어위치 x에서 위치 a의 거울에 의해 반사되었다고 해봅시다. 그러면 위치는 2a-x가 됩니다. 이 상태에서 위치 b의 거울에 의해 반사가 되면 2b-2a+x가 됩니다. 이를 반복하다보면 늦게 적용한 거울부터 +, -, +, - 가 반복되게 됩니다. 그러므로 거울이 짝수개라면 큰 N/2개가 +를, 작은 N/2개가 -를 가져가고 거울이 홀수개라면 큰 (N+1)/2개가 +를, 작은 (N-1)/2개가 -를 가져가면 됩니다.소스코드#include #include #define ll long longusing namespace std;ll arr[202020]={0};int main() { ios_base::sync_..

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

https://jungol.co.kr/problem/8569?cursor=MjcsMSwxOQ==아이디어앞에서부터 하나씩 채워넣으면서 세그먼트 트리에 기록을 합니다. 그리고 i번째 인덱스까지 오면 i번째 이전에서 멈춰야하는 화살에 대해서 방어력이 가장 큰 k개의 건초더미로 막을 수 있는가? 를 기준으로 매개변수탐색을 해주면 됩니다.소스코드#include #include #include #define ll long longusing namespace std;vector Nums; //1-인덱스ll SumTree[1212121]={0},CntTree[1212121]={0};void update(ll s,ll e,ll node,ll idx){ if (idx > Query[303030];int main()..

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

https://jungol.co.kr/problem/8595?cursor=MjcsMCw4아이디어어떤 정점에 대해서 오른쪽 간선과 왼쪽 간선의 이동 횟수가 다르다는것은, 그 정점을 기준으로 유턴을 했다는 것입니다. 만약 왼쪽 간선에서 더 많이 이동하였다면 왼쪽에서 와서 왼쪽으로 간 것이고 오른쪽 간선에서 더 많이 이동하였다면 오른쪽에서 와서 오른쪽으로 간 것입니다. 또한 각 간선을 사용한 절대적인 수치를 통해 간선을 높낮이의 관점에서 바라보면 한곳에서 왼쪽으로 튕기면 어디서 멈추는지를 생각해볼 수 있습니다. 소스코드#include #include int arr[202020]={0};int Next[202020]={0};bool visit[202020]={0};int main(){ int N,i; std::..

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

https://codeforces.com/contest/2224/problem/B아이디어가장 큰 수를 맨 왼쪽에 보내는것이 항상 이득입니다. 그리고 남은 위치에 0,1,2,3,.. 증가하는 순서대로 MEX값을 키우고 남은 수들을 그냥 오른쪽에 두면 됩니다. 증명) 맨 처음에 0,1,2,... 해서 i개의 수를 놓고 i번지에 최댓값을 놓았다고 생각해봅시다. 이때의 앞의 i개의 수의 MEX값은 i이하입니다. 만약 이 최댓값을 0번지로 옮긴다면, 최댓값에 의한 증가량은 i일것입니다. 반면 MEX값의 감소량은 앞의 i개의 수의 MEX값으로, i이하입니다. 그러므로 항상 최댓값을 맨 앞으로 가지고 오는것이 이득입니다.소스코드#include #include #include #define ll long longusi..

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