행과 열 각각에 대하여 bfs를 돌려주자. 각 단계마다 1*K꼴의 사각형이 존재하는지 확인하고, (1의 개수)*(K의 개수)를 ans에 더해주면 된다. 각 분할의 단계마다 상태는 최대 2가지 존재할 수 있어서 터질 걱정은 안 해도 된다.
기댓값의 선형성. 일단 사이에 추가된 전구를 무시하는 경우는 단순히 \(p_i\)를 다 더하면 되고, 추가된 전구가 켜질 확률은, 이웃한 두 전구 중 하나만 켜질 확률과 같다. 이 확률을 \(sum(P)\)에 더해주면 된다.
kmp의 실패함수를 이용하자. fail[s-1]이 \(\frac{ s(k-1) }{ k }\) 꼴이어야 한다.
이진 트리에서 어떤 원소를 찾는 과정과 비슷하다. 구간 합 세그를 짜고, k와 두 자식노드를 비교하며 타고 내려가면 된다. 다만 오른쪽으로 갈 때는, 우측의 서브트리에서 확인하는 것이므로 seg_L의 값을 빼주자.
여러 트리들 중,
1. 트리의 지름의 최댓값
2. 트리의 반지름의 최댓값 + 트리의 반지름의 두 번째로 큰 값 + \(l\)
3. 트리의 반지름의 두 번째로 큰 값 + 트리의 반지름의 세 번째로 큰 값 + \(2l\)
의 최댓값이 답이다.
상태가 번갈아 나오는 길이의 최대들을 순서대로 다 모으자. \(V_i\ + V_{I+1} + V_{i+2}\)의 최댓값이 답이다.
어떤 선분을 정사각형의 한 변이라고 하면, 나머지 두 점의 위치는 고정된다. map으로 존재 여부를 찾으면 된다. 9015번도 같은 문제다.
재밌는 문제다. 일단, 행의 최대와 열의 최대가 다르면 불가능하다. 가능한 경우를 생각해보자. 최댓값은, \(A_i\)보다 큰 \(B_j\)와, 작은 \(B_j\)를 각각 다르게 처리해주어야 한다. 작은 값들은 어자피 가려지니까 이들의 합이고, 큰 값들은 (개수)*\(A_i\)가 된다. 최솟값은, \(A_i\)가 \(B\)에 존재하지 않으면 다른 곳에서 써주어야 한다. 따라서 \(sum(B)\) + (B에 없는 \(A_i\)들의 합)이 된다.
웰논이다. 불도저로 어떤 선분을 잡아주고, 이 선분을 기준으로 잡아서 양쪽 각각에 대해 이분탐색으로 구간 \([l, r]\)을 구할 수 있다. 이 구간의 길이의 합을 3으로 나눈 값이 답이다.
기하 공부나 해야겠다.
'백준 문제풀이' 카테고리의 다른 글
| 8/15 ~ 8/20 PS (1000 Solve) (8) | 2022.08.20 |
|---|---|
| 8/8 ~ 8/14 PS (0) | 2022.08.14 |
| 7/22 ~ 7/27 PS (0) | 2022.07.27 |
| 7/19 ~ 7/21 PS (0) | 2022.07.22 |
| 7/9 ~ 7/18 PS (0) | 2022.07.18 |