코딩생활

https://codeforces.com/contest/2231/problem/C아이디어어떤 수 x에 대하여 주어진 연산을 하면서 나타는 수열을 x의 경로라고합시다. 모든 자연수 x에 대하여 경로의 마지막은 1 2 1 2 의 반복입니다. a1와 a2의 경로중 가장 처음으로 겹치는 부분을 생각해봅시다. 그리고 그 겹치는 지점과 a3와의 처음으로 겹치는 지점, 그 겹치는 지점과 a4와 처음으로 겹치는 지점, ... 이런식으로 해주면 마지막에는 어떤 수가 남습니다. 만약 이 수가 1 또는 2라면 1과 2가 모두 후보가 될 수 있습니다. 만약 이 수가 1과 2가 아니라면 그 수가 정답값이 됩니다. 이제 모든 수에서 그 정답값으로 가는데에 걸리는 비용을 모두 더해주면 됩니다.소스코드#include #include..

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

https://codeforces.com/contest/2231/problem/B아이디어ai>ai+1이라면 ai에는 더하지 말고 ai+1에는 k를 더해주어야합니다. 이를 앞에서부터 보면서 시행해주다가, k를 더해주어도 ai보다 작다면 불가능한것입니다.소스코드#include #define ll long longusing namespace std;ll arr[202020]={0};int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); ll T,N,i; cin>>T; while (T--) { cin>>N; for (i=1;i>arr[i]; ll mx=0; for (i=1;iarr[..

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

https://jungol.co.kr/problem/8536아이디어구간에 대한 세그트리를 다음과같이 만들어줍시다. 이때 M 이상의 수는 1로, M미만의 수는 0으로 표현해줍시다.1. 구간의 시작점2. 구간의 끝점3. 왼쪽 에서 연속으로 1이 최대 몇개가 있는지4. 오른쪽에서 연속으로 1이 최대 몇개가 있는지5. 그 구간에서 그냥 최대 1이 몇개가 연속해있는지이 구조체 세그먼트 트리를 만들어주면 됩니다.소스코드#include #include #define ll long longusing namespace std;struct Range{ ll s,e,Left,Right,mx;};Range operator+(Range A,Range B){ Range res; res.s=A.s; res.e..

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

https://jungol.co.kr/problem/7088아이디어구간 [L,R]에서 x이하의 수의 개수를 구하는것은 O(log N)에 가능합니다. 머지소트트리를 만들어주면 되기 때문입니다. 그러면 구간 [L,R]에서 K번째 수를 찾는것은 어떻게 할까요? 이분탐색을 통해 [L,R]에서 x이하의 수가 K이상인 최소의 x값을 찾아주면 됩니다. 그러면 하나의 쿼리를 O(log2N)으로 해결해줄 수 있습니다.소스코드#include #include #include #define ll long longusing namespace std;vector tree[2020202];ll arr[505050]={0};void init(ll s,ll e,ll node){ if (s==e) { tree[..

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

https://codeforces.com/contest/2231/problem/A아이디어1 3 5 7 ... 2N-1j을 출력해주면 앞에 N개의 수는 홀수, 뒤에 N개의 수는 짝수이며 앞에 N개의 수도 증가, 뒤에 N개의 수도 증가하기 때문에 겹치는 수가 발생하지 않게 됩니다. 물론 N+1,N+2,...2N의 출력도 가능합니다.소스코드#include #define ll long longusing namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); ll T,N; cin>>T; while (T--) { cin>>N; for (ll i=1;i

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

https://jungol.co.kr/problem/1117?cursor=MTQsNywx아이디어이분 매칭 또는 최대 유량을 구해주면 됩니다. 최대 유량을 구할 때에는 0->1, 0->2, ... 0->N을 잇는 크기 1의 간선과 N+1->N+M+1,N+2->N+M+1,...N+M->N+M+1을 잇는 크기 1의 간선, 그리고 i -> N+j를 잇는 크기 1의 간선으로 이루어진 그래프에서의 0->N+M+1의 최대 유량을 구해주면 됩니다.소스코드#include #include #include #define ll long longusing namespace std;ll Capacity[444][444]={0},Flow[444][444]={0};vector Graph[444];ll MaxFlow(ll Start..

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

https://jungol.co.kr/problem/5122아이디어구간 [i,j]에서 인접한 두개씩 가져가는 행동만으로 가능한지 확인하는것은 O(N)의 시간이 걸립니다. dp[i]를 [1,i]의 조약돌을 모두 가져가기위한 행동의 최소 횟수라고 정의하면 [i+1,j]에서 두개씩 가져가는것으로 가능한 최소의 j에 대해 dp[j]=min(dp[j],dp[i]+1)을 수행해줄 수 있습니다. 이를 바탕으로 O(N) DP를 해주면 됩니다.소스코드#include #include #define ll long longusing namespace std;ll arr[2525]={0},dp[2525]={0};int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); ..

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

https://jungol.co.kr/problem/7020아이디어diffi를 다음과 같이 정의합시다.diffi=aix>=ai-1인 가장 작은 정수 x 그리고 resi=ai에 2를 곱하는 횟수 라고 정의합시다. 그러면 resi=max(0,resi-1+diffi)라고 할 수 있습니다. 이떄 구간에 관계없이 diff값은 고정되어있으므로 어떠한 인덱스 i의 res값이 0이라면, i보다 크고 res값이 0이되는 최소의 j를 전처리할 수 있습니다. 물론 그러면 희소 배열을 이용해서 i보다 큰 인덱스중에서 res값이 0이되는 2k번째로 작은 j를 찾을 수 있습니다. 그리고 구간 res값에 0이 없는 구간 [i,j]가 주어지면 solve(i,j)=(diffj+2*diffj-1+3*diffj-2+...+(j-i+1)*..

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