はむ吉(のんびり)の練習ノート

主に(競技)プログラミングや言葉について,思いついたことや,試してみたこと,学んだことを,覚え書きを兼ねてまとめます.その際に参考になった,書籍などの紹介も行います.

動的計画法

問題集から一問無作為に選び出題するのを繰り返したときの,既出の問題数:あるいは,多面サイコロを繰り返し振ったときの,出た目の種類数

問題集から一問無作為に選んで出題するのを繰り返したときに,既出の問題数にまつわる確率と期待値を,とある経緯で知りたくなりました.これは,面,あるいは目の数がかなり多いサイコロを繰り返し振ったときに,これまでに出た目の種類を考えるのと等価に…