PAST006N DPをしたいが，順序によって得られる値が変わる． よって，最適な順序にソートしてからDPする．\(i \rightarrow j\) , \(j \rightarrow i\) のそれぞれに対して得点を調べて， 差分を計算すれば \( a_{i}/ b_{i} \geq a_{j} / b_{j}\) の順で行うの…

PAST006L 問題設定すべての頂点を行き来できる様にすれば良い． 一度つながった辺や円は自由に行き来できるので，connected component の様に考えてよい． 頂点を全て通る様な connected component の作り方が問題になる． 実装ここで，\(M \leq 8\) と小さ…

PAST006K 商品券を無視端数の扱いが面倒なので，まずは商品券を無視して考える． \(u-p \geq 0\) なら買う， そうで無ければ買わない， が最善． 商品券を考慮端数の扱いを綺麗に扱うのは難しそう． そこで，全探索したいので，DPが良さそう． DPを考えるに…

PAST006J 解法1\(p\) に関する多項式と見る． 平方完成すれば，どの \(p\) で最小になるか分かる． 解法2-(i)三分探索．今回， \(p\) に関して(下に)凸な関数なので可能． 解法2-(ii)三分探索の代わりに二分探索．導関数を2分探索して，0になる値を見つける…

PAST006I 実装上の注意 同じ場所で2回釣らないこと．(今のマスで釣ったか) \(\in Bool\) で管理した． 遷移に注意すれば，このフラグは無くてもDPは可能． その場合，(移動2種類)x(移動先で釣るor釣らない)の4通りの遷移になる． 移動先で釣るかどうかを決め…

PAST006G 辿り着く事のできる頂点は単調増加． よって，前日までの結果との差分を計算して高速化したい． 一度調べ終わった頂点，辺はもう一度調べる必要は無さそう． 新たに追加される頂点 \(v\) の入れ物 新たに追加される辺 \(e\) の入れ物 を用意してお…