問題 週末yukicoder。ずっと動的計画法の練習です。 解法 おなじみ動的計画法で解きます。一度選んだアトラクションが再度選べるのとその際価値が前回の半分（切り捨て）になるところが、ちょっといつもの問題と違うところですね。 アトラクションの価値が元…

週末yukicoder。 問題 問題はこちら 解法 動的計画法です。 個のお寿司が手前に流れてきたときの美味しさの最大をとします。この時と定義しておきます。 の時はお寿司が１つだけなので、そのお寿司を取るしかないので、 の時について、場合を分けて考えてみ…

個の町々で目的の町を目指して、時間内にもっとも安い値段で辿り着く場合を求める問題です。 問題 問題はこちら 解法 動的計画法で解きます。 ちなみに動的計画法の参考記事では下記の記事がとてもわかりやすいです。 典型的な DP (動的計画法) のパターンを…

お馴染み yukicoder で勉強です。慣れてきたので簡単な問題はサクサクコードかけるようになってきました。 問題 問題はこちら 解法 動的計画法(DP: Dynamic Programming)です。中でも一番よく聞く簡単なフィボナッチ数列です。 ] 数式にすると次の関係があり…

久々に競技プログラミングやります。やり方を忘れているので簡単な問題から徐々に思い出していきます。 問題 問題はこちら 解法 食べられる野菜の最大の数を とします。 すると問題分より下記の関係を満たす。 野菜の個数は最大 個 個の肉を食べる必要がある…

久々の投稿になります。 さて、最近の私の暇つぶしが「競技プログラミングをする」になっています。と言っても始めたばかりですが・・・。 少し空いた時間にでも問題を眺めて思考を凝らしています。 オンラインで競技プログラミンが楽しめるWEBサイトはいく…