오늘의 PS (28) - 240422

심심해서 문제를 조금 풀었다.

 

19852 공정한 회의

 

얼마 전에 petamingks가 던져 주었던 문제인데, 그 때는 진지하게 생각하지 않았다가 오늘 수업 시간에 갑자기 생각나 다시 잡았다.

 

생각의 흐름

 

triangle을 보았을 때 각 간선의 가중치가 모두 같거나, a a b (a < b) 형태여야 한다.

 

가장 처음 한 것은 불가능함과 동치인 깔끔한 조건을 찾는 것이었다. 정말 많은 시도를 했으나 모두 실패했다.

 

그래서 그냥 풀이를 먼저 찾아보기로 했다. 전에 했던 관찰 중 하나는 MST 느낌으로 간선을 가중치 순서대로 훑으면서 잘 합치는 것이었다. 당시에는 작은 것부터 보아서 반례가 존재했는데, 생각해보니 큰 간선부터 보면 잘 될 것 같았다. 그 이유는 triangle이 a b b 형태일 수 없어서 가장 큰 간선으로 연결된 Connected Component는 같은 가중치의 간선으로 이루어진 Clique 모양이 되어야 하기 때문이다.

 

이를 귀납적으로 확장하면 답도 쉽게 구할 수 있고 불가능 판정도 어렵지 않게 할 수 있다. 주어진 그래프가 연결 그래프가 아닌 경우를 처리해야 함에 유의하자.

 

코딩이 어렵지 않아 패드로 열심히 짠 후, 틀리길래 예제를 하나 만들어 넣고 고쳐서 맞았다.

소신 기여를 했더니 D4였던 것이 D5로 내려갔다.

 

18377 은광

 

북마크에 꽤 오래 있던 문제인데 오늘 뭔가 삘이 와서 잡았다.

 

생각의 흐름

 

저런 연산을 하면 판의 모양이 큰 직사각형으로 이루어진 체스판 형태가 된다. 관련 문제

 

따라서 일단 각 행/열의 inversion 상태를 관리해줄 것이다. \(K\)개씩 묶어야 하므로 레이지 세그먼트 트리를 사용하자. 조금만 응용하면 각 구간에서의 최댓값 뿐 아니라 최댓값의 갯수 역시 저장할 수 있다.

 

이제 \(K\) 크기 정사각형 구간에서의 켜진 점 개수를 세보자. 이 구간에서 켜진 열의 개수가 \(x\), 행의 개수가 \(y\)라면 켜진 점 개수는 \(x(k-y)+(k-x)y = (x+y)k-2xy\)이다.

 

이제 이 식을 잘 분석해보자. 잘 생각해보면 \({k} \over {2}\)를 기점으로 뭔가 나뉜다는 사실을 알 수 있다.

1) \(x, y\)가 \({k} \over {2}\)보다 모두 작거나 모두 큰 경우

이때는 \(x, y\)가 \({k} \over {2}\)에 가까이 있는 것이 이득이다.

2) \(x, y\)가 \({k} \over {2}\)와 비교해 하나는 작고 하나는 큰 경우

이때는 \(x,y\)가 \({k} \over {2}\)에 멀리 있는 것이 이득이다.

 

잘 종합해보면 결국 (가장 많이 켜진 열 갯수, 가장 적게 켜진 열 갯수)와 (가장 많이 켜진 행 갯수, 가장 적게 켜진 행 갯수)를 조합하는 4가지의 경우를 다 보면 됨을 알 수 있다.

 

여기까지 구현한다면 36%까지 가고 틀리는 모습을 볼 수 있다. 열심히 반례를 찾은 결과 아래의 사실을 알 수 있었다.

 

만약 \(k\)가 짝수이고 \(x\)나 \(y\)가 정확히 \({k} \over {2}\)라면 기울기가 0이라서 다른 모든 \(x\) 혹은 \(y\)와 매칭될 수 있기에 이를 확인해야 한다.

 

이 경우를 고려해야 하는 경우는 답이 \({k^2} \over {2}\)일 때이며, 이는 다음 두 가지 중 하나에 해당한다.

1) \(x, y\)가 \({k} \over {2}\)보다 모두 작으면서 적어도 둘 중 하나의 최댓값이 정확히 \({k} \over {2}\)인 경우

2) \(x, y\)가 \({k} \over {2}\)보다 모두 크면서 적어도 둘 중 하나의 최솟값이 정확히 \({k} \over {2}\)인 경우

 

이 둘에 해당하는지 검사한 후, 만약 그렇다면 적당한 수식 계산을 통해 가짓수를 새로 구해주면 된다.

 

 

17399 트리의 외심

 

다이아 문제를 2개나 풀었더니 힘들어서 클8에서 적당히 쉬워 보이는 문제를 잡았는데, 정작 앞 문제들만큼 고생해서 풀었다.

 

생각의 흐름

 

그냥 LCA 케웍 뚝딱인가?

케이스 나누는 중..

(N번 틀리고 뭔가 이상함을 깨달음)

 

이상의 과정을 거친 후 똑똑한 풀이를 찾아서 풀었다. 엄청 대단한 풀이도 아닌데 너무 뇌를 안 쓰려 하다 보니 손해를 본 느낌이다.

 

풀이 요약)

3개가 모두 같거나 2개가 같은 경우는 웰노운이다. LCA로 잘 처리해주면 된다.

3개가 다 다른 경우는 이 정점들로 만든 subtree가 Y자 모양이어야 하고 & 가장 먼 두 점 간의 중점이 외심이어야 한다.

 

추천만 받고 버린 문제가 한둘이 아니긴 하지만 문제 추천도 받습니다. 감사합니다.