본문 바로가기

알고리즘/코드포스44

cf #632 div2 C - Eugene and an array (투포인터) https://codeforces.com/contest/1333/problem/C -1e9~1e9값을 갖는 최대 1e5의 원소 n개의 배열이 주어진다. 배열의 subarray 중 그 subarray의 subarray의 원소합이 0이 아니면 good subarray라고 한다. 주어진 배열의 good subarray 개수를 구하라 [a1, a2, a3, a4]가 good subarray라면 [a1,a2,a3]도 good subarray이다. 하지만 [a3,a4]가 good subarray일수도 있고 아닐수도 있다. ps[1] = ps[4]인 경우 a[2]~a[4]는 bad subarray이다. 문제의 성질을 잘 생각해보면 투포인터로 풀 수 있다. ll n, a[MAX], ps[MAX]; int main() .. 2020. 4. 13.
cf #538 div2 C - Trailing Loves (소인수분해, 수학) https://codeforces.com/contest/1114/problem/C n! 에 어떤 소수가 몇개 들어있는지 로그시간에 파악하는 법 확인. 오버플로우를 피하기 위한 조건문 확인. 최대 1e18의 n과 최대 1e12의 b가 주어진다. n!을 b진법으로 표현했을 때 trailing zero의 수를 세라. (ex. 9800은 10진법으로 trailing zero가 두개 있다.) n!을 b로 몇번 나눌 수 있는지 구하면 된다. b를 소인수분해하여 p ^ x꼴의 인수들에 대해서, n!에 그 하나하나의 인수가 나오는 횟수들의 최소를 구하면 된다. n!에 어떤 소수 x가 몇 개 들어있는지 반환하는 함수 f를 이용해서 풀 수 있다. ll f(ll x) { ll ret = 0; ll t = x; x = 1; .. 2020. 4. 2.
cf #630 div2 E - Height all the same (수학, 집합) http://codeforces.com/contest/1332/problem/E n*m 그리드, 각 칸의 초기 높이 하한 상한 L,R이 주어진다. 인접한 두 칸의 높이를 1 늘리거나, 한 칸의 높이를 2 늘리는 작업을 마음대로 할 수 있을 때, 언젠간 모든 셀의 높이가 같도록 초기 그리드를 설정하고 싶다. 초기 그리드를 설정하는 경우의 수를 구하라. 높이를 맞추는 건 실제 높이가 중요하지 않고, 각 칸의 패리티가 중요하다. 모든 칸의 패리티가 같아질 수 있다면 그 초기 그리드는 유효한 그리드이다. 인접한 두 칸의 높이를 1씩 늘리는 것 -> 임의의 두 칸의 패리티를 바꾸는 것으로 생각할 수 있다. (u->v로 하나씩 높이를 늘리는 연산을 하다보면, 결국 u,v의 패리티만 바뀌고 경로상의 칸의 패리티는 변.. 2020. 4. 1.
cf 551 div2 D - Serval and Rooted Tree (tree, dp, 발상) https://codeforces.com/contest/1153/problem/D 문제를 재정의하는 방법이 새로워서 리뷰 루트가 1인 트리가 주어진다. 리프노드가 k개 있다면 각 리프노드에 1~k의 순열을 저장할 수 있다. 각 노드마다 min또는 max 성질이 주어지는데, 자식노드의 값중 최소 또는 최대를 값으로 갖는다는 의미다. 리프노드에 적절한 값을 넣어 루트에 저장될 수 있는 값 중 최대를 구하라. 현재 정점 u가 max 성질이 있다면, 그냥 자식 정점 값중 최대를 갖으면 된다. 문제가되는건 min성질이다. 예를들어서 min성질을 갖는 정점 u가 리프노드 3개를 자식으로 둔다면, 가장 작은 하나를 제외하고 2개의 숫자를 잃는다고 생각할 수 있다.(잘 생각해보면 u의 자식이 리프노드가 아니더라도 일반.. 2020. 3. 25.

티스토리툴바