BOJ - Bad Hair Day와 기댓값

• https://www.acmicpc.net/problem/18194
• 소 $N$마리가 일렬로 줄을 선다. 각 소는 오른쪽을 바라보는데, 자기보다 키가 크거나 같은 소가 나오기 전까지의 모든 소를 볼 수 있다. 이때 모든 줄 세우기 순열 $N!$에 대해, 관측 가능한 소 쌍 수의 기댓값을 구하여라.

Idea

• 기댓값의 선형성을 쓰는 건 자명하다.
• 관측자 소 $i$를 고정시켜두고, 몇 마리의 소를 볼 수 있을지에 관하여 조합적인 식 정리를 할 수 있다.
• 시그마 식이 나오는데, nPr을 nCr 꼴로 변형시키면 하키스틱으로 $O(1)$에 계산할 수 있는 꼴이 나온다.
• 예외처리 ($i$번째 소의 오른쪽에 더 높은 소가 없는 경우)를 해 준 후 계산하면 끝.

Reflection

• 식은 바로 세웠는데 $O(1)$에 어떻게 계산해야 할지 모르겠어서 좀 헤맸다. 찾아보니 하키스틱 공식이 나왔다.
• nPr을 nCr로 정리한 건 잘 한 것 같다.

Takeaway

• 이런 문제를 풀 때 가져야 하는 태도
  • 기댓값의 선형성으로 독립 확인하고 잘 카운팅하기
  • 하나를 고정하고 나머지를 카운팅하기
• 느낀 점, 얻어갈 점
  • nCr에서 n이 증가하는 꼴이면 하키스틱 공식을 생각해보자.
  • $r * {n \choose r}$같은 복잡한 합공식도 팩토리얼을 잘 쪼개서 상수항을 만들고, 다른 공식을 변형해서 $O(1)$에 계산할 수 없을 지 고민해봐야 한다.
  • ${a+b \choose b} = {a+b \choose a}$ $\rightarrow$ 시그마 식에서 유용

Notes

• statements_open.pdf