cdjs의 코딩 공부방

동일한 수의 연속하는 원소는 반드시 동시에 올리거나 내려야 한다는 점을 잘 파악하여 증명한 뒤, 각 값과 연속되는 구간을 저장한 뒤 그리디하게 가장 작은 값들의 구간부터 1씩 올리면서 최적값 찾기

반드시 겹치는 사이클이 존재하는데, 해당 사이클을 잘 찾아서 연산하기

없어지는 원소들을 잘 관리하면서 세그먼트 트리 활용하기. 크기가 x인 값을 처리할 때 현재 시간이 몇인지 잘 기록하고, 이미 실행이 끝난 프로세스 값을 1로 바꾸면 구간합 세그트리로 해결 가능하다.

각 여행지들을 각각 시작점으로 잡고 최대 힙으로 최대 기대치가 되는 다익스트라 돌리기

각 칸은 두번 이상 누를 일 없음 + 맨 윗줄을 어떻게 누르느냐에 따라서 아래쪽을 어떻게 눌러야 하는지 확정적으로 알 수 있음을 이용하여 브루트 포싱

장황한 순열 그래프 뭐시기는 낚시용이고 그냥 교차하는 선분의 개수 구하면 됨. 위쪽 노드를  왼쪽부터 순서대로 고르면 (b[a[i]], n) 구간의 합을 구하는 세그트리로 구하면 됨.

(x1, y1)에서 (x2, y2)까지 개수를 어떻게든 열심히 예외처리하면서 크기가 1, 2, 3, 4, 5인 개수 각각 다 구하고 그리디하게 큰것부터 넣어주면서 개수 세기

으악
으악 이게 뭐야
아니 이걸 풀라고? 아니 으악 살려줘 으악

ㅡ ㅣ ㅡ ㅣ ㅡ ㅣ
ㅣ ㅡ ㅣ ㅡ ㅣ ㅡ
ㅡ ㅣ ㅡ ㅣ ㅡ ㅣ
ㅣ ㅡ ㅣ ㅡ ㅣ ㅡ

높이가 5면 당연히 위아래 5인거 넣는게 최적임. 그니까 틀에 딱 맞춰서 넣는게 최적이다.
높이가 6이면? ㅡ 로 돼있는거는 그냥 하나 추가지만, ㅣ로 돼있는거는 5개나 추가되니까, 그리고 어차피 나열되니까
사실 높이가 뭐든지간에 위쪽을 틀에 딱 맞추는게 그냥 최적임
뭐 높이를 맞추든 너비를 맞추든 그게 그거같지만 아무튼 가장 윗변을 맞춰서 가자.
그럼 이제 좌우로 움직이면서 .. 어라 ㅅㅂ 잠깐만?
아냐 이게 맞아

이제 좌우만 따지면 되는데
근데 똑같은 논리로 그럼 좌우도 면에 딱 붙이는게 최적이어야 되는거 아님??
그냥 왼쪽 위에 맞춰서 계산하면 되는거 아님???

아니 문제 잘못읽었네 ㅅㅂㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
어쩐지 쉬워보이더라
그래도 접근은 비슷하게 하면 될것 같은데...
아니네


일단 문제 파트가 두갠데
1. (x1, y1), (x2, y2)에 있을 때 크기 1인거부터 5인거까지의 개수 구하기
2. 크기 1인거부터 5인거까지 개수가 있을 때, 크기 5 최소 개수만 써서 그거 만들기


근데 2.는 쉬운게
4를 만드려면 어차피 1이 나오게 되어 있음 --> 4 최대한 만들자
3 만들면 1 1 이나 2로 사용 가능한데, 1 만드는게 더 쉬우니까 3 개수에서는 2 최대한 넣고 넣은 후에는 다 1 넣으면 됨
그냥 그리디로 짜면 된다

1번이 문제야 1번이 ㅅㅂ 개귀찮아
이게 가운데 있는 꽉 찬 애들은 그냥 하면 되는데
끝부분 잘라먹기를 해야되는게 참...
개하기싫다
푼사람도 얼마 없겠지
22명이면 생각보다 많네
플4는 풀이를 도전하는 용기에서 나오는 난이도인건가
ㅅㅂ...

2 2 8 8
(2, 2) ~ (5, 2)
(5, 2) ~ (8, 2)


아 괜찮은 방법 없나?
음
어차피 뭐 좌표 크더라도 왼쪽 위를 왼쪽 위쪽으로 옮기면 무조건 왼쪽 위 좌표는 (10, 10)보다 왼쪽 위로 압축이 가능한데
전체에서 (0, 0) ~ (10, 10)는 그냥 다 저장 해 둔 상태에서, 범위 따라 구현하자

아익

상하좌우 그냥 다 해버리자
안해시발

후.... 그래 그래도 해야지 ㅅㅂ
왼쪽에 겹친 ㅡ 부분의 개수, 오른쪽에 겹친 ㅡ 부분의 개수, 위쪽에 

(8, 5) ~ (20, 16)에서,
(8, 5) ~ (10, 16)에 있는 ㅡ의 개수 : 6, 크기 : 2
(8, 16) ~ (20, 16)에 있는 ㅣ의 개수 : 5, 크기 : 1
나머진 모두 안에 있으니 그냥 하면 됨

ㅇ?ㅇ?ㅁㄴㅇ?ㅁ?ㅃ?!@?# ㅃ!?ㅇㄹㄴ ?ㅁㄴㅇ?ㄹ ㄴㅁㅇ? #? ?

4 0 10 2

disjoint set으로 합쳐 가되, 작은 집합과 큰 집합을 합칠 때는 작은 집합 값을 정리해주며 진행. 한 그래프 안에서의 총 지출 금액과 각 사람이 지출한 금액을 저장하고, 마지막에 쭉 돌려주면 각 사람이 내야 하는 / 받아야 하는 금액이 전부 나오고, 한명 총무로 삼아서 돈 송금하면 된다.

disjoint set

각 사람이 다른 사람들에게 내야 하는 돈의 양을 저장해 두자
라고는 해도?
이거 어떻게 구현하지
뭔가 정공법으로 자료구조 짜야될거 같은 듯한 그런 느낌

아 잠깐만
1->2 2->3 같이 송금하는게 가능하잖아?
지출 금액을 생각하면

(지출 금액 - 빚진 금액(자기에게 빚진것도 포함))을 저장하자

가령 예제의 경우,
1: 20 / 2: -31 / 3: 11

2가 1에게 20, 2가 3에게 11 주면 그냥 되잖아

근데 해당 그래프에 있는 모든 사람들에게 적용하는거?
합쳐질때 넣으면 됨
그니까 한 그래프의 루트에 (또는 그냥 구조체 만들어서) 박은 다음에
합쳐지기 전에 나눠주자


그럼 그냥 나눠주는게 아니라 
sz 자체가 작은 쪽이 큰 쪽에 융화되면 될듯?

그니까 노드 개수가 적으면 

노드에 각자가 지출한 금액을 넣어두고, 각 그래프에 대해 각자가 지출한 금액의 값의 합을 저장하자
나중에 계산할때는 각 그래프에 대해 (그래프 총 지출금 / 그래프 크기)만큼 내야 하는 돈을 추가해 준다.

크기가 작은 쪽이 큰 쪽과 융합될 때, (큰 지출금 / 큰 크기)
?
융합되면 그냥 똑같나?
그건 아니네
어차피 나중에 total 값을 저장할거니까
작은 그래프 청산 하고나서 큰 그래프에 넣어주자

가령
   40            24
4 8 12 16    10 14
라고 한다면
24 / 10 14 그래프를 먼저 조져서 total값에 각각 10-12, 14-12 값을 더해주고
노드값을 40/4=10으로 초기화해준 다음에 total값은 40/4*2만큼 늘려준다.

disjoint set을 구현하면서 size를 넣어주고,
해당 disjoint set에 들어 있는 노드들을 저장해 주고
ㅇㅋ
ㄱㄱ'

잠깐!

노드값들은 그냥 tot값에만 저장하고
sum 만 더해주면 나중에 문제 없다
그니까 tot 이 10, 14일때, 24/2를 빼고 40/4를 더해주자.

-20 -5 10 15

ㅇㅎ..

그냥 1번이 총무 하자 ㅋㅋ

5 7
1 2 3
1 4 5
2 2 2
2 3 2
2 4 6
2 5 6
1 1 5

높이 있는 노드부터 차례대로 내려오면서 최대값 저장하기.

비용 큰 간선부터 차례대로 간선 연결하면서, disjoint set으로 간선이 연결하는 그래프의 크기 고려하면서 정답값 더해주기.

가중치가 가장 작은 / 큰 간선은 몇 번 제거될까

작은 간선들을 보면?
가령 가중치가 2인 간선은 그냥 뭘 해도 다 없어지네?
!
MST
MST...가 맞나
Maximum?
Maximum spanning tree를 구성하자.

그럼 예제 그래프에서 남는 간선들이?
15 10 6 5 4가 된다
제거되는건 2, 3 <-- 얘들은 모든 두 정점 (u, v)에 대해 그냥 계속 없어지니까, N(N-1)/2번 없어진다
이제 작은것부터 보자
4도 뭘 해도 끊어진다
5는? (4 끊을때 5번 노드가 끊기므로) 5번 노드가 들어간 거 빼고는 다 끊어진다
6은? (5 끊을때 4번 노드가 끊기므로) 4번 노드가 들어간 거 빼고는 다 끊어진다
10은? (6 끊을때 그래프가 1-2, 3-6으로 나뉘므로) 

음
그래프가 나뉘는데, 각 그래프의 크기에 대해
어떤 한 그래프에서 다른 그래프로 연결하는 개수만큼..? 쫌 복잡하네요,,, 으엑

(1, 2) : 10 이하 다 끊김
(1, 6) : 6 이하 다 끊김
(1, 3) : 6 이하 다 끊김
근데 이렇게하면... N^2이잖아...

모든 그래프에서, 각 그래프 크기를 x라 하면,
sum(x(x-1)/2);
이게 깔끔하네
4:15
5:10
6:6
10:2
15:1

9*15 + 50 + 36 + 20 + 15



근데 구현을 어케함 이걸
uf 쓰기 싫은데
아니 uf 써도 시간 안에 되나
끊는거보단 잇는게 쉬우니깐...
큰거부터 이어볼까

!!

큰거부터 이어서 조지자
연결됐을 때, (x + = sz[s]*sz[e]), ans += v[node] * x;

ㄱㄱㄱㄱㄱㄱ
근데.. 그럼 사실 MST 필요없는거 아닌가
으익..!!!!
이미 연결되어 있었다면 x 증가 안시키고, 연결 안되어있었을 때만 증가시키게 하면 될듯
ㄱㄱ

세그트리에 값 하나가 아니라 두개를 넣거나 두개의 세그트리를 따로 만들어서 값을 구하면 되는 문제.

실력 차이가 D 이하인 가장 큰 구간을 투 포인터로 구하고 나서 그 안에 사람들 죄다 돌려보며 구하기

문제 상황을 그래프로 추상화한 뒤에 관찰을 통해 terminal node를 고르는 것이 최적이라고 증명한 뒤 나머지 남은 cycle은 dfs 돌리면서 size/2만큼씩 더해준다.

서로 지목하지 않은 사람의 최대 수
그래프로 생각하면

어떤 그룹이 있을 때, 해당 그룹끼리는 서로 화살표가 연결되어있지 않은 최대 크기의 그룹?

1->3
2->3
3->4
4->5
5->6
6->4
7->4

?
노드 N개, 간선 N개인 그래프
사실 유향 그래프일 필요가 없는게 연결되어 있으면 절대 서로가 마피아가 아님.
홀짝놀이

노드 N개, 간선 N개인 무향 그래프에서 서로 이웃하지 않은 노드들의 최대 갯수

간선 N개인게 많이 중요할까
읆...

dfs dp로 되나

cycle 하나 떼면 트리인데...

dp[x][0] : x번 노드가 마피아가 아닐 때, dp[x][1] : x번 노드가 마피아일때 
쩝,,


연결된 개수가 작은걸 제일 먼저 고르는게 무조건 낫나?
그니까 어떤 노드를 고르면 연결된 다른 노드를 절대 고를 수 없는데, 어떤 노드를 고르지 않으면 다른 노드를 고를 수 있는 가능성이 생긴다
가령 1-3 끊으면 1, 3 disable, 2:0, 4:3
2


간선 N개니까 시간 안에 됨
제일 작은거부터 고르되, 제일 작은게 누구인지 계속 봐줘야됨



이거 뭔가 증명이 안되는데...
!
terminal을 고르는 것이 무조건 best이다
그럼 계속 terminal을 찾아서 제거하자