2019の記事ではありません。(面白い記事がたくさんあるのでぜひチェックしてみてください!!1)この記事は何?弊社アドベントカレンダーの5日目に同僚のakht氏がこのような記事を書きました。akhtikd.comakht氏は競技プログラミング(以下、競プロ)にハマっており、それを活かして身近にある問題を競プロっぽく見立てて解決したという面白い記事です。お読みください!(この記事より先に読んで)で、今日そんなakht氏が社Slackの某チャンネルでこのような発言をしていました。(ちなみに文章中のモザイクは社Slackで僕を表すときによく使用される絵文字です)なんか突然捧げられてしまった...ということでこれを解いていきます、という謎な記事です。問題文は上記の記事をご覧ください。100でも解けるようにしてくれとのことでした。解けているであろうコードを先に貼っておきます。endl;}O(2^N)ではとても厳しいので動的計画法(以下、DP)を用いて解きます。「DPとは?」みたいな記事はインターネット上にたくさんあるので、気になる方は調べてみてください。やっていることは大きく分けて2つで、DPで最適解を求めることと復元です。DPについてはあまり言うことがないのですが、配列に領収書の金額を組み合わせてこの金額にできるかどうかを持たせてやれば良いです。今回重要なのが復元です。どの領収書を選ぶかが重要なので、最適解を求めたときにどれを選んだのか分かるようにします。コードのようにdpを更新するときにどの値から更新されたのかをprevに保存しておきます。これによって逆にたどっていけば復元することができます。経費精算できる金額をMとすれば、O(NM)くらいで解くことができます。これなら十分高速に解を求められるし、毎月経費精算ができますね。さいごに身近な問題を競プロっぽく解くのは面白いですね。競プロはネトゲみたいなところもありますが、実際にはこのような身近な問題を解決することができたりするので、少しでも気になった方はぜひ競プロに挑戦してみてください!さいごのさいごにちなみに今回のakht氏のリクエストからすると、1ヶ月分のランチの領収書が100枚になる可能性があるということで「なんかやべえな??」って感じがします。(ABS)のネタバ...2017-07-06PHP5.5で追加されたジェネレータについて調べた前にまとめたPHP5系で追加された機能を振り返る記事の続き。»プロフィールid:purple_jwlプログラミングやボードゲームなど、自分の好きなことを書くブログです。(12)月別アーカイブはてなブログをはじめよう!purple_jwlさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。