atcoder.jp問題を見てダイクストラ法ですかねと思い、ダイクストラ実装…してから気づいたけどよく考えたら最長経路問題だった。部分構造最適性が成立していないのでダイクストラ法みたいに計算量少なくは出来なかった…（色々考えた）辺の値全てに-1をかける…

atcoder.jp前回のやつより簡単だった（ただのナップサック問題で考察がほとんどいらないただのDPだったので） 何個選ぶか決めた時、価値の平均値が大きい順は価値の合計値が大きい順と同じ。合計を保持するDPを作って、最後にそれを個数で割って平均値を出し…