코드포스19 codeforces #622 div2 C2 - Skyscrapers (nsv, dp) https://codeforces.com/contest/1313/problem/C2 skyscraper 최대 5e5개 세우려고 한다. 각 건물마다 최대 높이 한도가 주어진다. 그 어떤 건물도 그 건물 기준으로 왼편, 오른편에 더 높은 건물이 둘 다 존재하지 않도록 건물을 올리려고 한다. (전체적인 모양 : non-descending - nod-increasing) 높이의 합이 최대일 때 건물들의 높이를 모두 출력하라 a[i] : 입력값. 건물의 최대 높이 한도 f[i] : 1번~i번까지 건물을 올리는데, i번 건물을 최대 높이로 하는 건물들의 높이 합. g[i] : n번~i번까지(거꾸로) 건물을 올리는데, i번 건물을 최대 높이로 하는 건물들의 높이 합. f[i]+g[i] - a[i]가 최대인 i를 가장.. 2020. 2. 25. Educational codeforces 67 div2 E - tree painting (dfs, dp, rerooting, tree) https://codeforces.com/contest/1187/problem/E 항상 궁금했던 그래프+dp 유형. editorial피셜로 기본문제라고 한다. https://suuntree.tistory.com/126?category=805933 트리에서 모든정점 사이즈 선형시간에 구하는 법 트리가 주어진다. 임의의 정점 하나를 선택한다. 그 정점을 루트로 취급할 때 그 서브트리의 모든 정점들의 size합을 구한다. 그 값 중 최대를 구해라. dp[u] : u를 트리의 루트로 봤을 때 모든 정점의 사이즈 합 위 예시와 같이 루트를 바꿨을 때 dp값이 바뀔 여지가 있다. dp값이 바뀐다면 참조투명하지 않다는 것인데, rerooting 테크닉을 사용하여 이를 극복하는 것에 유념하여 보면 된다. 일단 직관적으.. 2020. 1. 21. Educational codeforces #80 D - Minimax Problem(이분탐색, 비트마스크) https://codeforces.com/contest/1288/problem/D 최대 3e5개의 숫자 배열이 들어온다. 각 배열은 최대 m(m 20 0 1 0 1 1 -> 11 두 배열을 or했을 때 1 1 1 1 1이 되므로 b는 3이상의 최소값을 갖는다. 이번엔 4 이상이면 1, 4미만이면 0으로 바꿔보자 1 0 0 0 0 0 0 0 1 0 OR 연산 후에 1 1 1 1 1이 되지 않으므로 b는 4를 최소값으로 갖지 못한다 여기까지 생각했어도 isPossible(mid) 부분을 구현하는것이 쉽지 않다. 모든 배열에 대해 2중 for문으로 검사하면 n^2으로 시간초과다. 좀더 최적화 해보자 하나의 배열이 갖을 수 있는 비트값은 0 ~ (1 2020. 1. 17. codeforces #612 div2 D - Numbers on Tree (그래프, 수학, 구현) https://codeforces.com/contest/1287/problem/D 실패할 조건을 찾은데서 그친 문제. 시험볼 당시엔 좀만 보면 풀 수 있을 것 같다고 생각했지만, 꽤 오래 생각해봐도 못풀었다. 최대크기 2000의 트리가 주어진다. 각 정점마다 a[i]값을 갖는다. (이 값은 주어지지 않는다. 찾아내야 함) 이 때, 각 정점이 루트가되는 서브트리에서 현재 정점의 a값보다 작은 a값을 갖는 정점들의 수를 c값이 주어질때 가능한 a배열을 구해라. 위->아래, 왼쪽->오른쪽 순서대로 각 정점 번호가 1,2,3,4,5이다. (오른쪽 리프노드가 5번정점이다.) 크게 쓰인 수가 a값이고 괄호 안의 값이 c값이다. 1. 실패조건 각 정점을 루트로 하는 서브트리의 크기를 sz[i]라고 하자. 그러면 c[.. 2020. 1. 7. 이전 1 2 3 4 5 다음
