自称ASIC設計者です。どなたかkaggle一緒に出ましょう。動的計画法は全くわからないので、静的無計画法で解く。問題(概要)リスの高橋くんはN個のどんぐりを持っている。AとB二つの換金所が存在し、それらではどんぐりを金、銀、銅の各資源に相互に変換できる。レートは換金所によって異なる。高橋くんはまずAで好きなだけ変換し、次にBで好きなだけ変換し、もう一度Aで変換する。どんぐりの数は最大何個になるか?考え方まず、換金所Aで資源に変えたものを二回目の換金所A訪問時にどんぐりに戻すことはない。換金所Aでどんぐり→銅に変換して、その後換金所Aで銅→どんぐりに戻しても、レートが変動しないためどんぐりの数は変わらないからである。よって、Aで得た資源はBでどんぐりに戻し、Bで得た資源はAでどんぐりに戻すことだけを考える。そこで以下の二つの問題を解く。高橋くんははじめにN個のどんぐりを持っている。Aで資源に変換し、Bでそれら資源を全てどんぐりに戻す。この時点でのどんぐりの数を最大にせよ。高橋くんははじめに問題1で最大化された数だけどんぐりMを持っている。Bで資源を変換し、Aでそれら資源を全てどんぐりに戻す。この時点でのどんぐりの数を最大にせよ。問題1.二重ループで全探索して得られるどんぐりの最大数を求めればよい。ここで、一重目のループは換金所Aにてどんぐりを変換して何個の金を得るかで、二重目のループは換金所Aにて残りのどんぐりを変換して何個の銀を得るかである。ba)であれば可能な限り銅に変換し、そうでなければどんぐりのままとする。計算量はO(N^2)である。問題2問題1と同じ問題を解けば良いように見える、がMが大きくなるケースがある。5000となり、O(M^2)の計算をすることができない。いうことは、換金所Bにて、資源の少なくともどれか一つについてはどんぐり→資源の変換を行う必要がないことがわかる。そこで、場合分けを行う。5000の場合、問題1と同様に解く。5000の場合、1重ループのみを実行する。分岐2についてたとえばどんぐり→銅の変換を行わないとすると、金銀だけを考えればいいことになる。gb)銀に変換し、そうでなければそのまますべて残せばよいことになる。5000のため間に合う。5000の場合分けを思いついた。提出コード見返すとちょっと嘘解法っぽい気もする。sbのケースを考えられてない気がするんですよね。これについては読者の宿題とします(キリッ。»プロフィールid:segafrederverilog書いたり、でもPythonが好きだったり、そんな人の日記。月別アーカイブはてなブログをはじめよう!segafrederさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。