ARC072 F - Dam

1.7年前(2017/4/22)の本番では解法の見当もつかなかったが、改めて考えてみたら分かった。
F - Dam

問題

数Lと数列v_1, ..., v_N, t_1, ..., t_Nが与えられる。このとき、各1 <= i <= Nに対して以下の問いに答えよ。

  • 許容量Lリットルのダムに水を流入させることを考える。1日目にt_1度の水v_1リットルが流入し、その後水を任意量捨て、2日目にt_2度の水v_2リットルが流入し、…ということをi日目まで行う。各流入後に水を捨てる量をうまく調節して、i日目の流入のあとダムに水がLリットルある状態での温度を最大化したい。最大値を求めよ。

1 <= N <= 5 * 10^5
1 <= L <= 10^9
1 <= v_i <= 10^9
0 <= t_i <= 10^9

解法

i日目に水を捨てたあとの状態で、水がvリットル残っている状態での温度の最大値をf(i, v)と置くことにする。f(i, v)はvについて単調減少である。
g(i, v)をi日目に水を捨てる前の温度の最大値とすると、g(i, v) = (f(i - 1, v - v_i) * (v - v_i) + t_i * v_i) / v, f(i, v) = max_{w >= v} g(i, w)である。
ここで、f, gの代わりにp(i, v) = vf(i, v), q(i, v) = vg(i, v)を考えることにすると、q(i, v) = p(i - 1, v - v_i) + t_i * v_i なのでq(i, v)のグラフはp(i - 1, v)のグラフに(0, 0)と(v_i, t_i * v_i)を端点とする線分を連結させたものになる。またg(i, v)からf(i, v)を作るときに行われるchmaxのような処理は、p, qを使って表すとp(i, v) = v * max_{w >= v} (q(i, w) / w)である。qからpを作る操作は原点から見ていって傾きが増加したらグラフを書き換える、という操作を貪欲にやることで行える。図にすると以下のようになる。(Desmos | Graphing Calculatorで作成)

f:id:koba-e964:20190112160034p:plain
chmax前
f:id:koba-e964:20190112160010p:plain
chmax後
この操作を効率的にやるためには、dequeもしくはstackがあればよい。
計算量はO(N)である。

登場する典型

  • 最適値をパラメータを使って表す

実装上の注意点

  • stackを使って実装することもできるが、解説のようにdequeを使う方がよい(今回はstackを使った)

提出: Submission #3980185 - AtCoder Regular Contest 072 (Rust)

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (write!(out,$($format)*).unwrap());
    }
    input! {
        n: usize,
        l: f64,
        tv: [(f64, f64); n],
    }
    // Let x be the sum of v for all entry (v, _, _).
    // An entry (v, p, acc) means
    // (x - v, acc - p) and (x, acc) are connected by a segment.
    // We are to find max_y{(f(x) - f(x - y)) / y}.
    let mut pool: Vec<(f64, f64, f64)> = Vec::new();
    // Sentinel. l liter of water with temperature -1.0
    pool.push((l, -1.0, -l));
    // The pointer is at pool[cur].0 + pos
    // This pointer should always be at x - l, where x is described above.
    let mut cur = 0;
    let mut pos = 0.0;
    for (t, v) in tv {
        let mut last = pool[pool.len() - 1].2;
        pool.push((v, t * v, last + t * v));
        // Advances pointer by v
        let mut rem = v;
        while rem > 0.0 {
            if pool[cur].0 - pos < rem {
                rem -= pool[cur].0 - pos;
                cur += 1;
                pos = 0.0;
            } else {
                pos += rem;
                break;
            }
        }
        assert!(pos <= pool[cur].0 + 1e-9);
        // Greedy chmax
        while pool.len() >= 2 {
            let (v1, p1, acc1) = pool[pool.len() - 1];
            if v1 >= l { break; }
            let (v2, p2, _acc2) = pool[pool.len() - 2];
            if p2 / v2 > p1 / v1 {
                pool.pop();
                pool.pop();
                if v1 + v2 >= l {
                    pool.clear();
                    let newp = p1 + p2 / v2 * (l - v1);
                    pool.push((l, newp, newp));
                    // x = l. Pointer's position is reset to 0.0.
                    cur = 0;
                    pos = 0.0;
                } else {
                    pool.push((v1 + v2, p1 + p2, acc1));
                    if cur == pool.len() {
                        cur -= 1;
                        pos += pool[cur].0;
                    }
                }
            } else { break; }
        }
        let (v, p, acc) = pool[cur];
        let acclast = pool.last().unwrap().2;
        puts!("{:.15}\n", (acclast - acc + (p / v) * (v - pos)) / l);
    }
}

まとめ

実装の単純化が少し不足していた。