AtCoder ABC311 - G - One More Grid Task

たまには解説を書いてみます。

概要

\mathrm{O}(nm^2) 解の解説をします。

yfuka86 さんが書いた解説1の、帰着後の問題の解き方を解説します。

帰着後の問題

長さ m の整数列 B, C が与えられる。 l, r \,(1 \leq l \leq r \leq n) を適切に選ぶことによって、 ( \sum_{l\leq i \leq r}B_i )(\min_{l\leq i \leq r}C_i) として達成可能な最大値を求めよ。

入力例2を使って考えていきます。

4 5
3 1 4 1 5
9 2 6 5 3
5 8 9 7 9
3 2 3 8 4

l_y = 2, r_y = 3 の場合を考えてみます。

この時、 B = (5,8,17,5), C = (1,2,8,2) です。

高さが C_i で、横幅が B_i の長方形を並べてみます。

( \sum_{l\leq i \leq r}B_i )(\min_{l\leq i \leq r}C_i) はこの図形に含まれる長方形の面積に対応します。例えば、赤色の長方形は l = 2, r = 4 の場合に対応し、青色の長方形は l = 1, r = 3 の場合に対応しています。

従って、帰着後の問題の答えはこの図形に含まれる長方形の面積の最大値に等しいです。これはヒストグラム中の最大長方形を求める問題として知られており、スタックを使うか、Cartesian Tree2 を使うことで、 \mathrm{O}(n) で解くことができます。

ヒストグラム内の最大長方形 | アルゴ式3

  1. https://atcoder.jp/contests/abc311/editorial/6833↩
  2. Library Checker↩
  3. この解説では、lower_left や lower_right を求めるのにスタックを使っていますが、Cartesian Tree を使って求めることもできます↩