220826 문제 풀이 기록

P5 | 9463 - 순열 그래프

걸린 시간: 20분

체감 난이도: 어쩔수 없이 P5 주는 정도

시도 횟수: 1회

풀이 쓸 의향: 下

풀이:

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

여담: 그냥 세그트리 쓰면 풀리는 세그트리용 날먹 문제. seg 구현할때 등호 넣으면 안되는 식에 등호넣어서 5분 날림.

 

 

 

P4 | 1124 - 바닥 장식

걸린 시간: 1시간 30분

체감 난이도: P4 상위권

시도 횟수: 6회

풀이 쓸 의향: 下

풀이:

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

여담: 내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어내가이겼어

문제 보자마자 풀기싫어서 몸비틀다가 풀이 시작하자마자 문제 잘못읽고 풀다가 때려치려고 하다가 다시 풀다가 틀려서 예외처리하다가 정신이 나가버릴뻔함

저번에 풀었던 리그 (https://www.acmicpc.net/problem/3031)보다 예외 처리랑 구현 더 빡센 문제는 이게 처음인듯

 

풀이 메모

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

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

높이가 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

 

 

 

 

P3 | 21725 - 더치페이

걸린 시간: 1시간 15분

체감 난이도: P3 중/하위권

시도 횟수: 9회

풀이 쓸 의향: 中

풀이:

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

여담: 돈 0원 송금하면 안된다는 조건 때문에 한번 틀렸고, 다른 별 이상한 실수해서 틀렸던건데 풀이 증명 다시하고 반례 이것저것 넣고 assert 조지고 하느라 시도 횟수가 늘어났다.

아니 문제 알고리즘 바로 떠올리고 잘 풀어놓고 왜 구현에서 이상한 실수 하는지 모르겠는데 그냥 지금 졸려서 그렇다고 생각하자...

 

풀이 메모

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