Educational DP Contest J - Sushi
DPの練習をするためにEducational DP Contestの問題を解いた。典型的で簡単な問題らしいが、序盤から僕にとっては難しい問題が多くあった。
その中で、僕からすると簡単ではなかったけれど解けて嬉しかったのがJ問題。確率を求めるようなDPは見るけれど、期待値を求めるという問題は初めて見た。問題文を見た時点では方針がわからなかったが、最初のテストケースの解説がヒントになっていて、それなりに素直にDPに落とし込めた。とはいえ、DPと分かっていなかったら解法が思いついた自信はない。
しかし、久々に競プロの問題を解いたとはいえ実装でミスをしてなんどもWAなどを出してしまった。最初の実装では明らかに高速化・メモリ削減ができる要素を見逃していたりしたので、そういった点をなくせるようにしていきたい。
