다이아 1일1제

2021년 7월 31일까지 PS에서 실시함.
https://www.acmicpc.net/group/9175
p.s) 원래는 개인적으로 진행하던 프로젝트였으나, 때마침 cgiosy와 뜻이 맞아
격일로 플*2 +다5*1 // 플*1+다5*2 문제풀이를 실시한다.
Routine: 매일 아침 저녁 내일 문제 3개 프린트 + 다음 날 문제 풀이

20210531: 10124 다5

Merge Sort Tree와 Small To Large의 아이디어를 차용해서 풀었다.

O(N log^2 N)
각 Value 1~N에 대한 인덱스를 저장해서 벡터를 만들고 Merge Sort Tree를 만든다.
포인터를 이용해서 구현했고, 별도로 좌표압축 또한 하지 않았다.
포인터 안쓰는 구현으로 바꾸면 더 빨라진다
풀면 보세요: https://www.acmicpc.net/source/29724489 

정풀 관련해서 볼 것들
https://www.acmicpc.net/problem/2912 이 문제의 Hard 버전이므로 세그 쓰는 풀이가 대표적
지금까지 본 문제 중에 가장 풀이가 다양하다
빠른거 순으로 비트 응용, PST, 보이어-무어 + 세그, 머지소트트리, 랜덤, Mo's(될까?) ... 

20210601: 8177  다4

Hall의 결혼 정리는 이분그래프에서 사용하는 정리다.

G(L+R, E)에 대해 Perfect Matching(L의 모든 정점에 대응되는 R의 정점이 있는 매칭)이 존재 (1)할 필요충분조건
: L의 모든 부분 집합 S에 대해 S의 원소들에 연결된 R의 원소들의 합집합을 T(S)라 할 때 
|S| <= |T(S)| (2)

(1) -> (2)는 자명, but (2) -> (1)은 어려운 조건이다.
이에 관한 자세한 내용: https://gazelle-and-cs.tistory.com/10 (좋은 블로그)

Ice Skate의 풀이가 궁금하다면 내 블로그 말고도 많으니 구글링 해보시기를 ㅋㅋ
풀이를 보다보면 모든 부분집합을 봐야지, 왜 연속한 구간만을 봐도 되는가? 라는 질문이 생길 수도 있는데
이는 2가지 케이스로 나눠서 생각하면 편하다.
부분집합이 2개의 연속 구간으로 나뉘어져 있다고 생각하자.
[a,b] -> [a,b+X]
[c.d] -> [c,d+X]에 대응될텐데
1) 두 구간이 겹치면 [a,b]와 [c,d]를 [a,d]로 합쳐줘도 무방하다. [a,d]에서 [a,d+X]로 향하는 perfect Matching이 있는 경우 (b,c) 구간의 Matching만 지워주면 처음 조건을 만족시키기 때문이다.

2) 두 구간이 겹치지 않으면 [a,b], [c,d] 두 연속한 각각의 구간에 대해 각각 조건을 만족하는지 확인하면 처음 조건도 자연스럽게 만족한다.

따라서 연속한 구간에 대해서 조건을 만족하는지만 확인하면 된다.
수식을 전개하면 모든 [a,b]에 대해 sum(xi)  <= k * (b+d-a+1) = k*d + k*(b-a+1)이라는 식이 나오는데
이게 너무 신기하다. 아름답게 sum(xi-k) <= k*d라는 식으로 바뀌면서 배열 초깃값을 -k로 잡으면 이 문제를 최대연속합 문제로 환원시킬 수 있다. 어떻게 이런 문제를 내는 것인지 신기함.

진짜 여담.
Maximum Independent Set과 Minimal Vertex Cover Set이 여집합 관계인 것은
Vertex Cover의 정의를 통해 쉽게 알 수 있다.
Vertex Cover은 모든 간선에 대해 한 점 이상을 차지한다. 따라서 그 여집합에 대해서는 두 정점이 연결될 '간선' 자체가 존재하지 않는다. 이미 Vertex Cover한테 뺏겨버렸기 때문이다 ㅋㅋㅋㅋㅋ 그래서 여집합은 Independent Set이 되고, 이것이 Maximalize 되기 위해서는 Vertex Cover Set이 Minimal이 되면 된다.

20210602: 16225 15014 12766 다5 플5 다5

16225 제271회 웰노운 컵

B값 오름차순으로 정렬. 1번 문제는 무조건 내가 먹는 걸 이용하기 위함임.
1번 ~ 2i-1번 문제에 대해 매칭이 일어나기 위해서는 내가 i개 이상 문제를 먹어야 함. 
이 조건을 맞춰주기 위해 (2,3)번, (4,5)번.... 2개씩 보면서 하나씩 먹어줘야 함.
이때 지금까지 본 문제들 중 가장 큰 문제를 먹는 것이 가장 이득이다.

처음부터 2개씩 끊어서 보는 것보다 1~i번 문제를 봤을 때 무슨 조건이 맞춰져야 하는가 이게 엄청 중요한 듯

B가 큰 순으로 봤을 때도 B에 대해 위 조건이 똑같이 적용되는 것을 알 수 있다.

15014 Lemonade Trade

레모네이드를 통째로 옮기는 것이 항상 최대다.
수가 매우 커질 수 있으므로 '로그'를 사용하는게 핵심이다.
수학이 아주 중요해!

20210603: 14905 골3 21607 플1

14905 소수 4개의 합

시간복잡도 계산의 허점을 알려준 문제
1억까지여서 도저히 시간 안에 안 돌 것 같지만,
짝수를 두 소수로 분해할 때 대부분 1000 이하의 소수와 나머지로 분해하는 성질이 있어서 브루트포스가 체를 적용했을 때보다 훨씬 빠르게 동작한다.

21607
체비쇼프 다항식
교환법칙이 성립한다. (cos x -> cos nx, 해가 -1과 1 사이 무한 개의 실수이므로 합성 사이에서 교환 법칙 성립)

20210604;

20210605:

20210606: