hamayanhamayan https://blog.hatena.ne.jp/hamayanhamayan/ はまやんはまやんはまやん https://blog.hamayanhamayan.com/ 競技プログラミング https://atcoder.jp/contests/dp/tasks/dp_j 前提知識 期待値DP 解説 https://atcoder.jp/contests/dp/submissions/3963610もし考え方違ってたら指摘ください…期待値DPをする。 何番目の寿司かということは特に関係なく、残っている個数毎に集計して問題ない。 すると、制約もあって、以下のDPが考えつく。 dp[c1][c2][c3] := 1個残りがc1個, 2個残りがc2個, 3個残りがc3個である状態にするまでの操作回数の期待値 mathさんの期待値と条件付確率を読む。 これの条件付き期待値を使って解いてみ… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblog.hamayanhamayan.com%2Fentry%2F2019%2F01%2F09%2F001607" title="Sushi [Educational DP Contest / DP まとめコンテスト J] - はまやんはまやんはまやん" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2019-01-09 00:16:07 rich https://blog.hamayanhamayan.com/entry/2019/01/09/001607 1.0 100%