7/22 ~ 7/27 PS

kmp 공부 해야되는데..

 

 

BOJ 19586 - 울타리 (D5)

2차원 평면의 점에서 가장 거리가 먼 두 점은, Rotating Calipers를 이용하여 구할 수 있다. 이를 응용해서 90도와 270도 방향의 직선을 찾을 수 있다. 벡터의 내적과 외적을 이용하면 된다.

 

BOJ 11000 - 강의실 배정 (G5)

스위핑?처럼 풀 수 있다. 구간 $[l,r]$에서 $l$에는 +1, $r$에는 -1을 해주고, 쭉 훑으면서 최댓값을 찾으면 된다.

 

BOJ 25392 - 사건의 지평선 (D4)

$a_i$가 담당하고 있는 구간 $[l,r]$에 속하는 수들에 간선을 쭉 보내주자. 어느 순간부터 수가 일정하게 반복된다는 것은, 어떤 정점이 간선을 타고 가다가 scc에 들어가는 것을 말한다. 그럼, 그래프에서 scc를 구하고 dp를 돌리면 해결될 것 같지만, 간선이 최대 $N^2$개 존재할 수 있다. 이를 해결하는 방법은, 세그먼트 트리처럼 구간 간선을 이용하는 것이다. $[1,2,3,4]\to [1,2]$와, $[1,2,3,4]\to [3,4]$ 이런 식으로 작은 구간들에 간선을 보내주고, 앞서 말한 '구간에 간선 보내기'를 하면 된다. 이러면 간선의 개수를 $NlgN$개로 줄일 수 있다. https://www.acmicpc.net/problem/18193 에도 같은 테크닉을 사용한다.

 

BOJ 20190 - 버블버블 (P1)

일단, inversion의 개수를 세는 것은 웰논이니 넘어가자. $A_1$부터 본다고 할 때, 이 수를 다른 수로 바꿀 때 inversion의 개수가 어떻게 바뀌는 지를 알아야 한다. 먼저, 각 수마다 구간 $[x+1,inf]$에 1을 더해주자. 그리고 1번째 수부터, 각 수가 담당하던 구간에서 1을 빼주고, 전체 구간에서 최솟값을 찾아주면 된다. 이 값은 수 변경으로 인해 추가되는 inversion의 개수이다. 전체 inversion 개수에서 $A_i$가 속하는 inversion의 개수를 빼고, 여기에 방금 구한 최솟값을 더해주면 되는 것이다. 이게 끝나면, 구간 $[-inf,x-1]$에 1을 더해주어 j < i인 inversion을 구할 수 있도록 하자.

 

BOJ 19277 - ADD, DIV, MAX (D1)

세그비츠 복습을 위해 풀었다. min/d == max/d인 경우, min/d != max/d이고 min + 1 == max인 경우에 갱신하면 된다. 앞의 경우는 구간 값 변경 레이지로 보내고, 뒤의 경우는 구간 값 추가 레이지로 보내면 된다.

 

BOJ 18702 - Array Quaries (D1)

이것도 복습용이다. sqrt(min) == sqrt(max)인 경우, sqrt(min) != sqrt(max)이고 min + 1 == max인 경우에 갱신하면 된다. 위 문제와 똑같이 레이지를 보내면 된다. 근데 이 문제 FastIO를 안 쓰면 시간초과 난다 ㅋㅋ;;

 

BOJ 18665 - IQ Test (P5)

dfs 돌리면 된다. $x=\lceil \sqrt{N}\rceil$, $y=x^2-N$으로 두고 {x, y} 페어가 set에 존재하는지 확인하면 된다.

 

BOJ 15403 - Escape Room (P5)

$A_i$가 큰 쪽부터, 같다면 $i$가 큰 쪽부터 채우면 된다. 물론 1부터 채워야 한다.