9/5 ~ 9/11 PS

 이걸 밀고싶었는데, 너무 어려워서 결국 포기했다..

 

 

BOJ 18184 - 분할하기 (P4)

 가장 높은 곳에서 켜진 비트가 k번째에서 켜졌다고 하면, 이러한 수는 \(2^{k-1}\)개 존재한다. 또한 모든 수는 2의 거듭제곱의 합으로 나타낼 수 있으므로, 답은 항상 존재한다.

 

 

BOJ 18193 - 비행기 타고 가요 (D4)

 구간 간선 테크닉 + 다익스트라.

https://www.acmicpc.net/problem/25392

 

 

BOJ 18194 - Bad Hair Day와 기댓값 (P1)

 \(i\)번째 소보다 작은 소가 \(k\)마리라면, 이들보다 큰 소들 \((n-k)\)마리를 먼저 세워볼 수 있다. 여기서 사이사이에, 즉 \((n - k + 1)\)칸에 소 \(k\)마리를 잘 배정할 것이다. 당연하게도 \(i\)번째 소 바로 옆에 이보다 작은 소 한 마리가 올 확률은 \((n-k+1)^{-1}\)이고, 여기에 \(k\)를 곱한 값이 \(i\)번째 소에 대한 기댓값이다.

 

 

BOJ 25517 - 머리 아픈 암산은 이제 그만! (P4)

 1000만씩 잘라서, \(x\)부터 \((x+10^7)\)까지 곱한 값들을 전처리해두면 된다.

 

 

BOJ 2180 - 소방서의 고민 (P5)

 exchange argument. \(b/a\)가 작은 곳부터 진압하면 된다.

 

 

BOJ 13560 - 축구 게임 (P5)

 랑주 정리. \(C(i, 2)\)보다 지금까지의 합이 더 커야 한다. C는 이항 계수이다.

 

 

BOJ 6567 - Let it Bead (P5)

 번사이드 보조정리 기초문제다. 설명이 귀찮은 관계로 https://algoshitpo.github.io/2020/02/09/burnside/ 로 대체한다.

 

 

BOJ 13433 - 기하 문제 (G1)

 \(N!\)가지의 경우를 다 돌려보면 된다. 바로 옆 원에서 접하지 않을 수 있음에 주의해야 한다.

 

 

ARC147D - Sets Scores

 \(i\)번째와 \((i-1)\)번째에서 새롭게 등장하거나, 사라지는 원소를 \(A_i\)라고 하자. 길이 \((N-1)\)의 수열 \(A\)으로는 총 \(M^{N-1}\)가지가 있다. 각 점수는 \(N^M\)이 되므로, 총 점수는 \(N^M \times M^{N-1}\)가 된다.