マツシタのお勉強

2016-11-28から1日間の記事一覧

バレンタインデーの幸福度を最も高くするためにやるべき5つのステップ

問題 D: バレンタインデー - AtCoder Beginner Contest 018 | AtCoder 解法 グループにどの女子を含ませるか決まれば、どの男子を含めるべきかは貪欲に決定される。よって以下のステップで解くことができる。 グループに含める女子を固定 幸福度が最も高くな…

動的計画法が困難なナップザック問題

問題 D: ナップサック問題 - AtCoder Beginner Contest 032 | AtCoder 解法 この問題はナップザック問題を応用したものである。入力値は以下の3つの条件のどれかが当てはまる N <= 30 のケース それぞれの荷物の価値Viが1000以下のケース それぞれの荷物の…

プライオリティキューを用いたダイクストラ法 ~トレジャーハント編 ~

問題 D: トレジャーハント - AtCoder Beginner Contest 035 | AtCoder 解法 流れ 滞在する必要のある頂点は1つと考える。滞在する頂点を頂点iとすると、頂点0から最短で頂点iに到達し、できるだけ長く頂点iに滞在し、最短で頂点0に戻る事を考える。頂点iを…