# キーエンス プログラミング コンテスト2021 A - Two Sequences 2

キーエンス プログラミング コンテスト2021 A - Two Sequences 2

問題へのリンク

https://atcoder.jp/contests/keyence2021/tasks/keyence2021_a

問題概要

長さ $NN$ の数列 $aa$, $bb$ があり、 $ii$ 番目の数はそれぞれ $aia_i$, $bib_i$ である。$cn=max1≦i≦j≦naibic_n = max_{1 \leqq i \leqq j \leqq n}a_ib_i$ を要素として持つ長さ $NN$ の数列 $cc$ を作る。各 $c1,c2,…,cNc_1, c_2, \dots, c_N$ を求めよ。

制約

$1≦N≦2×1051 \leqq N \leqq 2 × 10^5$
$1≦ai,bi≦1091 \leqq a_i, b_i \leqq 10^9$

ABC中の解答

制約 $1≦N≦2×1051 \leqq N \leqq 2 × 10^5$ から単純に for を２回使って計算しては TLE となってしまうので何かしらの工夫は必要だと気づいた。けどそれが何かぱっと思いつかなかった。累積和と同じように累積Max的なものを取ればいいのかな？でも $AA$ 側から使える $BB$ が全部とは限らないしなと考えていた。
ノートにまとめていくと、 $cic_i$ の場合 $AiA_i$ だけ $BiB_i$ のみしか考慮できないが、それより前の $AA$ の値たちはすべての $BiB_i$ を考慮してよいと気づいたので、 $ii$ より前の $AA$ の最大値と $BB$ の最大値をメモしておけば、最大値と $ii$ 番目の値のみ考慮しそれ以外は計算しなくてよいと考えDP風に実装した。

$dpdp$ = [$AA$の$ii$番目までの最大値, $BB$の$ii$番目までの最大値, $AxByA_xB_y$の最大値すなわち$cic_i$]
とした。

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
# cn = max1<=i<=j<=n aibj

dp = [A[0], B[0], A[0] * B[0]]
print(dp[2])
for i in range(1, N):
    dp[2] = max(dp[2], dp[0] * B[i], A[i] * B[i])
    dp[0] = max(dp[0], A[i])
    dp[1] = max(dp[1], B[i])
    print(dp[2])

https://atcoder.jp/contests/keyence2021/submissions/19466016

公式解法1

$cnc_n$ は $cn=max(cn−1,max(a1,a2,…,an)bn)c_n = max(c_{n-1}, max(a_1, a_2, \dots, a_n)b_n)$ と表すことができる。したがって、ABC中の解答でも触れたように累積Maxを計算しておけば $O(N)O(N)$ で解くことができる。

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

max_A = [A[0]]
for i in range(1, N):
    max_A.append(max(max_A[i - 1], A[i]))

C = [A[0] * B[0]]
for i in range(1, N):
    C.append(max(C[i - 1], max_A[i] * B[i]))

for c in C:
    print(c)

https://atcoder.jp/contests/keyence2021/submissions/19480371