피곤하다
Vandermonde's identity를 사용하는 문제다. 위키에 있는 걸 그대로 사용하면 됨
우측으로 쭉 이동 -> 한칸 아래로 -> 쭉 왼쪽으로 ... 이렇게 반복하여 내려가면 된다. 그리고 지금 보고 있는 칸이 원하는 상태와 다르다면, 앞으로 갔다가 뒤로 가주고, 다시 앞으로 가주면 된다.
각 행, 각 열의 기우성은 변하지 않는다. 각 행마다 타일의 등장 횟수를 세고, 기우성이 동일한지를 확인해주면 된다. 좋은 문제라고 생각한다.
N의 값이 매우매우 작다. 가능한 \(N^4\)가지의 모든 쌍들에 대해, 각각을 직사각형의 상하좌우 변으로 고정하자. 여기서 직사각형 외부의 나무들을 다 잘라서 울타리를 짓는 것이 가능할 때 ans를 갱신하면 된다.
BOJ 18086 - Gnoll Hypothesis (P5)
i번째에 대한 기댓값을 찾아보자. i - d의 확률이 i번째로 넘어오기 위해서는, i - d부터 i - 1까지는 선택되면 안 된다. 그러면 나머지는 n - d - 1개 중 d - 1개를 뽑는 경우의 수와 같다.
진짜 너무 좋은 문제다. 일단 올리브의 볼록 껍질을 구해주자. 피자의 꼭짓점을 P1로 고정하고, 여기에서 올리브의 볼록 껍질의 꼭짓점 중 가장 오른쪽에 있는 것을 뽑아주자. 이분 탐색 등으로 이러한 점 k를 찾을 수 있다. 이제, 시점이 P1이고, k를 지나는 벡터에 대해 투 포인터로 P2를 가장 멀리 보내주면 된다.
이것도 너무너무 좋은 문제다. 선분의 양 꼭짓점만 들고 있으면 된다는 사실은 쉽게 알아낼 수 있다. 한 점에 대한 다른 점들의 기울기로 점들을 정렬한 후, 스위핑을 해주면 된다. 한쪽 끝은 +k, 다른 쪽 끝은 -k로 두면 된다.
'백준 문제풀이' 카테고리의 다른 글
| 백준 18032 - Dazzling Stars (0) | 2022.10.17 |
|---|---|
| 9/26 ~ 10/9 PS (0) | 2022.10.10 |
| 9/12 ~ 9/18 PS (+ 앳코더 민트) (0) | 2022.09.19 |
| 9/5 ~ 9/11 PS (0) | 2022.09.11 |
| 8/29 ~ 9/4 PS + 매우 짧은 SUAPC 후기 (4) | 2022.09.05 |