第六回アルゴリズム実技検定

PAST006K 商品券を無視端数の扱いが面倒なので，まずは商品券を無視して考える． \(u-p \geq 0\) なら買う， そうで無ければ買わない， が最善． 商品券を考慮端数の扱いを綺麗に扱うのは難しそう． そこで，全探索したいので，DPが良さそう． DPを考えるにあたって，同一視できる物や区別しないといけない物を考える． 端数は区別する必要があるので，記録しながら遷移． 今調べている番号 \(i\) 以前は，どれを買ったかは区別しなくてよい． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" i…

PAST006J 解法1\(p\) に関する多項式と見る． 平方完成すれば，どの \(p\) で最小になるか分かる． 解法2-(i)三分探索．今回， \(p\) に関して(下に)凸な関数なので可能． 解法2-(ii)三分探索の代わりに二分探索．導関数を2分探索して，0になる値を見つける． 導関数を自前で用意する必要がある． 実装は，三分探索で行った． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main() { ll n, c; cin >> n >> c; vll vx(n), vy(n…

PAST006I 実装上の注意 同じ場所で2回釣らないこと．(今のマスで釣ったか) \(\in Bool\) で管理した． 遷移に注意すれば，このフラグは無くてもDPは可能． その場合，(移動2種類)x(移動先で釣るor釣らない)の4通りの遷移になる． 移動先で釣るかどうかを決めるのが大事． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" ll dp[220][110][110][2]; int main() { ll h,w; cin >> h >> w; vvll a(h, vll(w)); ci…

PAST006G 辿り着く事のできる頂点は単調増加． よって，前日までの結果との差分を計算して高速化したい． 一度調べ終わった頂点，辺はもう一度調べる必要は無さそう． 新たに追加される頂点 \(v\) の入れ物 新たに追加される辺 \(e\) の入れ物 を用意しておけば良い感じ． ただし，辺はコストが \(x_{i}\) 以下である必要がある． それを高速に取り出すために，priority_queue を使っておくと良さそう． とりあえず，辿り着いた頂点 \(v\) から出ている辺 \(e\) を， 使える候補として priority_queue に入れておく． そして， \(x_{i}\) …