본문 바로가기

알고리즘/코드포스44

Educational codeforces #78 D - Segment Tree (라인스위핑) https://codeforces.com/contest/1278/problem/D 풀이가 너무 생소해서 정리해둠 최대 5e5개의 정점이 입력된다. 정점은 [l,r]의 정보를 담고 있다. 서로 교차되는(intersect) 정점들이 서로 이어져있다고 할 때, 그 그래프가 트리인지 아닌지를 출력하는 문제. ex) 정점[1,3]과 [2,4]는 이어져있다. 하지만 [1,2],[3,4]는 이어져 있지 않다. +모든 끝점은 유일하다. 예를들어 [1,2][2,3]이 동시에 주어지는 경우는 없다 1. 각 정점의 정보를 P a[MAX]에 담아둔다. 2. vector evs에 (a[i].first, i) 와 (a[i].second, i)를 모두 담아서 오름차순 정렬한다. 3. set cand를 마련한다. (아직 교차할 정점.. 2019. 12. 29.
codeforces #608 div2 D - Portals (dp) https://codeforces.com/contest/1271/problem/D dp인건 파악했는데 중요한 포인트를 놓치고 식을 너무 복잡하게 짜서 틀린 문제. 성 n개, (성의 방어력 a, 성에서 영입되는 병사 b, 성에 인원 1명을 배치했을 때 받는 점수 c), 성과성을 잇는 간선 m개, 초기 병사 수 k명이 주어질 때 얻을 수 있는 최대 점수를 출력하는 문제다. pos번째 성에 인원을 1명 배치하는 경우는 최대한 늦게 하는 것이 최적이다. 예를들어 3번째 성으로 4번 5번 성에 포탈이 있다면 3번째 성에서 바로 인원을 배치하는 것보단 4번 성에서 포탈을 태워 보내는 경우가 최적이고, 그보다 5번째 성에서 3번째 성으로 인원을 배치하는 것이 최적이란 뜻이다. 위 아이디어를 자료구조로 잘 구현해 보면.. 2019. 12. 21.
codeforces #585 div2 B - The Number of Products (전처리, 구현) https://codeforces.com/contest/1215/problem/B B번이지만 신기한 전처리를 사용해서 풀 수 있어서 리뷰 길이가 n인 0이 아닌 정수의 배열에서, 연속된 부분 수열의 곱이 음수인 것의 개수와 양수인 것의 개수를 출력하는 문제다. ex) 1 2 -3 4의 경우 6 4을 출력해야 한다. 0. 음수인 것의 개수를 cnt_n 이라고 한다면 양수인 것의 개수는 n*(n+1)/2 - cnt_n 이 될 것이다. 1. 음수가 나오는 인덱스를 1 base로 벡터에 넣어준다. (그 후 벡터가 비어있으면 cnt_n은 0이다) 마지막으로 계산의 편의를 위해 n+1도 벡터에 넣어준다. 예1) 예를들어 n이 4이고 벡터에 3 4가 들어있다면 배열에서의 배치는+ + - +이다. 곱이 음수인 부분수열.. 2019. 12. 14.
codeforces #604 div2 D - Beatiful Sequence (수학,발상) http://codeforces.com/contest/1265/problem/D - 댓글풀이 0,1,2,3이 각각 a,b,c,d번 나오는 숫자의 배열 a 를 만드는데 다음 조건을 만족해야 한다. 문제의 조건을 만족하기 위해선, 어떤 연속한 수도 같은 parity를 가질 수 없다. 따라서, 1. 배열의 크기가 홀수인 경우엔 cnt(even)와 cnt(odd)가 1 차이가 나야 한다. cnt(even)이 더 큰 경우 0과 2를 배열a의 홀수번 idx에 순서대로 배치하고, 1과 3을 배열 a의 짝수 idx에 순서대로 배치하면 된다. cnt(odd)가 더 큰 경우는 그 반대로 하면 된다. 2. 배열의 크기가 짝수일 경우엔 cnt(even)=cnt(odd) 1번처럼 하면 된다. 무엇을 먼저 배치할진 자유 그리고 .. 2019. 12. 7.

티스토리툴바