D - Xpectation of Cards in Hand with Laboratory 解説 by evima 印刷ページ
When all operations draw two cards
Let \(a\) and \(b\) be the number of draw cards and normal cards drawn from the deck so far, respectively. The condition for the hand to run out of draw cards is that \(b = a + K\) occurs for the first time. The number of orderings of \(A + B\) cards satisfying this is \(\left(\binom{a+b-1}{a} - \binom{a+b-1}{a-1}\right) \times \binom{A-a+B-b}{A-a}\).
When some operation draws at most one card
The condition for this to occur is that \(b < a + K\) holds at all times. The number of orderings of \(A + B\) cards satisfying this is \(\binom{A+B}{A} - \binom{A+B}{A+K}\).
Summary
Multiplying each of these by the final hand size and summing gives the answer. The time complexity is \(O(A + B)\).
The problem can also be solved when the number of cards drawn from the deck is \(\min(c, x)\) for an integer \(x \geq 2\) rather than \(\min(c, 2)\).
投稿日時:
最終更新: