2021. 1. 23. 10:08ㆍPS/Problem Solving
구현 없이 풀이만 생각
효율적인 사고력 증진 연습
https://www.acmicpc.net/problem/1040
1040번: 정수
정수 N이 주어진다. N보다 크거나 같은 수 중에, K개의 서로 다른 숫자로 이루어진 수 중 가장 작은 수를 출력하는 프로그램을 작성하시오.
www.acmicpc.net
dp[N][first][st] : 길이 N의, first로 시작하는 수들 중 st 상태만큼의 숫자들을 사용했을 때 만들 수 있는 최소 정수
9623번: 부분 수열의 길이
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 N (1 ≤ N ≤ 500,000)과 X (-109 ≤ X ≤ 109)가 주어진다. 둘째 줄에는 수열에 들어있는 정수 N개가 주어진다. 이 정수는
www.acmicpc.net
접두사 누적합 저장. & 좌표압축
sum(1)부터 sum(n)을 좌표압축한다.
'좌표압축 값'을 인덱스로 하는 최댓값 세그 트리에, 각각 1~n을 저장할 것이다.
i를 1부터 n까지 돌리면서
sum(i)에 대해서 $0<=j < i$ , $sum(i)-sum(j) >= X$ 를 만족하는 j 중 최댓값을 구해야 하므로
sum(i)-X를 sum들을 좌표압축한 value들 중에 찾아 인덱스를 구하고 세그트리에서 최댓값을 찾는다.
인덱스는 upper_bound로 구할텐데, 없을 경우는 처리해주자.
세그트리의 초기값은 -1로 초기화 한다. (0이 있기 때문)
i-j로 ans를 갱신 시도.
5419번: 북서풍
각 테스트 케이스에 대해서, 북서풍을 타고 항해할 수 있는 섬의 쌍의 수를 출력한다.
www.acmicpc.net
x좌표 정렬된 순서로 보면서 y좌표 좌표압축 (or 다이내믹 세그) 해 놓고 y축 세그트리에 1 업데이트.
스위핑한다고 생각하자.
각 점마다 1 ~ 자기 y좌표의 구간합을 구하여 ans에 더한다. 펜윅으로 하면 편함.
9034번: 순위
프로 게이머 협회는 등록된 N 명의 선수들에 대한 순위를 유지한다. 선수들의 순위는 게임을 치를 때마다 얻는 점수에 의해 결정된다. 점수를 누적한 값은 랭킹 포인트가 되고, 랭킹 포인트가 높
www.acmicpc.net
indexed set을 쓰거나
다이내믹 세그를 쓰거나
좌표압축 + 펜윅을 쓴다.
당연히 값을 인덱스로 하고, 개수를 값으로 하는 구간합 세그다.
20052번: 괄호 문자열 ?
괄호 문자열은 '('와 ')'로 이루어진 문자열이고, 올바른 괄호 문자열은 다음과 같이 정의된다. 빈 문자열은 올바른 괄호 문자열이다. S가 올바른 괄호 문자열일 때, (S)도 올바른 괄호 문자열이
www.acmicpc.net
( -> 1 , ) -> -1로 생각하면 (Saycorn GOD!!!!!!)
S a~ b가 괄호문자열이 될 조건은
1. sum[i] - sum[a-1] >= 0 for all a<=i<=b
2. sum[b] - sum[a-1] == 0
sum[i] >= sum[a-1] (a<=i<=b)를 만족한 다는 것은
min(sum[i]) >= sum[a-1])을 만족한다는 것
세그트리로 쌉가능
17407번: 괄호 문자열과 쿼리
괄호 문자열은 '('와 ')'로 이루어진 문자열이고, 올바른 괄호 문자열은 다음과 같이 정의된다. 빈 문자열은 올바른 괄호 문자열이다. S가 올바른 괄호 문자열일 때, (S)도 올바른 괄호 문자열이
www.acmicpc.net
위 문제랑 일맥상통하는데
str[a]를 수정하는 것은
sum[a] ~ sum[n]을 수정하는 것.
이는 레이지 세그 트리로 가능하다.
각 쿼리에 대해 sum[1] ~ sum[n]의 최솟값이 0 이상인지, 그리고 sum[n]이 0인지 체크해 결과값 변수에 더해주면 된다.
18571번: Calculating Average
Bytelandian schools have a rather unusual average mark calculation system. Students’ marks are represented as an array a of n integers. At the end of a term, the teacher picks any mark with index k in array a. Then the student may choose any consecutive
www.acmicpc.net
Parallel Binary Search + CHT
에디토리얼을 봤다. 그리고 감동 받았다
얘는 꼭 여기다가 풀이 적고 구현해보기.
CHT는 결국 순차적인 직선 삽입과 특정 x좌표에서 최댓값을 구해주는 '자료구조'다.
16121번: 사무실 이전
첫 번째 줄에 모든 사무실 후보에 대한 모든 직원의 출근 경로 길이의 제곱을 모두 합한 값을 998,244,353으로 나눈 나머지를 출력한다.
www.acmicpc.net
트리DP라는 스포를 받았다. 그 후 생각한 것들을 적는다. 스포 없어도 풀었을거다.
결국 구하는건 a1,...,am과 b1,...,bk 두 수열에 대해
sum( dist(ai,bj)^2 )이다.
x ∈ [1,n] 에 대해 sum( dist(ai,x)^2 )를 구한다.
이걸 O(n)에 구할건데 이를 위해 3가지 sum들을 구해야 한다.
류호석님의 표현: 1-sum, linear sum, square sum
dp1[x]: x의 subtree 안에 있는 ai들의 sum
dp2[x]: x의 subtree 밖에 있는 ai들의 sum
ai들의 sum이라는 건 결국 sum( f(ai,x) <- 3가지 중 하나 )다.
dp1[x], dp2[x]를 2번의 dfs로 채울 수 있다.
간략하게 설명하자면 x와 x의 자식 c를 생각해보자.
c의 서브트리 내에 있는 ai와 x의 거리는
d = ai와 c의 거리보다 정확히 1 크다.
제곱을 생각해보면
(d+1)^2 = d^2 + 2*d + 1
square sum, linear sum, 1 sum이 필요함을 알 수 있다.
따라서 dp1[x]를 dp1[c]들을 이용하여 구한다. (dfs)
반대로 dp2[c]는 dp1[x]와 dp2[x]를 이용하여 구한다. (bfs-like dfs)
요즘 다이아가 능지로 풀린다. ㄷㄷ
12928번: 트리와 경로의 길이
첫째 줄에 N과 S가 주어진다. (1 ≤ N ≤ 50, 1 ≤ S ≤ 1,000)
www.acmicpc.net
deg[i]합이 2*(n-1)일 때 comb(deg[i]-1,2)의 합을 S로 만들 수 있는가
내 첨 풀이: O(N^3 * S * ???)
dp[n][d][S] : 노드가 n개이고 루트의 차수가 d인 트리에서 deg comb 2 합이 S인 트리를 만들 수 있는가
cgiosy평 : 되긴할텐데 뇌절임
d=1일 때 dp[n-1][1~n-2]를 이용해 채움
d>=2이면
n에서 1~[(n-1)/d] 가 크기인 서브트리를 하나 떼어낸다고 생각
dp[n-t][d-1][S-(d-1)-dp[t]] 를 이용해 채움. 여기서 dp[t]는 n=t일 때 가능한 모든 S임.
적당히 될거 같다.
갓기오시 풀이: O(N * S * min(N, sqrtS))
dp[n][S]: deg[i]합이 n일 때 comb(deg[i]+1,2) 합을 S로 만들 수 있는가
deg[i]의 합이 2*(N-1)이고 comb(deg[i]+1,2)이
트리를 단방향 DAG로 생각해줘도 됨. 그럼 outdegree의 합이 N-1이다.
첫번째 노드 - 루트부터 k개의 노드를 연결해준다.
암튼 이런식으로 해서
dp[x+k][S+k(k+1)/2]를 채운다. 암튼 그렇다 ㅇㅇ
2060번: 염소 줄서기
거액 사기도박 혐의로 체포된 아기염소들은 구치소에서 저녁밥을 먹기 위해 줄을 선다. 아기염소들은 각각 저마다의 번호판을 달고 있고, 줄 서는 순서는 이 번호판의 번호에 의해 정해진다. 아
www.acmicpc.net
100 1111 5
4 100
5 101
6 110
7 111
8 1000
9 1001
10 1010
11 1011
12 1100
13 1101
14 1110
15 1111
정렬 하면
100 1000 101 110 1001 1010 1100 111 1011 1101 1110 1111
5번째 수는 1001이 된다.
내가 직접 손으로 셀 때는 카운팅소트처럼
비트 개수 1개인거 : 쭉쭉
2개인거 : 쭉쭉
3개인거: 쭉쭉
이런식으로 했는데 숫자가 20억까지 올라가므로 이 경우 직접세는것은 어려워 보인다.
31C0 = 1 31C1 = 31 ...
수들을 비트의 개수에 따라 분류하면 각 수들은
실제 크기 순으로 정렬되어 있는 것을 관찰할 수 있다.
비트개수 0: 1개
비트개수 1: 31개
비트 개수 2: 31C2개
...
이렇게 쭉 있는데 문제는 그 31Ci개 중 a<=t<=b인 t들만 카운팅해야 한다는 점이다.
이를 살짝 twist해 비트 개수가 c고 0<=t<=x인 수의 개수를 f(x,c)라 정의하자.
비트 개수가 c이고 a<=t<=b인 t의 개수는
f(b,c) - f(a-1,c)가 된다. 물론 f(-1,c) = 0이다.
K번째 수를 c개의 비트를 가진 x라 하면
K = sum_i <- 0 to c-1_{ f(b,i) - f(a-1,i) } + f(x,c)
a와 b는 고정이다.
f(b,i) - f(a-1,i)를 전처리 해놓자.
어떤 x가 주어졌을 때 이게 t개의 비트를 가진 수 중 몇번째 수인지 어떻게 구하는가?
t개의 비트를 가진 수 중 x번째는 어떻게 구하지?
둘 중 하나라도 해결된다면 문제를 풀 수 있다.
(푸는 중)
t개의 비트를 가진 x가 몇번째인지 재귀적으로 구할 수 있다. ncr 전처리와 재귀를 이용하면 31번 연산으로 가능
x 이하의 최대 t개 비트 가진 수를 구하눈 것
x의 비트가 t이상이면 오른쪽에서 차례대로 빼면 됨.
t 미만이면 먼저 x초과의 최소 t개 비트 가진 수를 구한다. 그리고 그 수에서 마지막으로 나오는 10 꼴의 패턴을 찾아서
1을 한칸 쉬프트하고 나머지 1들을 땡긴다
ex) 1 10 0111 ==> 1 01 1110
그러면 x 이하의 t개 비트 가진 최대 수가 구하진다.
이렇게 각 연산이 최대 31번 걸림.
nCr과 a,b에 대한 전처리를 미리해놓고
정답이 가져야할 비트 수를 구한다음
파라메트릭 서치를 돌려서 최종 정답을 구할 수 있다.
푸는 데 꼬박 하루 + 반 소요되고
구현하는데 1시간 걸렸다 ㅋㅋ
1528번: 금민수의 합
첫째 줄에 N이 주어진다. N은 1,000,000보다 작거나 같다.
www.acmicpc.net
dp but 역추적 고려
가능한 금민수가 2^7-2이기 때문에 모든 금민수에 대해 dp를 돌릴 수 있다.
가장 첫번째 수가 제일 작아야하기 때문에 N에서 거꾸로 간다. N에서 0으로 가눈 dp를 세우는데
dp[k]는 당연히 n에서 k까지 만드는데 필요한 최소 금민수의 개수를 저장. pre[k]는 합 에 쓰일 직전 금민수
dp[k], pre[k] 순으로 작아지게 dp테이블을 n에서부터 채운다. for문으로 dp[0]에서 부터 추적 가능.
1520 문제는 n이 10^9이던데 어떻게 풀까
bfs? 그리디?
15318번: 새로운 수열
첫 줄에 N(1 ≤ N ≤ 300,000)이 주어진다. 두 번째 줄에 N개의 정수 ai (|ai| ≤ 109)가 공백으로 구분되어 주어진다.
www.acmicpc.net
b0: 1 -2 3 -4 ....
b1: 1 -2 3. ..
2개 더하면. ? -1 1 -1 1 ...
n의 기우성에 따라 첫번째 원소에 곱할 값이 달라짐. 요지는 b0와 à0-a1+a2 ...값을 전처리해놓아 모든 b값을 O(N)에 구할 수 있다.
'PS > Problem Solving' 카테고리의 다른 글
| 2021년 1월 24일 PS일지 (0) | 2021.01.24 |
|---|---|
| 공부할 예정 목록은 다 여기에! (0) | 2021.01.23 |
| 2021년 1월 23일 PS일지 (0) | 2021.01.23 |
| 2021년 1월 22일 PS일지 (0) | 2021.01.22 |
| If you are a Newbie in Competitive Programming (3) | 2021.01.21 |