알고리즘 공부방

문제 oj.uz/problem/view/IOI20_plants 문제 보기 - 식물 비교 (IOI20_plants) :: oj.uz 문제 보기 - 식물 비교 (IOI20_plants) oj.uz 원 위에 0~N-1의 N개의 수가 배열되어 있는 순열 $A$가 있다. 이 때 $R_i$는 i번째 칸부터 오른쪽으로 연속한 $K-1$개의 수들 중 $A_i$보다 큰 수들의 개수로 정의된다. 수열 $R_i$와 쿼리 (x, y)가 Q개 주어질 때, 가능한 모든 $A_i$에서 $A_xA_y$를 만족하는지, 아니면 두 경우 모두 가능한지 판별해야 한다. 단, 주어지는 $R$는 대응되는 $A$가 적어도 하나 존재하는 수열로 주어진다. $K1; init(node*2, tl, mid); init(node*2+1, mid+1, t..

문제 oj.uz/problem/view/JOI19_dishes 문제 보기 - Two Dishes (JOI19_dishes) :: oj.uz 문제 보기 - Two Dishes (JOI19_dishes) oj.uz 두가지 요리가 있고, 각 요리를 완성하기 위해서는 각각 $N$, $M$개의 단계를 거쳐야 한다. 각 단계마다 수행하는 시간이 주어지고, 각 단계를 $A_i$ 시간 이하로 끝낸다면 $B_i$의 보상을 받을 수 있다. 각 요리의 단계들은 순서대로 시행해야 하며, 두 요리의 단계들을 번갈아 가며 하는 것은 허용된다. 이 때 얻을 수 있는 보상을 최대화해야 한다. $N=Y_i)$ 구간에 더해줌 원래 계단 꼴이었고, 뒤쪽 구간에 $P_i$를 더하는 과정에서 깨진 계단을 다시 맞춰주는 형식이니, 요약하자면 ..

문제 oj.uz/problem/view/JOI19_antennas 문제 보기 - Two Antennas (JOI19_antennas) :: oj.uz 문제 보기 - Two Antennas (JOI19_antennas) oj.uz N개의 안테나마다 $A$, $B$, $H$의 값이 주어지는데, 이는 $i$번째 안테나가 통신할 수 있는 거리의 범위가 $A$이상 $B$이하이며, 높이가 $H$라는 것을 의미한다. 서로 다른 두 안테나 $i, j$ 사이의 거리는 $|i-j|$로 정의된다. 이 때 Q개의 $(l, r)$쿼리가 주어지는데, 이는 $[l, r]$구간에 있는 안테나들 중 서로 양방향으로 통신할 수 있는 $i$와 $j$에 대하여 $|H_i-H_j|$의 값들 중 최댓값을 출력해야 한다. $N

https://contests.ioi-jp.org/open-2018/index.htmlhttps://oj.uz/problems/source/351 역시 JOIOC는 어렵다. 문제 하나하나가 다 좋은 문제이고, 많이 생각할 수 있게 해주는 문제들인 것 같다.4일동안 1, 4번을 풀었고, 2번은 부분점수, 3번은 풀지 못하였다.Heavy Light Decomposition을 응용한 DP 최적화, Sqrt Decomposition 등 아직 내가 익숙하지 않은 개념들이 많이 이용되어서 더 어렵게 느껴진 것 같다. 나중에 이런 개념들을 잘 익힌 후에 꼭 다시 풀어봐야 할 문제들이다. 4. xylophone 순열이 하나 있고, 물어볼 수 있는 쿼리는 오직 어떤 구간 내의 최대값-최솟값만 물어볼 수 있을 때 2N 번..

문제 https://www.acmicpc.net/problem/1395 스위치 n개에 대하여 특정 구간의 스위치를 모두 반전시키거나, 구간에 있는 켜져 있는 스위치의 수를 세는 쿼리를 해결하는 문제이다. 풀이 세그먼트 트리를 이용한다. 세그먼트 트리의 각 노드가 해당 구간의 켜져 있는 스위치들의 수를 갖고 있다면, 2번째 쿼리는 쉽게 해결할 수 있다. 문제는 첫번째 쿼리가 하나의 스위치를 반전시키는 것이 아니라, 특정 구간의 모든 스위치들을 반전시키는 것이다. 따라서 세그먼트 트리 레이지 프로파게이션을 사용해야 한다. 레이지 배열에는 그 구간에 대한 반전 연산이 적용되었는가 여부를 저장한다. 구간합에 대한 레이지처럼 구간 업데이트를 할 때 자신이 완전히 속한 노드에 대해서, 레이지값을 자식들에게 넘겨주며..

기본적인 세그먼트 트리는 구간에 대한 쿼리와, 특정 값을 업데이트하는 연산밖에 안된다. 만약 구간에 대해 업데이트 하는 연산이 필요하다면 Lazy Propagation 을 사용해야 한다. 간단한 원리는 업데이트해야하는 구간에 완전히 속한 노드들에게 lazy 값을 올려준 후, 나중에 그 노드를 방문할 때가 됬을때 lazy 값을 꺼내서 실제 값에 업데이트 해주는 방식이다. *더 구체적인 설명은 https://www.acmicpc.net/blog/view/26을 참고한다. struct SEG { int n; vector tree, lazy; SEG() {} SEG(int n) : n(n), tree(n*4+10), lazy(n*4+10) { init(1, 1, n); } void init(int node, i..