AGC004 B Colorful Slimes

beta.atcoder.jp

所見

変数を一つ固定すると見通しが良くなるパターン。こういうのは回数って感じだ

問題概要

N色のスライムが存在する。色iのスライムはつかまえるのにa_iの時間がかかり、魔法を使うとxの時間を消費して色iのスライムを色i+1に変えることができる。すべての色のスライムを手に入れるのにかかる最短時間を求めよ。

取った方針

一番安いm個の区間のスライムを捕まえてmを全探索しようとするも嘘なのでNG。
その後いろいろ実験するも上手くいかず終了

正しい方針

魔法を使う回数をkで固定すると、色iのスライムを得るための最小コストはmin(a_i-k, ... a_i)となる。
それをb_i(k)と置くと、b_i(k) = min(a_i-k, b_i(k-1))であることを利用してすべてのb_i(k)がO(N²)で求まる。
よって、k回魔法を使うときの最小コストはb_1(k)+...+b_N(k)+k*xで求められ、O(N²)で解が求まる。

得られた知見

・変数を固定すると見通しがよくなりがち
・固定できそうな変数は全部試してみる

解くのに必要な要素

・変数固定->全探索
・[i,j]の最小値がkの時、[i, j+1]の最小値はmin(k, j+1番目の数)みたいなアレ

周辺調査によって得られた知見

特になし