본문 바로가기

코드포스19

Educational codeforces #69 div2 D - Yet Another Subarray Problem (dp) https://codeforces.com/contest/1197/problem/D 까다로운 dp문제 최대 3e5개의 숫자 배열이 주어진다. 연속된 부분수열 a[l..r]의 비용이 다음과 같을 때, 그 최대값을 구해라. (빈 부분수열의 비용은 0이다. 따라서 답의 최댓값은 0이다.) i번째에서 끝나는 연속된 부분수열은 다음 네 가지 경우로 나눌 수 있다. 첫번째 경우: 0 두번째 경우: a[i]-k 세번째 경우: 네번째 경우: psum(0,i)-k 이걸로 for문 디피하면된다. #include #include #include #define FAST ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); using namespace st.. 2020. 1. 5.
codeforces #610 div2 B2 - K for the Price of One (구현) https://codeforces.com/contest/1282/problem/B2 빡구현 초기 돈 p와 세트로 살 수 있는 묶음단위 k, 최대 2e5개의 물품 가격이 주어질 때, 최대한 많은 물품을 구하는 경우 몇개를 사는지 구하는 문제. 한번 물건을 살 땐 단 한개를 사거나 딱 k개를 사야 한다. k개 묶음을 살 땐 가장 비싼 물품에 대해만 돈을 내면 된다. 돈 6, 묶음단위 3, 가격 2 3 4 5 7 8이 주어질 때를 생각해보면.. (초기돈은 신경쓰지 말자) 물건 1개 살 때 -> (2) 가격:2 물건 2개 살 때 -> (2),(3) 가격:5 -> 일단 신경쓰지 않는다. 더 싼 값으로 더 많이 살 수 있기 때문. 물건 3개 살 때 -> (2,3,4) 가격:4 물건 4개 살 때 -> (2),(3,4.. 2019. 12. 30.
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 #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.

티스토리툴바